# Bit Manipulation (7)
> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
>
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)
<!-- 常用色碼紀錄
Easy: <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard: <font color="#ee2f56">**Hard**</font>
-->
## Introduction
位元運算包括以下:
* AND: `&`
* OR: `|`
* NOT: `~`
* Exclusive OR: `^`
| `P` | `Q` | `P & Q` | `P \| Q` | `P ^ Q` | `~P` |
| :-: | :-: | :-: | :-: | :-: | :-: |
| 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 |
* left shift: `<<`
* right shift: `>>`
| `P`(decimal) | `P`(binary) | `P << 1` | `P >> 1` | Remark |
| :-: | :-: | :-: | :-: | :-: |
| `26` | `11010` | `110100` | `01101` | 等同於 `*2` 或 `//2` |
## 1. Single Number
<font color="#00ad5f">**Easy**</font>
> You are given a non-empty array of integers `nums`. Every integer appears twice except for one.
>
> Return the integer that appears only once.
>
> You must implement a solution with $O(n)$ runtime complexity and use only $O(1)$ extra space.
### Example 1:
```java
Input: nums = [3,2,3]
Output: 2
```
### Example 2:
```java
Input: nums = [7,6,6,7,8]
Output: 8
```
### Constraints
* `1 <= nums.length <= 10000`
* `-10000 <= nums[i] <= 10000`
### Recommended complexity
* Time complexity: $O(n)$
* Space complexity $O(1)$
### Solution
最簡單的方式是使用一個 hash map 紀錄每個數字的出現次數，但會需要 $O(n)$ 的空間，且過程非常簡單。另一種方式可使用 exclusive or 的運算。
Exclusive OR(XOR, $\oplus$)的運算性質
| $P$ | $Q$ | $P \oplus Q$ |
| :-: | :-: | :-: |
| $T$ | $T$ | $F$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |
根據以上性質可知:
* a $\oplus$ a = 0
* a $\oplus$ 0 = 0
因此，只要將整個陣列兩兩一組做 XOR 的運算，因為重複數字會抵消為 0，所以最後計算的結果就是多餘不成對的數字。
```python=
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for num in nums:
res = num ^ res
return res
```
## 2. Numbers of 1 bits
<font color="#00ad5f">**Easy**</font>
> You are given an unsigned integer `n`. Return the number of `1` bits in its binary representation.
>
> You may assume `n` is a non-negative integer which fits within 32-bits.
### Example 1:
```java
Input: n = 00000000000000000000000000010111
Output: 4
```
### Example 2:
```java
Input: n = 01111111111111111111111111111101
Output: 30
```
### Recommended complexity
* Time complexity: $O(1)$
* Space complexity: $O(1)$
### Solution
> [!Note]
> 題目給定的數字都是十進位置的整數，只不過在進行 bitwise operation 時會自動轉成二進位制
針對二進位的數字逐一檢查每個位置有沒有 `1`，所以需要一個能隨著位移做 mask 的數字，可用 `1 << i` 建立，因為 `1 << 2` 等同於將 `000..0001` 往左位移兩位，可得 `00..00100`。因此 `1 << i` 相當於對第 `i` 位做 mask。
題目限制長度是 32-bits 的整數，所以可以每個 bit 逐一跟 `1` 做 AND 運算
* 若結果 = 1 表示該位置有 `1`
* 若結果 = 0 表示該位置沒有 `1`
```python=
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
for i in range(32):
mask = 1 << i
if n & mask == 0: # i-th bit of n is 0
continue
res += 1
return res
```
## 3. Counting Bits
<font color="#00ad5f">**Easy**</font>
> Given an integer `n`, count the number of `1`'s in the binary representation of every number in the range `[0, n]`.
>
> Return an array `output` where `output[i]` is the number of `1`'s in the binary representation of `i`.
### Example 1:
```java
Input: n = 4
Output: [0,1,1,2,1]
```
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
### Constraints
* `0 <= n <= 1000`
### Recommended complexity
* Time complexity: $O(n)$
* Space complexity: $O(n)$
### Solution
**(1) 可採用前一題的做法**
從 0 開始檢查到 n，每個數字都去計算有幾個 1。內圈 `mask` 的長度可以參考題目的 constraints 設計一個定值。
```python=
class Solution:
def countBits(self, n: int) -> List[int]:
res = []
for num in range(n + 1):
count = 0
for i in range(11):
mask = 1 << i
if num & mask == 0:
continue
count += 1
res.append(count)
return res
```
**(2) Dynamic programming**
暫略
## 4. Reverse Bits
<font color="#00ad5f">**Easy**</font>
> Given a 32-bit unsigned integer `n`, reverse the bits of the binary representation of `n` and return the result.
### Example 1:
```java
Input: n = 00000000000000000000000000010101
Output: 2818572288 (10101000000000000000000000000000)
```
Explanation:
Reversing `00000000000000000000000000010101`, which represents the unsigned integer `21`, gives us `10101000000000000000000000000000` which represents the unsigned integer `2818572288`.
### Recommended complexity
* Time complexity: $O(1)$
* Space compleity: $O(1)$
### Solution
**(1) 題目都是限制 32-bits 的整數**
可觀察每個 bit 反轉前後的位置變化。以 8-bits 為例: 10110**0**10 $\Rightarrow$ 01**0**01101。第 2 bit 的數字反轉後會到第 5 = (8 - 1) - 2 bit。因此第 `i` bit 反轉後的位置為第 `(n - 1) - i` bit。
確認反轉後的位置後，該 bit 反轉後的數值大小 $= b \times 2^{31-i}$ 或 $b << (31-i)$，其中 $b = 1$ 或 $0$。只要從最低位開始逐位先反轉再累加即可。
> [!Tip]
> 可以選擇用次方計算或是位移計算，多數情況下 bitwise 的位移運算會比乘法來的快，因為位移運算對應到 assembly lamguage 只有一個指令，但乘法會牽涉到多行 assembly code
**(2)如何確定每個 bit 是 1 或 0**
可用類似前幾題找 1 的方法逐位檢查每個位置是 1 還是 0。
#### False ver.
```python=
# false
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for i in range(32):
mask = 1 << i
bit = mask & n # bit = 2^i not 1
res += (bit << (31 - i))
return res
```
**Output:**
```
Error
```
這個版本錯的地方在於 `mask = 00...010..0` 是一個第 `i` bit = 1 的數字，當 `mask` 跟 `n` 做 AND 運算時的確可以判斷第 `i` bit 是不是 `1`，但計算後的結果 `bit = 00..010..0` 以十進位來說卻是 $2^i$，最後就會變成 $2^i$ 再往左位移 $31 - i$ 位。
<img src="https://hackmd.io/_uploads/BkrQQ2bpkg.jpg" width=500>
正確做法應該是針對題目給定的數字 `n` 每次往右移動，讓最低位跟 `1` 做 AND 運算
<img src="https://hackmd.io/_uploads/Bki97n-Tye.jpg" width=500>
#### Correct ver.
```python=
# false
class Solution:
def reverseBits(self, n: int) -> int:
res = 0
for i in range(32):
bit = (n >> i) & 1 # bit = 1 or 0
res += (bit << (31 - i))
return res
```
## 5. Missing Number
<font color="#00ad5f">**Easy**</font>
> Given an array `nums` containing `n` integers in the range `[0, n]` without any duplicates, return the single number in the range that is missing from `nums`.
>
> **Follow-up**: Could you implement a solution using only `O(1)` extra space complexity and `O(n)` runtime complexity?
### Example 1:
```java
Input: nums = [1,2,3]
Output: 0
```
Explanation: Since there are 3 numbers, the range is [0,3]. The missing number is 0 since it does not appear in nums.
### Example 2:
```java
Input: nums = [0,2]
Output: 1
```
### Constraints
* `1 <= nums.length <= 1000`
### Recommended complexity
* Time complexity: $O(1)$
* Space complexity: $O(1)$
### Solution
**(1) Hash set**
要檢查某數字有沒有在陣列之中，可以使用 hash set 加快查找的動作($O(1)$)。將題目給定的 array 中的數字加入到 hash set 之中，再從 0 到 n 開始迭代，若某個數字 i 不在 hash set 中表示它是 missing number。
```python=
class Solution:
def missingNumber(self, nums: List[int]) -> int:
hashSet = set()
for n in nums:
hashSet.add(n)
n = len(nums)
for i in range(n + 1):
if i in hashSet:
continue
return i
```
**(2) XOR**
相同的兩數字做 XOR 的結果為 0。理想上 `nums` 中的數字跟 `0` 到 `n` 所組成的陣列 `[0, 1, ..., n]` 做 XOR 後應該要是 `0`，因為每個數字都是兩兩一組。
當 `nums` 少一個數字時該組數字無法湊成 0，所以最後結果 = miss number。
Step-by-step 如下:
* 把 0 到 n 依序做 XOR 疊加
* 上述結果繼續跟 `nums` 中的元素做 XOR
* 最後結果 = missing number
<img src="https://hackmd.io/_uploads/SkChrnWake.jpg" width=500>
```python=
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
res = 0
for i in range(n + 1):
res = res ^ i
for n in nums:
res = res ^ n
return res
```
## 6. Sum of Two Integers
<font color="#ffbb00">**Medium**</font>
> Given two integers `a` and `b`, return the sum of the two integers without using the `+` and `-` operators.
### Example 1:
```java
Input: a = 1, b = 1
Output: 2
```
### Example 2:
```java
Input: a = 4, b = 7
Output: 11
```
### Constraints
* `-1000 <= a, b <= 1000`
### Recommended complexity
* Time complexity: $O(1)$
* Space complexity: $O(1)$
### Solution
觀察 binary bit 等級的加法過程:
* 0 + 0 = 0
* 0 + 1 = 1
* 1 + 1 = 1**0**
與 XOR 的計算非常類似，但 1 + 1 時需要考慮進位的問題。進位可以透過 AND 運算輔助判斷，當同時出現 1 時表示需要進位，此時將 `1 & 1` 的結果左移一位表示進位動作。
每一次計算 `a ^ b` 與 `(a & b) << 1` 後把兩者相加，相加的過程就是繼續做 XOR 與 AND 直到 AND 的結果為 0 就是答案。
(因為 Python 的整數型態是任意精度沒有限制，所以此題以 C++ 進行)
```cpp=
class Solution {
public:
int getSum(int a, int b) {
while (b != 0){
int carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}
};
```
## 7. Reverse Integer
<font color="#ffbb00">**Medium**</font>
> You are given a signed 32-bit integer `x`.
>
> Return `x` after reversing each of its digits. After reversing, if `x` goes outside the signed 32-bit integer range `[-2^31, 2^31 - 1]`, then return `0` instead.
>
> Solve the problem without using integers that are outside the signed 32-bit integer range.
### Example 1:
```java
Input: x = 1234
Output: 4321
```
### Example 2:
```java
Input: x = -1234
Output: -4321
```
### Example 3:
```java
Input: x = 1234236467
Output: 0
```
### Constraints
* `-2^31 <= x <= 2^31 - 1`
### Recommended complexity
* Time complexity: $O(1)$
* Space complexity: $O(1)$
### Solution
可利用除法和取餘數把每一位數字找出來
因為題目限制在 32-bits 的整數，以 MAX = 2147483647 為例，不可先計算 `res` 的結果後再比較兩者大小，因為系統根本無法算出比 `MAX` 大的數字，因此聚焦在比較最後一位數以及倒數第二位數字。
```cpp=
class Solution {
public:
int reverse(int x) {
int MAX = 2147483647; // 2^31 - 1
int MIN = -2147483648; // -2^31
int remains;
int res = 0;
while (x != 0){
remains = x % 10;
x = x / 10;
if ((res > MAX / 10) ||
(res == MAX / 10 && remains > MAX % 10)){
return 0;
}
if ((res < MIN / 10) ||
(res == MIN / 10 && remains < MIN % 10)){
return 0;
}
res = res * 10 + remains;
}
return res;
}
};
```
Sign in with Wallet
Connect another wallet