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;
    // }
}
Previous头脑风暴NextCarry bit

Last updated

Was this helpful?