参考链接：知识星球 、英雄算法联盟

位与运算符是一个二元的位运算符，也就是有两个操作数，表示为 x & y。

注意：这里的 前导零 可有可无，作者写上前导零只是为了对齐以及让读者更加清楚位与的运算方式。

前导零的概念通过一个例子解释： 例如，反转 2021 得到 1202 。反转 12300 得到 321 ，这里就不保留前导零 。

对任何一个数，通过将它和 0b1 进行位与，结果为零，则必然这个数的二进制末尾位为0，根据以上表就能得出它是偶数了；否则，就是奇数。

【例题1】给定一个数，求它的二进制表示的末五位，以十进制输出即可。

【例题3】给定一个 32 位整数，要求消除它的末五位。

还是根据位与的性质，消除末五位的含义，有两层：

那么，根据位运算的性质，我们需要数，它的高27位都为1，低五位都为 0，则这个数就是： ( 11111111111111111111111111100000 ) 2 (11111111111111111111111111100000)_2 (11111111111111111111111111100000)2​ 但是如果要这么写，代码不疯掉，人也会疯掉，所以一般我们把它转成十六进制，每四个二进制位可以转成一个十六进制数，所以得到十六进制数为 0xffffffe0。 代码实现如下：

提示： f 代表 4 个1； e 代表 3个1,1个0； 0 代表 4 个 0 ;

【例题4】给出一个整数，现在要求将这个整数转换成二进制以后，将末尾连续的1都变成0，输出改变后的数（以十进制输出即可）。

我们知道，这个数的二进制表示形式一定是： … 0 11 … 11 ⏟ k \dots 0 \underbrace{11\dots11}_{\text{k}} …0k 11…11​​ 如果，我们把这个二进制数加上1，得到的就是： … 1 00 … 00 ⏟ k \dots 1 \underbrace{00\dots00}_{\text{k}} …1k 00…00​​ 我们把这两个数进行位与运算，得到： … 0 00 … 00 ⏟ k \dots 0 \underbrace{00\dots00}_{\text{k}} …0k 00…00​​

【例题5】请用一句话，判断一个正数是不是2的幂。

如果一个数是 2 的幂，它的二进制表示必然为以下形式： … 1 00 … 00 ⏟ k \dots 1 \underbrace{00\dots00}_{\text{k}} …1k 00…00​​ 这个数的十进制值为 2 的 k 次。 那么我们将它减一，即 2 的 k 次 减一 的二进制表示如下（参考二进制减法的借位）： … 0 11 … 11 ⏟ k \dots 0 \underbrace{11\dots11}_{\text{k}} …0k 11…11​​ 于是 这两个数位与的结果为零，于是我们就知道了如果一个数 x 是 2 的幂，那么 x & (x-1) 必然为零。而其他情况则不然。所以本题的答案为： (x & (x-1)) == 0

右移运算符是一个二元的位运算符，也就是有两个操作数，表示为 x >> y。其中 x 和 y 均为整数。

x >> y 念作：“将 x 右移 y 位”，这里的位当然就是二进制位了，那么它表示的意思也就是：先将 x 用二进制表示，对于正数，右移 y 位；对于负数，右移 y 位后高位都补上 1。

举个例子：对于十进制数 87，它的二进制是 (1010111)， 左移 y 位的结果就是： ( 1010 ) 2 (1010)_2 (1010)2​

x >> y 的执行结果等价于： ⌊ x 2 y ⌋ \lfloor\frac{x}{2^y}\rfloor ⌊2yx​⌋ ⌊ ⌋ \lfloor\rfloor ⌊⌋这个符号代表取下整。如下代码：

输出结果为： 10 即： ( 1010 ) 2 (1010)_2 (1010)2​ 正好符合这个右移运算符的实际含义： 10 = ⌊ 87 2 3 ⌋ 10 = \lfloor\frac{87}{2^3}\rfloor 10=⌊2387​⌋

由于除法可能造成不能整除，所以才会有 取下整 这一步运算。

所谓负数右移，就是 x >> y 中，当 x 为负数的情况，代码如下：

它的输出如下： -1 同样满足式子： ⌊ x 2 y ⌋ \lfloor\frac{x}{2^y}\rfloor ⌊2yx​⌋ 这个可以用补码来解释，-1 的补码为：（补码的计算方法可参考：补码的计算 ） 11111111111111111111111111111111 11111111 11111111 11111111 11111111 11111111111111111111111111111111 右移一位后，由于是负数，高位补上 1，得到： 11111111111111111111111111111111 11111111 11111111 11111111 11111111 11111111111111111111111111111111

可以理解成 - (x >> y）和 (-x) >> y 是等价的。

刚才我们讨论了 x < 0 的情况，那么接下来，我们试下 y < 0 的情况会是如何？是否同样满足如下性质呢？ ⌊ x 2 y ⌋ \lfloor\frac{x}{2^y}\rfloor ⌊2yx​⌋ 如果还是满足，那么两个整数的左移就有可能产生小数了。 看个例子：

虽然能够正常运行，但是结果好像不是我们期望的，而且会报警告如下： [Warning] right shift count is negative [-Wshift-count-negative]

实际上，编辑器告诉我们尽量不用右移的时候用负数，但是它的执行结果不能算错误，起码例子里面对了。

右移负数位其实效果和左移对应正数数值位一致。

【例题2】给定一个数 x，去掉它的低 k 位以后进行输出。

这个问题，可以直接通过右移来完成，如下：x >> k。

【例题3】获取一个数 x 低位连续的 1 并且输出。

对于一个数 x，假设低位有连续 k 个 1。如下： ( … 0 11 … 11 ⏟ k ) 2 (\dots 0 \underbrace{11\dots11}_{\text{k}})_2 (…0k 11…11​​)2​ 然后我们将它加上 1 以后，得到的就是： ( … 1 00 … 00 ⏟ k ) 2 (\dots 1 \underbrace{00\dots00}_{\text{k}})_2 (…1k 00…00​​)2​ 这时候将这两个数异或结果为： ( 11 … 11 ⏟ k+1 ) 2 (\underbrace{11\dots11}_{\text{k+1}})_2 (k+1 11…11​​)2​ 这时候，再进行右移一位，就得到了 连续 k 个 1 的值，也正是我们所求。 所以可以用以下语句来求：(x ^ (x + 1)) >> 1。

【例题4】获取一个数 x 的第 k(0 k) & 1。

异或运算符是一个二元的位运算符，也就是有两个操作数，表示为 x ^ y。 异或运算会对操作数的每一位按照如下表格进行运算，对于每一位只有 0 或 1 两种情况，所以组合出来总共 4 种情况。

通过这个表，我们得出一些结论：

1）两个相同的十进制数异或的结果一定为零。

2）任何一个数和 0 的异或结果一定是它本身。

3）异或运算满足结合律和交换律。

(1) 在C语言中，以 0b 作为前缀，表示这是一个二进制数。那么 a 的实际值就是 (1010) 。

(2) 同样的， b 的实际值就是 (0110) ；

(3) 那么这里 a ^ b 就是对 (1010) 和 (0110) 的每一位做表格中的 ^ 运算。

所以最后输出结果为：

12 因为输出的是十进制数，它的二进制表示为： (1100) 。

【例题1】给定一个数，将它的低位数起的第 4 位取反，0 变 1，1 变 0。

这个问题，我们很容易联想到异或。我们分析一下题目意思，如果第 4 位为 1，则让它异或上 0b1000 就能变成 0；如果第 4 位 为 0，则让它异或上 0b1000 就能变成 1，也就是无论如何都是异或上 0b1000 ，代码如下：

【例题2】给定两个数 a 和 b，用异或运算交换它们的值。

我们直接来看 (1) 和 (2) 这两句话，相当于 b 等于 a ^ b ^ b ，根据异或的几个性质，我们知道，这时候的 b 的值已经变成原先 a 的值了。

而再来看第 (3) 句话，相当于 a 等于 a ^ b ^ a，还是根据异或的几个性质，这时候，a 的值已经变成了原先 b 的值。

从而实现了变量 a 和 b 的交换。

【例题3】输入 n 个数，其中只有一个数出现了奇数次，其它所有数都出现了偶数次。求这个出现了奇数次的数。

根据异或的性质，两个一样的数异或结果为零。也就是所有出现偶数次的数异或都为零，那么把这 n 个数都异或一下，得到的数就一定是一个出现奇数次的数了。

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。 leetcode 461. C语言版本：

python版本：