前言
位运算是把数字用二进制表示之后，对每一位上 0 或 1 的运算。二进制及其位运算非常重要，在很多底层技术中频繁出现。那么面试题更不例外了。
位运算总共有 5 种运算，与、或、异或、左移和右移。关于与 (&)、或 (|)和异或 (\(\oplus\)) 的规律可总结为:
- 与：只要有 0就是 0，否则为 1；
- 或：只要有 1 就是 1，否则为 0；
- 异或：两个二进制位不同为 1，相同为 0。
左移运算符 m<
题目(二进制中1的个数)
题目：请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如把 9 表示成二进制 1001，有 2 位是 1 。因此，如果输入 9，则该函数输出 2。
算法思路
算法思路一
我们把输入的二进制数的最后一位与 1 进行位与运算，如果是 1，就计数；然后将二进制数右移一位，再进行同样的操作，直到整数为 0 退出循环。此思路只能针对输入的整数是正整数，否则会陷入死循环。
算法思路二
由于正数和负数的二进制数 n 移位规律不同，因此采用右移来计数较为麻烦。那现在我们就不移动输入整数的二进制表示，而是利用一个无符号的数 1，然后先和 n 的最低位相与，判断最低位是否为 1；然后接着把 1 左移一位，再和 n 做与运算，就能判断 n 的次低位是不是1，这样一直操作，直到循环 n 的二进制位数次。
算法思路三
我们发现将 n 减去 1 再和 n 位与可以去掉 n 中最右的 1，那么 n 中有几个这样的 1 ，就需要去掉几次。
注：把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的 1 变成 0。很多二进制的问题都可以用这种思路解决。
算法实现
算法实现一
算法实现二
算法实现三
复杂度分析
算法一的时间主要消耗在对二进制的移位上，时间复杂度为 O(logn)；算法二需要进行循环 n 次(输入的二进制有 n 位)，因此时间复杂度为 O(n);若输入数的二进制表示中 1 的个数为 n，那么算法三仅需循环 n 次，时间复杂度最好达到 O(1)，最坏达到 O(n)。另外空间复杂度均为 O(1)。
参考
<<剑指offer2>>
