Bit Counting

计算一个二进制数里面有多少个 1

方法1：逐位与

unsigned int countBits(unsigned long long n){
  //your code here
  unsigned int cnt = 0;
  while(n){
    cnt += n & 1;
    n >>= 1;
  }
  return cnt;
}

self adding

动机是减少循环次数，可不可以只数 1，不管 0。 一个数减去 1 的话，它的最末一个 1，以及之后的所有 0，全部变反，前面的位不变。因此要消除最末一个 1，可以把一个数减一再与自己。这样一次消除一个 1，消除到 0 就停止循环。因此可以减少循环次数到 1 的个数。

unsigned int countBits(unsigned long long n){
  //your code here
  unsigned int cnt = 0;
  while(n){
    n = n & (n-1);
    cnt++;
  }
  return cnt;
}

https://www.dazhuanlan.com/2019-12-07