数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究设置最右边的未设置位
问题陈述包括在 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+1 的二进制表示只是将 N 从右边开始的第一个未设置位设置为 1，并取消设置 N 的所有设置位，直到我们找到第一个未设置位。
这可以用表达式更好地解释
$$\mathrm{2^{n}=2^{n-1}+2^{n-2}+....+2^{0}+1}$$
因此，如果我们在数字及其旁边的数字上应用 OR 运算，我们可以将 N 的第一个未设置位设置为 1，而不会更改其他位，因为如果两个位都是 0，则 OR 返回 0；否则，如果任何一个位是 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++ 来实现该技术。本文中用于解决该问题的方法以恒定时间运行，使其成为最佳选择。我相信阅读本文后，您将更好地理解这个主题。
439 次浏览
