剑指offer(java实现)二进制中1的个数

红太狼 2021-12-23 04:15 196阅读 0赞

题目描述：

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。比如输入9，9的二进制表示是1001，1的个数是2，所以输出2。

这有一个重要结论：一个数与该数减一的结果进行与运算，会把该数右边（低位）第一个1变为0，而该位左边保持不变（高位）。可以举一个简单的例子进行证明：比如1100（对应十进制是12），减去1之后的结果是1011（也就是十进制的11），两个数进行与运算之后，我们发现最后的结果是1000（对应十进制的8，当然这个8与后面没有关系，可以略过）。这样我们每进行一次的与运算就消去一个1，这样消到最后肯定是0了，所以我们可以在代码中以这个为循环的终止条件。

**注意：在计算机中，负数以其正值的补码形式表达。 负数源数据不管符号的正值称为原码，对其进行取反，取反后的数据称为反码。  
比如原来数据为-5，先不管其符号，将原数据正值（二进制）5为00000101，取反后的反码为11111010. … 11111010+1=11111011，此值即为-5的二进制表示。**

举例：15

1110  
1101  
\+1

1100  
1011  
\+1

1000  
0111  
\+1

public class Solution {//负数用补码表示，最高位为1
        public int NumberOf1(int n) {
            if (n == 0) {
                return 0;
            }
            int count = 0;
            while (n != 0) {//当n不为0时，其他任意整数的二进制至少有一个1
                n = n & (n-1);//n-1，如果n的二进制右边数第一位是1，则变为0，如果到某几位才为1时，如：0110 0100，则最右边的1变为0，
                //原先1的右边的00都变为1:0110 0011，然后与n相与;得到的值正好是：0110 0000:  -》 只会将最右边的1变为0
                count++;
            }
            return count;
        }
    }

相关题目：  
1、用一条语句判断一个整数是不是2的整数次方。

一个整数如果是2的整数次方，那么它的二进制表示有且只有一位是1，而其他所有位都是0。根据前面的分析，把这个整数减去1之后再和自己与，这个整数中唯一的1就会变成0；

2、输入两个整数m和n,计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制表示为1010，13的二进制为1101，需要改变1010中的3位才能得到1101。

我们可以求这两个数的异或，再统计异或结果中1的个数