1.题目

1.题目

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

1.1题解

利用一个结论：一个二进制数n减1后与原二进制数进行&运算( 即n&(n-1) )会消去最右边的1。

• 假设二进制数101进行减1运算，刚好最右边是1，则得到100，此时用100跟101做&运算，得到的是100，故消去了101左右边的1。
• 100减1呢？最低位是0,跟十进制减法一样啊，向高位借。(可以脑补一下十进制100减1的过程)

所以二进制100减1的运算过程如下：

• 最右边的0向右数第二位借1得：2-1=1，
• 右数第二位还是0，却要借给最右边那位1，所以它也得向高位借。
• 这样右数第三位的1借给它1之后变成0，右数第二位借1得：2-1=1。
• 所以得到新数为011。

1.2 核心知识

• &是二进制“与”运算，参加运算的两个数的二进制按位进行运算，运算的规律是：

• 0 & 0=0
  0 & 1=0
  1 & 0=0
  1 & 1=1

• | 运算

  0 | 0 = 0
  0 | 1 = 1
  1 | 0 = 1
  1 | 1 = 1

• 异或(^)运算

  0 ^ 0 = 0
  0 | 1 = 1
  1 ^ 0 = 1
  1 ^ 1 = 0

• 对于参加运算的数要换算为二进制进行运算，例如3 & 2的结果是2，过程如下：

  3 & 2
  =0111 & 0010
  =0010
  =2

1.3答案

public class Solution {
    public int NumberOf1(int n) {
        int num = 0;
        while (n != 0) {
            num++;
            n = n & (n - 1);
        }
        return num;
    }
}