C++ 设置右侧未设置的位

问题说明包括在C++中设置任何正整数N的最右侧未设置位。当以二进制数的形式表示时，位就是任何数字的二进制位。

二进制数是以0和1的形式表示任何数据的数字表示，其中数字的每一位（位）表示2的幂，从单位数字开始，指数是2^0。

让我们以二进制数的形式表示整数7。

7的二进制表示将是111。

这些数字可以用32位或64位表示。

在此问题中，会提供一个正整数N，我们的目标是将最右侧未设置位（即最右侧的0位）设置为1。如果每个位都设置为1，则数字保持不变。

让我们使用一些示例来更好地理解问题说明。

输入

N=8

输出

9

解释：整数8的二进制表示为1000。在这里，第一个未设置的位是0，也就是第一个位。在修改第一个未设置的位之后，二进制数将变为1001，即\mathrm{2^{3}+2^{0}=9}。因此输出为9。

输入

N=19

输出结果

23

解释：19的二进制表示为10011。二进制数10011中第一个未设置的位是从右边数的第三位。将第一个未设置的位设置后，二进制数变为10111，即\mathrm{2^{4}+2^{2}+2^{1}+2^{0}=16+4+2+1=23}，这就是我们的输出。

输入

N=3

输出

3

解释：3的二进制表示是11。由于二进制数中没有未设置的位，保持数字不变。因此，3将是我们的输出。

让我们学习解决这个问题的算法，以设置任何数字中最右边的未设置的位。

算法

设置任何数字中最右边的位的想法非常简单。我们已经知道以二进制数形式表示任何数字的概念。

让我们将两个连续的数字用二进制形式表示，并观察模式。

假设数字是9和10。

9的二进制表示是1001。

而10的二进制表示是1010。

类似地，让我们看看12和13。

12的二进制表示是1100。

而13的二进制表示是1101。

如果我们仔细观察模式，我们可以得出结论：对于任何正数N，N的二进制表示中的第一个未设置的位的N+1只需将第一个未设置的位从右边设置为1，然后取消设置N的所有设置位直到找到第一个未设置的位。

这可以用以下表达式更好地解释：

\mathrm{2^{n}=2^{n-1}+2^{n-2}+….+2^{0}+1}
因此，如果我们对数字和其下一个数字进行OR操作，我们可以将N的第一个未设置的位设置为1，而不改变其他位，因为OR操作将返回0，如果两个位都为0，则返回1，如果两个位中有一个位为1，则返回1。

在应用N | N+1之前，我们需要检查N是否设置了所有位。如果是，则返回相同的数字。

方法

• 为了在任何数字中设置最右边的未设置位，我们将编写一个函数。

• 如果数字的所有位都设置，则只需返回该数字而不更改任何位。

• 我们可以通过简单地对N和N+1进行AND运算（N&(N+1)）来检查一个数字的所有位是否设置。如果它等于0，这意味着N的所有位都设置。返回数字N而不更改任何位。如果（N&(N+1)）的输出不等于0，则我们将对N和N+1（N | N+1）应用OR运算，并返回应用OR运算后得到的数字。

• 假设N=7，其二进制表示为111。在这种情况下，N的所有位都被设置。当我们取111（即7）和1000（即8）的AND时，我们将在所有这些情况下得到0。

• 通过这种方式，我们可以使用最有效的方法在任何数字N中设置第一个未设置的位。

这个方法的C++代码：

示例

#include <bits/stdc++.h>

using namespace std;

//function to set the rightmost unset bit of N
int setbit(int N){

   if(N&(N+1)==0){  //if all the bits of N are set
      return N;
   }

   int x= N | N+1; //if not, then set the rightmost unset bit of N using the OR operation

   return x;
}

int main()
{
   int N;
   N=33;
   cout<<"The number after setting the rightmost unset bit of "<<N<<" is : "<<setbit(N)<<endl;

   N=123;
   cout<<"The number after setting the rightmost unset bit of "<<N<<" is : "<<setbit(N)<<endl;


   return 0;
}

输出

The number after setting the rightmost unset bit of 33 is : 35
The number after setting the rightmost unset bit of 123 is : 127

时间复杂度 ：O(1)，因为只需要常数时间。

空间复杂度 ：O(1)，因为没有使用额外的空间。

结论

可以在C++中设置任何正整数N的最右边未设置的位。本文使用C++实现了这个技术。文章中使用的方法在常数时间内解决问题，使其成为最佳选择。我相信读完这篇文章后，您会对这个话题有更好的理解。