逐位计算1个数

• 有两种思路，一种右移n，每次与1进行与运算；另一种是左移1，每次与n进行与运算，由于n为负数时右移会填充1，所以选择左移1的思路

  public class Solution {
    public int NumberOf1(int n) {
        int ans = 0;
        int mark = 1;
        while(mark != 0) {
            // 判断某位是否为1
            if((mark & n) != 0) {
                ans++;
            }
            // 左移一位
            mark <<= 1;
        }
        return ans;
    }
  }

逐步消1，计算次数

• 对于任意一个正整数n，n&(n-1)由于(n-1)向最低1位借位的关系会消去最低1位，所以进行多少次n&(n-1)操作就是含多少个1
• 对于任意一个负整数n：

  有：n的补码 + -n的补码（正整数） = 0的补码（(溢出1)0...0）
  则：n的补码 = 0的补码（(溢出1)0...0） - -n的补码（正整数）
  则：n的补码 = 的原码（10...0） - -n的原码（正整数）
  则：n的补码 = ( + n)的原码（正整数）

以上，可以得知对负数n补码的处理就是对( + n)的原码（正整数）的处理，所以+1-1的操作可以直接作用于补码，即n&(n-1)也会由于(n-1)向最低1位借位的关系会消去最低1位，所以进行多少次n&(n-1)操作就是含多少个1

public class Solution {
    public int NumberOf1(int n) {
        int ans = 0;
        // 每次消去一个1
        while(n != 0) {
            n &= n - 1;
            ans++;
        }
        return ans;
    }
}