Bit Mainpulatoin

Binary Number with Alternating Bits

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

• 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

• 这题关键在于是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.

• For each byte, we can use cache to improve performance.

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

• 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

• 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

• 有两个数只出现一次，其余都出现2次

• 1 5 2 2 3 3 4 4

• if XOR all nums. the res should be a^b, res != 0

• 二进制的某一位是1

• 意味着a和b在某一位上是不一样的

• diff &= -diff;//get the right most "1" bit

• 把所有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;
    // }
}