資料結構
網路
關係資料庫管理系統 (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 次瀏覽
