# 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:

Input: nums = [3,2,3]

Output: 2

### Example 2:

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，所以最後計算的結果就是多餘不成對的數字。

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:

Input: n = 00000000000000000000000000010111

Output: 4

### Example 2:

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`

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:

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 設計一個定值。

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:

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.

# 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.

# 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:

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:

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。

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>

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:

Input: a = 1, b = 1

Output: 2

### Example 2:

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++ 進行)

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:

Input: x = 1234

Output: 4321

### Example 2:

Input: x = -1234

Output: -4321

### Example 3:

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` 大的數字，因此聚焦在比較最後一位數以及倒數第二位數字。


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;
    }
};