# Bit Mainpulatoin

[Binary Number with Alternating Bits](https://leetcode.com/problems/binary-number-with-alternating-bits/description/)

Reverse Bits

* Setting a bit `num |= 1 << x;`
* clearing a bit `num &= ~(1<<x)`
* toggling(flipping) a bit `num ^= 1 << x`
* checking a bit `bit = (num >> x) & 1`
* **1 << i  就是Math.pow(2, i)**
* **`n & (-n)`get the least significant standing bit,就是找最右边的1所代表的数，比如n = 6(110), n & (-n) = 2(10)**
* **`n & (n - 1)` 效果为减去 n 的二进制表示中最右边为 1 的 bit,等效为`n - n & (-n)`,n =6, n &(n-1) = 4**
* **`n &(n - 1) == 0`的话就说明n is power of 2**
* **`n + (n & -n)` 就是直接在最低位的 1 上做进位加法**
* **如果是Unsigned Bit, 判断终止条件不能写`n > 0`,而应该是`N != 0`，**[**参见Number of 1 Bits**](https://leetcode.com/problems/number-of-1-bits/)
* a^0 = a
* a^a = 0
* 0b001100 ^0b101010 = 0b100110
* **所以可以in place swap(a, b)**

  ```
  a ^= b;
  b ^= a;
  a ^= b;
  ```
* Reverse Bits
* Counting Bits

## [Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/)

* 这题关键在于是Unsigned Bit,所以在while loop里的条件不能写n > 0,而应该是N != 0
* Naive的想法就是找这32 bits里有多少个1,可以用`1 << i`的技巧，这个方法有个好处就是可以算上最高位的1，不用care是否是Unsigned Bit

  ```
  // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt = 0;
        //naive way using bit shift
        for(int i = 0; i < 32; i++){
            if((n & (1 << i)) != 0){
                cnt++;
            }
        }
        return cnt;
    }
  ```
* 还有一种就是用n -= n & (-n)的方法，或者n = n & (n - 1)。但是要注意是`while(n != 0)`

  ```
  // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int cnt = 0;
        //cannot be while(n > 0)
        while(n != 0){
            n-= n & (-n);
            cnt++;
        }
        return cnt;
    }
  ```

## Reverse Bits

* 拿到没做过的题目先想Brute Force,很多时候思路不见得不对
* 先shift bit,再赋值

```
// you need treat n as an unsigned value
    public int reverseBits(int n) {
        int reverse = 0;
        for(int i = 0; i < 32; i++){
            reverse = reverse << 1;//shift to the left bit
            if((n & 1 << i) != 0){
                reverse += 1;
            }
        }
        return reverse;
    }
```

* **FOLLOW UP: 如果多次call method如何优化？**
* We can divide an int into 4 bytes, and reverse each byte then combine into an int.&#x20;
* For each byte, we can use cache to improve performance.

## [Counting Bits](https://leetcode.com/problems/counting-bits/)

* 给一个数num,要求返回0 <= i <= num的所有i包含bit 1的个数
* 这题可以用Fenwick Tree的思路做
* 当前数为i（假设是1010）, 先找到i&(i - 1)的bit of 1的个数count\[i&(i - 1)],可以发现count\[i] = count\[i&(i - 1)] + 1
* 这个想法真的很巧妙

  ```
  public int[] countBits(int num) {
        int[] count = new int[num + 1];
        for(int i = 1; i <= num; i++){
            count[i] = count[i & (i - 1)] + 1;
        }
        return count;
    }
  ```

## [Flip Bit](https://www.lintcode.com/en/problem/flip-bits/)

* given two numbers A and B, check how many different bits
* 一开始想到的是把32位都循环一遍，然后check最后一位，如果两个数的最后一位不一样就cnt++

  ```
  public static int bitSwapRequired(int a, int b) {
        // write your code here
        int cnt = 0;
        for (int i = 0; i < 32; i++) {
            int first = a & 1;
            int second = b & 1;
            if (first != second) {
                cnt++;
            }
            a >>= 1;
            b >>= 1;
        }
        return cnt;
    }
  ```
* 上面这个方法虽然也过了，但显然没有get point
* 这题的核心其实是看C= A^B, get the number of bit 1 in C

```
public static int bitSwapRequired(int a, int b) {
        // write your code here
        int cnt = 0;
        for (int c = a ^ b; c != 0; c &= c - 1) {
            cnt++;
        }
        return cnt;
    }
```

## Single number

* 每个数出现两次except for one, find that single one
* XOR, a^a = 0

```
public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) res ^= num;
        return res;
    }
```

## [Single Numebr II](https://leetcode.com/problems/single-number-ii/)

* 3 \*n + 1个数，每个数出现3次except for one num,find it
* 把32 bits的每个bit位上求和sum, 如果sum % 3 != 0, 则说明res在此bit x上为 1

```
public int singleNumber(int[] nums) {
        //every int number can be seen as a 32-bit number
        //so we can count for each bit
        //if sum of each bit mod 3 != 0, it means this bit is one of bit of the single numebr
        if(nums == null || nums.length == 0) return -1;
        int res = 0;

        for(int i = 0; i< 32; i++) {
            int sum = 0;
            int x = 1 << i;
            for(int j = 0; j < nums.length; j++) {
               if((x & nums[j]) != 0) sum++;
            }
            if(sum % 3 != 0) res |= x;
        }
        return res;
    }
```

## [Single Number III](https://leetcode.com/problems/single-number-iii/)

* 有两个数只出现一次，其余都出现2次
* 1 5 2 2  3 3 4 4&#x20;
* if XOR all nums. the res should be a^b, res != 0
* 二进制的某一位是1
* 意味着a和b在某一位上是不一样的
* diff &= -diff;//get the right most "1" bit&#x20;
* 把所有num分成两拨，一拨是第k位为0，另一拨是第k位为1
* 然后各自一拨single number I

  ```
  if(nums == null | nums.length == 0) return null;
        int[] res = new int[2];
        int diff = 0;
        for(int num : nums) diff ^= num;
        diff &= -diff;//get the right most "1" bit , if diff = 6(110), diff &(-diff) = 2(010)
        for(int num : nums) {
            if((diff & num) == 0) {
                res[0] ^= num;
            }else res[1] ^= num;
        }
        return res;
  ```

## Hamming Distance

```
public int hammingDistance(int x, int y) {
        int cnt = 0;
        int xor = x ^ y;
        while (xor != 0) {
            if (xor % 2 == 1) {
                cnt++;
            }
            xor >>= 1;
        }
        return cnt;
    }
```

## Power of Two

* 利用n & (n-1) == 0性质

```
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0;
    }
```

## Power of Three

* 没法用bit manipulation

```
public boolean isPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n > 1) {
            if (n % 3 != 0) return false;
            n /= 3;
        }
        return n == 1;
    }
```

## Power of Four

* 这题naive solution就是check num %4 == 0, num /=4,   Time: O(logN)
* 还可以用bit manipulation, count bit i = i+2, num = 1 << i;   Time: O(32)

```
class Solution {
    /*
    1. naive %4 solution, O(LogN)
    2. count bit i = i+2, num = 1 << i; O(32)
    */

    public boolean isPowerOfFour(int num) {
        for (int i = 0; i < 32; i += 2) {
            if (num == 1 << i) return true;
        }
        return false;
    }
    
    // public boolean isPowerOfFour(int num) {
    //     if (num <= 0) return false;
    //     while (num > 1) {
    //         if (num % 4 != 0) return false;
    //         num /= 4;
    //     }
    //     return true;
    // }
}
```