# Leetcode刷題學習筆記--Bit Manipulation
## Code Snippet
1. 把left most的1切換成0

val = val & (val - 1);

2. 把left mode的1取出來

mask = val & -val;

## Problems
### [137. Single Number II(Medium)](https://leetcode.com/problems/single-number-ii/)
給你一個數列vector<int> nums，其中每個數都會出現3次，只有一個數出現一次。找出出現一次的數字。

> 1. 我一開始使用hash map來統計，雖然tc為$O(N)$，但是sc也是$O(N)$
> 2. 官方解答有數學解，即
$sum = 3(x_1+x_2+...+x_n) + k$
$sum = 3(setsum - k) + k$
$k = (3setsum - sum) / 2$
> 3. 另一種是看數字的bit，只要分別統計每個bit的個數，因為都出現3次，所以mod 3 == 0，如果不為0，表示這個bit是因為出現一次的數字。

int singleNumber(vector<int>& nums) {
    int ans{};
    for(int i = 0; i < 32; ++i) {
        int sum{};
        for(auto& n : nums)
            sum += (n >> i) & 1;
        sum %= 3;
        if(sum) ans |= 1 << i;
    }
    return ans;
}

### [260. Single Number III(Medium)](https://leetcode.com/problems/single-number-iii/)
給你一個數列nums，找出其中只有兩個沒重複的數字。例如：[1,2,1,3,2,5]，答案是[3, 5]因為只有這兩個只有重複一次。

解題思路：
> 1. 如果這題只有一個沒重複，那就是把全部XOR起來就可以得到答案。但現在是兩個沒重複的數字。所以全部XOR起來回得到兩個數字的XOR。例如上面的例子就是3^5。
> 2. **這邊的關鍵是XOR，如果XOR為1的bit即為不相同的bit。**
> 3. 3(11b)^5(101b) = 110b，意味3和5中第二和第三個bit不相同。
> 4. **mask = diff & -diff; 取出最後一個不相同的bit**。
> 5. 所以我可以使用這個當成mask把數字分成兩邊，分成兩邊後，每一邊的數列只會有一個不重複的數字，就可以使用XOR把不重複的數字找出來。

vector<int> singleNumber(vector<int>& nums) {
    auto n = nums.size();
    if(n == 2) return nums;
        
    unsigned long diff = accumulate(nums.begin(), nums.end(), 0, bit_xor());
        
    int mask = diff & -diff;   // get the last difference bit
    
    vector<int> rtn{0, 0};
    for(auto& n : nums) {
        if(n & mask)
            rtn[0] ^= n;
        else
            rtn[1] ^= n;
    }
        
    return rtn;
}

這邊有幾個關鍵：
:::warning
1. nums的size從2開始，因為只有兩個不重複數字，所以size==2可以直接return。
2. diff須告為unsigned long，因為diff宣告為unsigned int且為整數最大值的時候，-diff會超出可以表示的範圍，
:::

### 287. [Find the Duplicate Number[Medium]](https://leetcode.com/problems/find-the-duplicate-number/)

同樣題目使用fast slow pointer的解法請參考[連結](/jO2mrGfpSiyZ_WlZIG7Aeg#287-Find-the-Duplicate-NumberMedium)。
這邊是參考這個[部落格](https://www.cnblogs.com/grandyang/p/4843654.html)。這個解法非常漂亮，值得學習。

解題思路:
> 1. 題目說有N+1個數，全部都在[1, N]的範圍裏面。
> 2. 重複的數字會出現兩次或多次。其他數字只會一次。
> 3. 假設重複的數字出現兩次，也就是其他數字[1, N]都會出現一次。=> 統計[1, N]的數字每個bit有幾個bit 1。=> cnt1。
> 4. 計算所有nums相同bit位置的1有幾個。=> cnt2。
> 5. 如果cnt2 > cnt2表示重複的數字在這個位置上的bit為1。
> 6. 如果重複的數字出現兩次以上，cnt2會比出現兩次還大，所以還是成立。


int findDuplicate(vector<int>& nums) {
    int res = 0, n = nums.size();
    for (int i = 0; i < 32; ++i) {
        int bit = (1 << i), cnt1 = 0, cnt2 = 0;
        for (int k = 0; k < n; ++k) {
            if ((k & bit) > 0) ++cnt1;
            if ((nums[k] & bit) > 0) ++cnt2;
        }
        if (cnt2 > cnt1) res += bit;
    }
    return res;
}

### [201. Bitwise AND of Numbers Range(Medium)](https://leetcode.com/problems/bitwise-and-of-numbers-range/)
給你一個範圍的整數[left, right]，求出這個範圍裏面所有整數的AND。

> 1. 把這個範圍內所有的數字都AND，如果有一個0就一定為0，所以等於是求範圍內，==左邊都一樣的部分==。


int rangeBitwiseAnd(int left, int right) {
    int i{0};
    while(left != right) {
        left >>= 1;
        right >>= 1;
        i++;
    }
        
    return left << i;
}

2022/12/6
> 1. 另一個找出common prefix的方法是，逐步把right的leftmost關掉，直到right <= left。
> 2. 因為 right & right - 1 就是把left most的1變成0，如果比left還小表示找到了common prefix。

int rangeBitwiseAnd(int left, int right) {
    while(right > left) {
        right &= right - 1;
    }
    return left & right;
}

###### tags: `leetcode` `刷題`