leetcode338. counting bits

• method 1
  

  Bit operator

• <<, >>

  • x << y : shift bits in the literal left by 3
    • 3 = 0011, 3 << 2 = 0110 = 6, 3 << 3 = 1000
  • x >> y: shift bits in the literal x right by y
    • 12 = 1100, 12 >> 3 = 0001

• ^

  • 0 ^ arbitrary number = arbitrary number
  • 1 ^ 0 = 1 1 ^ 1 = 0 usually used to calculate the number of 1 in a number

calculate every number in the range

1
2
3
4
5
6
7
8
9
10
11

int calculate(int n){
    int count = 0;
    for(int i = 0; i < 32; i++){
        int origin = n;
        int comp = origin ^ 1; 
        if(origin > comp)
            count++;
        n >>= 1; // shift a bit in the literal n right by 1
    }
    return count;
}

• method 2-dp
  find the pattern 🙂