1.27 剑指offer 二进制中1的个数

位运算

在c 中左移也就是所说的逻辑移位，右端补0，而右移是算数移位，左端补齐的是最高位的符号位。
故负数左移，有可能变成正数，但负数右移，肯定还是负数。

• 正数左移一位等价于乘以2
• 负数左移一位不确定，因为符号位移出，可能变成正数，无等价运算
• 正负数右移一位等价于除以2

补码

在计算机中，数值是按字节、按补码的形式存储，按位运算的。

数值用二进制原码表示时，最高位为符号位，正数为0、负数为1，位数不够用0补全。

如：9 和 -9 的原码分别为 0000 1001 和 1000 1001 。

用原码存储数值时，关于 0 和 -0 存在两种表示，分别为： 0000 0000 和 1000 0000 。

同一个数值，存在两种表示方法当然有问题，用补码便可解决。

关于补码，正数的补码同原码，负数的补码将原码的符号位不变、其余位取反、再加1。数值补码进行运算时，符号位参与运算。

如：9 和 -9 的补码分别为： 0000 1001 和 1111 0111 。而0 和 -0 的补码均为： 0000 0000 。

补码运算可化减法为加法，方便运算。如： 9 - 9 = 9 + （-9），即（0000 1001） + （1111 0111） = 0000 0000 。

补码变回原码，依然是正数的原码同补码，负数的补码转原码需符号位不变、其余位取反、再加1，符号位参与运算。

题目

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

思路

找规律发现，把一个整数减去1，再和原始整数做与运算，会把该整数最右边的1变成0。
在 Python 程序中，当对一个负整数与其减 1 后的值按位求与，若结果为 0 退出，循环执行此过程。由于整型数可以有无限的数值精度，其结果永远不会是 0，在 Python 中，整型数是没有溢出的（overflow）。

在python中，负数和0xffffffff按位与之后变成一个无符号数，可减为0。

代码

    def NumberOf1(self, n):
        count = 0
        if n < 0:
            n = n & 0xffffffff
        while n:
            count += 1
            n = (n-1) & n
        return count