n = 3
| n 1 = 4 |
n & (n 1) |
|
|
011 の中国語訳: | 011
| 100 |
000 |
|
Thus it is safe to conclude that all the bits of n are already set and we return the number as it is.
找到最左边未设置的位
如果AND操作的输出不等于零，则继续查找最左边未设置的位。首先生成一个位数与给定整数相等的数字。新数字的最左边位最初设置为1。
然后，我们运行一个循环，从最左边的1位开始，向右搜索第一个0，通过对给定数字和新数字进行位与运算来实现。当位与运算的结果为0时，我们返回第一个未设置的最左边位的位置pos。
To Set the Leftmost Unset Bit
Generate a new number in which only the bit corresponding to pos is set. Perform bitwise OR operation between this new number and the original number.
Algorithm
的中文翻译为：算法
Function all_bits_set()
Function find_leftmost_unset_bit()
Initialize m = 1, pos = 0.
while (n > m)
将 m 右移 1 位，以使其对应于 n 的最高有效位。
while ((n & m) != 0)
一旦循环中断，我们就可以得到最高有效位（MSB）中最左边未设置的位的位置。
返回 log2(n) - pos，即从最低有效位开始的位位置。
函数 set_leftmost_unset_bit()
Function main()
-
初始化 n
-
Function Call 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)位数来找到最左边的未设置位。
Space Complexity: O(1), as constant space is always used in the implementation.
Conclusion
本文讨论了一种寻找并设置给定数字最左边未设置位的方法。如果数字的所有位已经设置，我们将返回该数字。否则，为了设置该位，我们使用位左移和右移运算符生成一个新的位模式，并使用位或运算符计算结果。解决方案的概念、多个示例、使用的算法、C++程序解决方案以及时间和空间复杂度分析都被详细解释，以便更深入地理解。
