数据结构
网络
关系数据库管理系统 (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 次浏览
广告