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 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告