## 技巧
### Basic Skill
#### 二進制左移計算
```python!
1 << 3 = 2 ** 3 = 8 = 0b1 << 3 = 0b1000 # 補三個零，因為 0b1 左移三位
```
等價於 2 的 3 次方
#### 二進制右移計算
```python!
6 >> 1 = 6 // 2 = 3
```
等價於除以二並且拋棄於數(只取商值)
#### 二進制 & (AND)
兩個數字的二進位都要為 1 才能為 1
```python!
6 & 6 = 6 = 0b110 & 0b110 = 0b110
5 & 2 = 0 = 0b101 & 0b10 = 0b000
```
#### 二進制 | (OR)
兩個數字的二進位任何一個為 1 就能為 1
```python!
5 | 2 = 7 = 0b101 | 0b10 = 0b111
```
#### 二進制 ~ (NOT)
```python!
~5 = 2 = ~0b101 = 0b10
```
#### 二進制 ^ (XOR)
**XOR** 運算（或**異或**）採用兩位並返回1 1 如果**正好**有一位是1 1。否則，它返回0 0。
```python!
5 ^ 6 = 0b0101 ^ 0b0110 = 0b0011 = 3
```
#### 確認數字是否為基偶數
```python=
def evenOdd(n: int) -> bool:
"""
Check if a number is even or odd
:param n: int
:return: bool
"""
return n & 1 != 0
```
過程：
```python=
ex1: evenOdd(5)
0b101 (5) & 0b001 = 0b001 (1)
1 != 0 = True
ex2: evenOdd(2)
0b10 (2) & 0b01 = 0b00 (0)
0 != 0 = False
```
#### 確認數字是否為負數
```python=
def isOpposite(n: int) -> bool:
"""
Check if a number is opposite sign
:param n: int
:return: bool
"""
return 1 ^ n < 0
```
過程:
```python=
ex1: isOpposite(5)
0b101 (5) = 0b001 ^ 0b101 = 0b100 (4)
4 < 0 = False
ex2: isOpposite(-1)
-0b1 (-1) = -0b1 ^ 0b1 = -0b10 (-2)
-2 < 0 = False
```
#### 數字加一
```python=
def addOne(n: int) -> int:
"""
Add one to a number
:param n: int
:return: int
"""
return -~n
```
#### 數字減一
```python=
def subOne(n: int) -> int:
"""
Sub one to a number
:param n: int
:return: int
"""
return ~-n
```
#### 兩數字交換 (不使用額外變數)
```python=
def swapNumber(x: int, y: int) -> [int, int]:
"""
Swap two numbers
:param x: int
:param y: int
:return: [int, int]
"""
x ^= y
y ^= x
x ^= y
return x, y
```
過程：
```python
ex: swapNumber(3,4)
input:
x = 0b11 (3)
y = 0b100 (4)
x = x ^ y => 0b011 ^ 0b100 = 0b111
y = x ^ y = 0b111 ^ 0b100 = 0b011
x = x ^ y = 0b111 ^ 0b011 = 0b100
output:
x = 0b100 (4)
y = 0b011 (3)
```
### K'th Bit
#### 把第k位數字變為0
```python=
def offKthBit(n: int, k: int) -> int:
"""
Turn off kth bit in a number
:param n: int
:param k: int
:return: int
"""
return n & ~(1 << k)
```
過程:
```python
ex1: offKthBit(5,2)
0b101 (5) & ~(1 << 2) = 0b101 & 0b011 = 0b001 (1)
ex2: offKthBit(8,3)
0b1000 (8) & ~(1 << 3) = 0b1000 & 0b0111 = 0b0000 (0)
```
#### 把第k位數字變為1
```python=
def onKthBit(n: int, k: int) -> int:
"""
Turn on kth bit in a number
:param n: int
:param k: int
:return: int
"""
return n | (1 << k)
```
#### 反轉第k位數字
```python=
def toggleKthBit(n: int, k: int) -> int:
"""
Toggle kth bit in a number
:param n: int
:param k: int
:return: int
"""
return n ^ (1 << k)
```
### Right most set bit of number
#### 去除最右邊的 1
```python=
def unsetRightMostBit(n: int) -> int:
return n & (n - 1)
```
#### 找到最右邊的 1
```python=
def findRightMostPosition(n: int) -> int:
return n & (n - 1) ^ n
```
#### 查看數字是否 Power of two
```python=
def isPowerOfTwo(n: int) -> bool:
return n & (n - 1) == 0
```
#### 查看最右邊 1 的位置
```python=
def findRightMostPosition(n: int) -> int:
"""
Find right most position in a number
:param n: int
:return: int
"""
if n & 1 != 0: # check if n is odd
return 1
n = n & (n - 1) ^ n # unset right most bit
pos = 0
while n > 0: # right shift until n is 0
n = n >> 1
pos += 1
return pos
```
##### 優化版本 Time complexity O(1)
取 2 的對數直接得到位置
```python=
def findRightMostPositionO1(n: int) -> int:
"""
Find right most position in a number
:param n: int
:return: int
"""
if n & 1 != 0: # check if n is odd
return 1
return int(log2(n & -n)) + 1
```
#### 取得只有一個1的二進制唯一位置
```python=
def positionOfOnlySetBit(n: int) -> int:
"""
Find position of only set bit in a number
input most be power of two
:param n:
:return:
"""
if n & (n - 1) != 0: # check n is power of two ,because if n is power of two ,binary will be 10...0
return 1 # if not return 1
return int(log2(n)) + 1
```
#### 查詢二進制中 1 的數量是奇數還是偶數
```python=
def findParityRightShift(n: int) -> bool:
"""
Find parity of a number
Note: 'Parity' is compute the number of 1 in binary count is odd or even
:param n:
:return:
"""
parity = False
while n:
if n & 1:
parity = not parity
n = n >> 1
return parity
def findParityOffRight(n: int) -> bool:
"""
Find parity of number
Note: 'Parity' is compute the number of 1 in binary count is odd or even
This version is turn off rightmost bit one by one ,in the end the n will be 0, and stop the loop
:param n:
:return:
"""
parity = False
while n:
parity = not parity
n = n & (n - 1)
return parity
```
### English letters and alphabet
#### 大寫英文字母轉成小寫 (uppercase to lowercase)
ascii 65 ~ 91 對應到 'A' ~ 'Z'
每個字母對空格 (ascii 32) 做 bitwise or 就可以對應到 ascii 的 小寫字母
這也是相當於對數字直接做加法
```python!
ex: 'A' (ascii 65) | ' ' (ascii 32) = 0b1000001 | 0b0100000 = 0b1100001 (97) => (ascii 'a')
```
```cpp=
// cpp
for (char ch = 'A'; ch <= 'Z'; ch++) {
cout << char(ch | ' ');
}
```
```python=
# python
for i in range(65,65+26):
print(chr(i | ord(' '))) # show a~z
```
```python=
# python
def upperToLower(s: str) -> str:
"""
Convert upper case to lower case
:param s:
:return:
"""
return chr(ord(s) | 32)
```
#### 小寫英文字母轉大寫
ascii 97 ~ 123 對應到 'a' ~ 'z'
```cpp=
// cpp
for (char ch = 'a'; ch <= 'z'; ch++) {
cout << char(ch & '_');
}
```
```python=
# python
for i in range(97,97+26):
print(chr(i & ord('_')))
```
```python=
# python
def lowerToUpper(s: str) -> str:
"""
Convert lower case to upper case
:param s:
:return:
"""
return chr(ord(s) & 95)
```
### 二進制的負數轉換過程
二進制中會使用一個標記位 0 或 1 來表示是否為負數
轉換步驟如下:
1. 取得正數下的二進制數值
2. 翻轉正數下的二進制數值
3. 翻轉過後的二進制需要再加一
4. 轉換為十進制的時候，最前面的數字 1 需要轉換為負數，其餘的為正數，最後全部數字相加，就會得到正確的十進制負數
```python!
ex: -5
5 = 0b0101
1. 翻轉
0b0101 => 0b1010
2. 二進制 +1 # 2 的補數
0b1010 => 0b1011
3. 計算證明
0b1011 = ((-2**3) * 1) + ((2 ** 2) * 0) + ((2 ** 1) * 1) + ((2 ** 0) * 1) = -8 + 0 + 2 + 1 = -5
```
### 二進制中的 Arithmetic Right Shift 和 Logical Right Shift
二進制中有兩種 Right Shift 方式，一種是 Logical Right Shift，就是正常的把二進制往右移
```python!
0b10110101 (-75) => 0b01011010 (90)
```
但是會發現，使用 Logical Right Shift 的話，如果數字是負數的時，往右移之後數字就會變成正數，所以就有了 Arithmetic Right Shift，Arithmetic Right Shift 會在所有 bit 往右移動之後，把最前面的 bit 換成 1 **(注意 `` )**，以確保右移時數字不會從負數變成正數
```python!
0b10110101 (-75) => 0b`1`1011010 (-38)
```
從上面兩個例子就可以很容易地看出兩種 Right shift 的不同
### 如何使用位運算求和
```python!=
class Solution:
def addBinary(self, a: str, b: str) -> str:
x = int(a,2)
y = int(b,2)
while y:
ans = x ^ y # 使用 XOR 計算餘數
c = (x & y) << 1 # 使用 & 計算進位，並且向右移一位
# 假設 (11 & 01) << 1 = 01 << 1 = 10
x,y = ans,c # 把 x 記錄成餘數，y 記錄成進位，重複做到 y 為零為止
return bin(x)[2:] # 把數字轉換成二進制，並且把前面的 0b 去除
```
ex: x = 0b11, y = 0b01
### 如何計算二進位有幾個 1
#### 1. 掃描每個 bit 並且做 AND 確認
```python!
class Solution:
def hammingWeight(self, n: int) -> int:
output = 0
for i in range(32):
if n & (1 << i): # 1 << i 會創建類似 0001, 0010, 0100 的二進制 取決於 i 是幾位，使用左移特性逐一掃描做AND，確認每一位bit是否為 1，為 1 output 就加一
output += 1
return output
```
Time complexity: O(L) 取決於二進制有多長
Space complexity: O(1)
#### 2. 位運算優化
ex: 0b110 (6)
1. 0b110 & 0b101 = 0b100
2. 0b100 & 0b011 = 0b000 # 停止
相比於每個bit做AND比較的解法，本來要做六次操作，現在只需要做兩次
```python!
class Solution:
def hammingWeight(self, n: int) -> int:
output = 0
while n:
n &= n - 1 # 每次做這個操作就會去掉一個 1 直到 n 為零為止
output += 1
return output
```
Time complexity: O(logn)
Space complexity: O(1)
### 如何算出二進制數字的長度
```python!
def binary_length(num):
length = 0
while num > 0:
num >>= 1
length += 1
return length
# 測試
number = 37 # 將這裡的數字替換為你想要計算的二進制數字
length = binary_length(number)
print("二進制數字 {} 的長度為 {}".format(bin(number)[2:], length))
```
### 快速走訪二元樹的特定節點
1. 先找出要找節點的 level ，套入公式 node = 1 << (level - 1)
2. 使用 node & target 得到 0 或 1，0 代表 left，1 代表 right
3. 每次 node 比較完 target 都要向右移一位 node >>= 1
4. 直到 node == 0 時停止尋找節點
5. 如果節點存在，則會在 node == 0 時走到節點上，判斷指針是否為 null 即可
note: 也可以使用 math.log2(node_num) 來取 2 的對數取得第幾層
## 練習題
1. 0b0110 (6) + 0b0010 (2) = 0b1000 (8)
2. 0b0011 (4) * 0b0101 (5) = 0b11001 (25)
3. 0b0110 (6) + 0b0110 (6) = 0b0110 (6) * 2 = 1 << 0b0110 = 12
4. 0b0011 (3) + 0b0010 (2) = 0b0101 (5)
5. 0b0011 (3) * 0b0011 (3) = 0b01001 (9)
```python!
(5)
0011 (3)
x 0011 (3)
------- (以下加法)
0011
0011
0000
0000
-------
0001001 (9)
```
8. 0b1101 () >> 2 = 11 (3)
12. 0b1011 & (~0 << 2) = 0b1011 & 0b0100 = 0
## 參考資料
[Bit manipulation interview questions and practice problems](https://medium.com/techie-delight/bit-manipulation-interview-questions-and-practice-problems-27c0e71412e7)
Sign in with Wallet
Connect another wallet