位运算 - 二进制中1的个数

位运算是把数字用二进制表示之后，对每一位上0或者1的运算。

位运算总共只有5种运算：与、或、异或、左移和右移。

与、或和异或运算的规律

image.png

左移运算符m<<n表示把m左移n位。在左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0。比如：

00001010<<2 = 00101000
10001010<<3 = 01010000

右移运算符m>>n表示把m右移n位。在右移n位的时候，最右边的n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值，则用0填补最左边的n位；如果数字是个有符号数值，则用数字的符号位填补最左边的n位。也就是说，如果数字原先是一个正数，则右移之后在最左边补n个0；如果数字原先是负数，则右移之后在最左边补n个1。下面是对两个8 位有符号数进行右移的例子：

00001010>>2 = 00000010
10001010>>3=11110001

二进制中1的个数

题目：请实现一个函数，输入一个整数，输出该数二进制表示中 1的个数。例如，把9表示成二进制是 1001，有2位是1。因此，如果输入9，则该函数输出 2。

把一个整数减去 1，都是把最右边的 1 变成 0。如果它的右边还有 0，则所有的 0 都变成 1，而它左边的所有位都保持不变。接下来我们把一个整数和它减去 1 的结果做位与运算，相当于把它最右边的 1 变成 0。以 1100 为例，它减去 1 的结果是 1011。再把 1100 和 1011 做位与运算，得到的结果是 1000。我们把 1100 最右边的 1 变成了 0，结果刚好就是 1000。

把一个整数减去 1，再和原整数做与运算，会把该整数最右边的 1 变成 0。那么一个整数的二进制表示中有多少个 1，就可以进行多少次这样的操作。

func numberOf1(_ n: inout Int) -> Int {
    var count = 0
    
    while (n != 0) {
        count += 1
        n = (n - 1)&n
    }
    
    return count
}

相关题目

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

• 输入两个整数m和n，计算需要改变 m 的二进制表示中的多少位才能得到 n。比如 10 的二进制表示为 1010，13 的二进制表示为 1101，需要改变 1010 中的3位才能得到 1101。我们可以分为两步解决这个问题：第一步求这两个数的异或；第二步统计异或结果中1的位数。

摘抄资料：《剑指offer》