> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/wei-yun-suan/wei-yun-suan-zong-jie.md).

# 位运算总结

## 与运算

### 判断某一位是否为1

需要判断某个数字的第$$i^{th}$$位是否为1, 使用只有第$$i^{th}$$位为1的**掩码**, 与该数字相与, 如果结果不为0, 则该位置为1.

得到掩码的方法是将1左移$$i-1$$次.

相关题目:

* [\[191\]\[简单\] 位1的个数](/garnet/suan-fa/wei-yun-suan/191-wei-1-de-ge-shu.md)

### 将数字的最后一个1位反转为0

对于任意数字$$n$$, 将$$n$$与$$n-1$$相与, 就可以把数字$$n$$的最后一位变为0.

这种技巧常常使用在:

* 计算一个数字中**一比特数**的数量, 就不需要将所有的位遍历一边了. 只需要不断地将最低的1位置0, 并统计数字, 直到所有的1都被置零, 此时数字就等于0了, 停止
* 判断数字中是否只有1个1, 即该数字是否是2的幂

相关题目:

* [\[191\]\[简单\] 位1的个数](/garnet/suan-fa/wei-yun-suan/191-wei-1-de-ge-shu.md)
* [\[338\]\[中等\]\[动态规划\] 比特位计数](broken://pages/-Mb2BzPGiCkDWUNWPwJo)
* [\[461\]\[简单\] 汉明距离](/garnet/suan-fa/wei-yun-suan/461-han-ming-ju-li.md)
* [\[231\]\[简单\] 2的幂](broken://pages/-Mb2BzPD7bY6JEHtbYsz)

### 提取最低位的1

```
n & (-n)
```

-n是n的相反数, 负数在二进制中是按照补码规则在计算机中存储的, -n的二进制表示为n的二进制表示的每一位取反再加上1. 因此n中最低位的1取反为0, 这之前的位原来都是0, 取反之后都是1. 加上1之后, 这些位置都会进位变成0, 原来最低位的1又会变为1. 而更高位的数字都是反转的, 因此将n与它的相反数-n相与, 得到的就是n中最低位的1代表的数值.

* [\[231\]\[简单\] 2的幂](broken://pages/-Mb2BzPD7bY6JEHtbYsz)

## 异或运算

* **异或运算满足结合律**.
* 相同的数字进行异或, 得到的结果为0; 相同的三个数字进行异或, 得到的原来的数字
  * 题目: [\[268\]\[简单\] 缺失数字](/garnet/suan-fa/wei-yun-suan/268-que-shi-shu-zi.md)

## 求和

### 两数求和

对于两个数字`a`和`b`, 有:

* `a^b`: 每位的异或运算, 得到的结果为**无进位相加的结果**
* `a&b`左移一位: 每位的与运算, 得到的结果为**进位结果**

因此将这`a^b`与`a&b`**左移一位**相加, 得到的仍然是`a+b`. 左移一位的目的是实现进位.

参考:

* [\[67\]\[简单\] 二进制求和](broken://pages/-Mb2BzP9U96Xih_e4bN-)
* [\[剑指Offer-65\]\[简单\] 不用加减乘除做加法](/garnet/suan-fa/wei-yun-suan/jian-zhi-offer65-bu-yong-jia-jian-cheng-chu-zuo-jia-fa.md)

## 找数组中的异常数字

在反复出现数字组成的数组中, 找到其中异常的数字, 即独立出现, 或出现次数异常的数字.

* [\[136\]\[简单\] 只出现一次的数字](/garnet/suan-fa/wei-yun-suan/136-zhi-chu-xian-yi-ci-de-shu-zi.md)
* [\[137\]\[中等\] 只出现一次的数字 II](/garnet/suan-fa/wei-yun-suan/137-zhi-chu-xian-yi-ci-de-shu-zi-ii.md)
* [\[260\]\[中等\] 只出现一次的数字 III](/garnet/suan-fa/wei-yun-suan/260-zhi-chu-xian-yi-ci-de-shu-zi-iii.md)

## 数字关系

### 整除

无论奇偶数, 将其二进制表示左移一位, 等价于将其二进制表示的最低位去掉, 这个数字也可以由整除得到$$\lfloor \frac{x}{2} \rfloor$$

### 奇偶

* 奇数的最后一位为1, 偶数的最后一位为0, 因此判断一个数是否是奇偶数, 可以将其于1相与, 为1则为奇数
* 奇数中的**一比特数**, 可以由它紧邻的之前的偶数中**一比特数**再加1得到
* 偶数中的**一比特数**, 就是它的一半$$\frac{x}{2}$$对应的**一比特数**, 因为将$$\frac{x}{2}$$右移相当于乘以二

## Python中的位运算

Python中低位在右, 高位在左, 因此将一个数向右移一位是在求整除2的结果, 左移一位是在将这个数字乘以2.

```
a = 0011 1100 = 60

b = 0000 1101 = 13
```

Python中支持的位运算符如下:

| 运算符 | 描述                                                      |
| --- | ------------------------------------------------------- |
| &   | 按位与运算符                                                  |
| \|  | 按位或运算符                                                  |
| ^   | 按位异或运算符                                                 |
| \~  | 按位取反运算符, \~x 类似于 -x-1                                   |
| <<  | 左移动运算符, 运算数的各二进位全部左移若干位, 由 << 右边的数字指定了移动的位数, 高位丢弃, 低位补0 |
| >>  | 右移动运算符, 把 >> 左边的运算数的各二进位全部右移若干位, >> 右边的数字指定了移动的位数       |