資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究透過位操作將數字加1
位操作使用按位運算子（如 AND(&)、OR(|)、NOT(~)、XOR(^)、左移(<<) 和右移(>>)）對位流進行邏輯運算以獲得所需結果。使用按位運算子是有益的，因為我們可以操作單個位，並且它們比其他運算子更快。
問題陳述
給定一個數字。僅使用按位運算子將數字加1。（不要使用像 ‘+’、‘-’、‘*’ 或 ‘/’ 這樣的算術運算子）
方法一：使用反碼/非運算子
按位補碼/反碼是使用 NOT(~) 運算子實現的。
對於數字 n，n 的按位補碼，即 ~n = -(n+1)。因此，我們可以透過僅取 ~n 的值並忽略符號來得到 n+1。這可以使用 abs() 函式來完成，該函式返回變數的值並忽略符號。
虛擬碼
procedure inc (num) num = |~n| // | | represents the abs() function end procedure
示例
在下面的程式中，我們透過使用按位補碼運算子和絕對值函式來計算數字加1的結果。
#include <bits/stdc++.h>
using namespace std;
// Function for finding the increment of input by 1
int inc(int num){
// using the abs() function to get the value obtained by applying the ~ operator
num = abs(~num);
return num;
}
int main(){
int input = 7;
cout << input << " + 1 using bit manipulation = " << inc(input);
return 0;
}
輸出
7 + 1 using bit manipulation = 8
時間複雜度 − O(1)，因為沒有實現迴圈。
空間複雜度 − O(1)，因為沒有使用額外的空間。
方法二
來看一些二進位制加法的例子，如下所示：
從上面的例子可以看出，在對1進行二進位制加法時，數字右邊第一個未設定位的左邊二進位制位保持不變。但是，右邊第一個未設定位被設定，右邊所有的位都被反轉，即設定位被取消設定，未設定位被設定（0 轉換為 1，1 轉換為 0）。
因此，我們可以將我們的問題分解成兩個基本部分：
設定右邊第一個未設定位。
反轉右邊所有的位。
遞迴方法虛擬碼
procedure inc (num)
if num & 1 == 0
ans = num | 1
else
ans = inc (num >> 1) << 1
end if
end procedure
示例
在下面的程式中，我們使用遞迴根據上面解釋的思想將數字加1。
#include <bits/stdc++.h>
using namespace std;
// Function for finding the increment of input
int inc(int num){
// check if the LSB is set or not. If it is unset, it enters if otherwise, it goes to else
if ((num & 1) == 0) {
// LSB is set
return num | 1;
}
else {
// The number is right shifted and the function is called again
// After obtaining the return number from called function, the number is left shifted
return inc(num >> 1) << 1;
}
}
int main(){
int input = 14;
cout << input << " + 1 using bit manipulation = " << inc(input);
return 0;
}
輸出
14 + 1 using bit manipulation = 15
時間複雜度 − O(k)，其中 k 是從右邊第一個未設定位的位數。
空間複雜度 − O(k)，由於遞迴堆疊空間。
迭代方法虛擬碼
procedure inc (num)
m = 1
while num & m
num = num & (~m)
m = m << 1
end while
num = num | m
end procedure
示例
在下面的程式中，我們使用一個掩碼數字，該數字在每次迭代中都會更改，直到我們得到右邊第一個未設定位。發現它後，將設定未設定位，並將右邊所有其他位反轉。
#include <bits/stdc++.h>
using namespace std;
// Function for finding the increment of input
int inc(int num){
// declare a mask with value 1 which is used to find the first unset bit from right side
int m = 1;
// checks if LSB is set. If set enter the loop and repeat till we get to the unset bit
while (num & m) {
num &= ~m;
// mask is changed at every iteration to set the unset bit and toggle bits when the loop ends
m <<= 1;
}
// mask used to set the unset bit and toggle all the bits on the right-hand side
num |= m;
return num;
}
int main(){
int input = 14;
cout << input << " + 1 using bit manipulation = " << inc(input);
return 0;
}
輸出
14 + 1 using bit manipulation = 15
時間複雜度 − O(k)，其中 k 是從右邊第一個未設定位的位數。
空間複雜度 − O(1)
方法三
在這種方法中，我們試圖透過減少查詢第一個未設定位的時間來降低時間複雜度。在這種方法中，我們將首先找到從右邊第一個未設定位，設定它並反轉右邊所有的位。
虛擬碼
procedure inc (num)
pos = log2 (num & ~num)
add = 1 << pos
num = num | add
if pos != 0
toggle = (1 << pos) - 1
num = num ^ toggle
end if
ans = num
end procedure
示例
在下面的程式中，使用 Log2() 操作來查詢未設定位，左移和 OR 來設定位，以及左移和 XOR 來反轉位。
#include <bits/stdc++.h>
using namespace std;
// Function for finding the increment of input
int inc(int num){
// finds the position of the first unset bit from right
int pos = log2(num & ~num);
// the following 2 operations combined set the unset bit
int add = 1 << pos;
num |= add;
// Toggling bits only for the numbers where the first unset bit was not the LSB
if (pos != 0){
// Using left shift and XOR operations to toggle bits
int toggle = (1 << pos) - 1;
num ^= toggle;
}
return num;
}
int main(){
int input = 14;
cout << input << " + 1 using bit manipulation = " << inc(input);
return 0;
}
輸出
14 + 1 using bit manipulation = 15
時間複雜度 − O(1)
空間複雜度 − O(1)
結論
總之，為了將數字加1，我們可以使用反碼概念，或者透過分析加1時位的性質，我們可以遵循上述方法來獲得所需的結果。
863 次瀏覽
