leetcode338. counting bits

338. 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 🙂