資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中清除給定數字的位範圍
給定一個數字n，編寫一個C++程式來清除l和r之間給定範圍內的位。其中，1 <= l <= r <= n的二進位制表示中的位數。
清除給定範圍內的位的方法
以下是C++中清除給定數字中位範圍的不同方法：
使用暴力方法
以下是使用暴力方法清除給定數字中位範圍的步驟：
- 步驟1：建立一個名為clearIthBit()的函式來清除第i位。
- 建立一個掩碼，在第i位為0，其他位置為1。
- 使用按位與運算子將掩碼應用於n，以清除第i位。
- 步驟2：使用迴圈單獨清除索引l到r的每個位，並呼叫函式clearIthBit()。
示例
#include <iostream>
using namespace std;
int clearIthBit(int n, int i) {
int mask = ~(1 << i);
return n & mask;
}
int main() {
int n = 63;
int l = 1, r = 3;
int result = 0;
for (int i = l - 1; i < r; i++) {
n = clearIthBit(n, i);
}
cout << n;
return 0;
}
空間複雜度：O(1)
時間複雜度：O(r-l+1)
因為我們正在執行從l到r的迴圈。
使用最佳化方法
以下是使用最佳化方法清除給定數字中位範圍的步驟：
- 步驟1：建立一個所有位都設定為1的掩碼。這可以透過對0取按位非(~)來完成。因為0可以是000....0000，所以它的反碼將是111....1111。
- 步驟2：為所有右側位建立一個掩碼，即我們需要將所有1右移r次。
- 步驟3：為所有左側位建立一個掩碼，即我們需要將所有位保持1 (l-1) 次。
- 步驟4：組合掩碼以獲得一個從l到r為0，其他位置為1的掩碼。
- 步驟5：使用掩碼清除n中從l到r的位。
示例
#include <iostream>
using namespace std;
int clearBits(int n, int l, int r) {
int allOnes = ~0;
int leftMask = allOnes << (r);
int rightMask = (1 << (l-1)) - 1;
int mask = leftMask | rightMask;
return n & mask;
}
int main() {
int n, l, r;
cout << "Enter the number (n): ";
cin >> n;
cout << "Enter the left index (l): ";
cin >> l;
cout << "Enter the right index (r): ";
cin >> r;
int result = clearBits(n, l, r);
cout << "Result after clearing bits from " << l << " to " << r << " is: " << result << endl;
return 0;
}
空間複雜度：O(1)
時間複雜度：O(1)
更新於：2024年9月2日
104 次瀏覽
廣告