C++ 设置最左侧未设置的位

本文旨在寻找设置给定数字最左侧未设置位的方法。在最高位设置位后的第一个未设置位被认为是最左侧未设置位。

问题描述

给定一个数字n，任务是设置该数字二进制展开中未设置的最左侧位。所有其他位应保持不变。如果原始数字的所有位均已设置，则返回该数字。

示例

Input: 46

Output: 62

解释

46的二进制展开为101110。

最左边未设置位是101110。

通过设置下划线标记的位，我们得到111110。这是62的二进制展开。

因此答案是62。

Input: 11

Output: 15

解释

11的二进制表示为1011。

最左边未设置的位是1011。

改变下划线标记的位后，我们得到1111，这是15的二进制表示。

Input: 30

Output: 31

解释

30的二进制展开是11110。

最左边未设置的位是11110。

在设置最左边未设置的位后，我们得到11111，这是31的二进制展开。

Input: 7

Output: 7

解释

7的二进制展开为111。

由于所有位都被设置，不存在最左边未设置的位。因此答案与原始数值保持相同。

解决方法

检查所有位是否被设置。如果是，则将原始数值作为答案返回。
使用按位与运算符找到最新的未设置位的位置，并更新计数器。
设置与计数器相对应的位。
显示答案。

判断是否所有位都被设置

思路是通过添加一位，如果所有位都被设置，输入数将变为2的完全平方数。因此，以下表达式将确定数的所有位是否被设置：n & (n + 1) 0;

让我们通过一个例子来理解。

假设数是5。我们需要检查数5的所有位是否被设置。

n = 3	n + 1 = 4	n & (n + 1)
011	100	000

因此我们可以安全地得出结论，n的所有位都已经设置，我们将原样返回这个数字。

查找最左侧未设置的位

如果AND运算的输出不等于零，我们继续查找最左侧未设置的位。首先生成一个位数与给定整数相等的新数字。新数字的最左位是初始设置的。

然后，我们运行一个循环，从最左侧的1位开始，通过对给定数字和新数字进行按位AND运算，向右搜索第一个0。当AND运算的结果为0时，返回第一个未设置的最左位的位置pos。

设置最左侧未设置的位

生成一个新数字，其中只有与位置pos对应的位设置。对这个新数字和原始数字执行按位OR运算。

步骤

函数 all_bits_set()

计算 n & (n + 1)。
如果结果等于0，则返回true。
否则返回false。

函数 find_leftmost_unset_bit()

初始化 m = 1，pos = 0。
while (n > m)
- 左移 m 1 次。
右移 m 1 次，使其对应于n的最高有效位。
while ((n & m) != 0)
- 右移 m 1 次。
- pos++
循环结束后，我们得到了从最高有效位向最左侧未设置的位的位置。
返回 log2(n) – pos，即从LSB的位位置。

函数 set_leftmost_unset_bit()

初始化 k = 1
调用 find_leftmost_unset_bit() 函数。
k = k << pos
计算 n | k。
更新 n。

函数 main()

初始化 n
调用 all_bits_set() 函数
调用 find_leftmost_unset_bit() 函数
调用 set_leftmost_unset_bit() 函数
显示 n

示例：C++程序

这个程序通过将输入数字n的二进制展开中最左边未设置的位设置为1来修改它。它使用位运算符OR，左移和右移运算符以及位与运算符来实现其目标。

// A C++ program to set the left most unset bit of a number. If all the bits of the given number are already set, it returns the number as it is.
#include <iostream>
#include <cmath>
using namespace std;
// function to check if all bits of the given number are already set
// if all bits of n are set, n + 1 will be a power of 2.
bool all_bits_set(int n){
   if ((n & (n + 1)) == 0)    {
      return true;
   }
   return false;
}

// function to find the position of the leftmost unset bit from the LSB.
int find_leftmost_unset_bit(int n){
   int m = 1, pos = 0;
   while (n > m){
      m = m << 1;
   }
   m = m >> 1; // to make the number of digits in m equal to number of digits in n

   // the following loop executes till the first zero is encountered, starting from the msb
   while ((n & m) != 0){
      m = m >> 1;
      pos++;
   }

   // since pos is the position of the unset bit from the MSB we return log2(n) - pos which is the location of the leftmost unset bit from the LSB.
   return log2(n) - pos;
}

// function to set the leftmost unset bit from the LSB.
void set_leftmost_unset_bit(int &n){
   int k = 1;
   int pos = find_leftmost_unset_bit(n);
   k = k << (pos); // left shift k by pos
   n = n | k; // to set the leftmost unset bit
}

// main function
int main(){
   int n = 46;
   cout << "Input Number: "<< n << endl;
   if (all_bits_set(n))    {
      cout << n << endl;
      return 0;
   }
   set_leftmost_unset_bit(n);
   cout << "Number after setting the Leftmost Unset Bit: " << n << endl; // display the updated number
   return 0;
}

输出

Input Number: 46
Number after setting the Leftmost Unset Bit: 62

时间和空间分析

时间复杂度：O(log2(n)) ，因为在函数find_leftmost_unset_bit()中，我们可能需要遍历二进制展开的log2(n)位来找到最左边未设置的位。

空间复杂度：O(1) ，因为实现中始终使用恒定的空间。

结论

本文讨论了一种查找和设置给定数字最左边未设置位的方法。如果数字的所有位都已设置，我们将返回数字本身。否则，为了设置所述位，我们使用位左移和右移运算符生成新的位模式，并使用位或运算符计算结果。对解决方案的概念、多个示例、所使用的算法、C++程序解决方案以及时间和空间复杂度分析进行了详细解释，以便更深入地理解。