位与模的对白
原创
位运算和模运算在日常的应用开发中倒也少见，主要是这两个概念更多是存在于新手教程中一笔带过，很多情况下都是说位运算主要是针对字节位来进行相关的处理，有或与非、异或和取模，这些概念我们也只是知道了一些相关的知识点，然后也就偶尔刷题的时候遇到了，不过这个概念对于系统、数值运算都是极友好的，此外还有的是在权限服务中有所应用，快不说，还稳。
定义
在位运算和模运算中，比较有点费解的就是位的相关概念，暂且先把概念过一遍，之后我们再理论联系实践。
我们知道在程序中的所有数在计算机内存中都是以二进制的形式储存的，而位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）
由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6 and 11没有什么实际意义啊。别急嘛，且听我们一层层推演🍵
原码反码和补码
正数的二进制即为原码，负数的二级制为正数的反码再补码，反码将二进制数按位取反(1变0,0变1)，补码对反码加1。比如说-5
原码：00000000 00000000 00000000 00000101
反码：11111111 11111111 11111111 11111010
补码：11111111 11111111 11111111 11111011下面两道题是对掩码意义的体会
- 191. 位1的个数，这个例题很有代表意义，很可以感受到掩码的意义。
- 面试题 05.01. 插入
左移 <<
按二进制形式把所有的数字向左移动对应的位数，高位移出(舍弃)，低位的空位补零。比如说： 3 << 2，则是将数字3左移2位
计算过程
3 << 2 首先把3转换为二进制数字
0000 0000 0000 0000 0000 0000 0000 0011然后把该数字高位(左侧)的两个零移出，其他的数字都朝左平移2位，最后在低位(右侧)的两个空位补零。则得到的最终结果是
0000 0000 0000 0000 0000 0000 0000 1100之后转换为十进制是12。
数学意义
如果是10进制向左移动一位，是不是就成了10倍，移两位乘100倍，所以在数字没有溢出的前提下，对于正数和负数，二进制左移左移n位就相当于乘以2的n次方。
右移 >>
按二进制形式把所有的数字向右移动对应的位数，低位移出(舍弃)，高位的空位补符号位，即正数补零，负数补1。
案例11 >> 2，则是将数字11右移2位
计算过程
11 的二进制形式为：
0000 0000 0000 0000 0000 0000 0000 1011然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。则得到的最终结果是
0000 0000 0000 0000 0000 0000 0000 0010转换为十进制是2
数学意义
右移一位相当于除2，右移n位相当于除以2的n次方(取整)。
应用
这个操作最常见的应用就是在二分法、折半等这些需要找到中间值的时候，而且不用担心被除数是奇数、商带小数、除数为0等异常情况，使用位移操作可以尽可能的避免这些异常的处理，减少系统的异常情况
或 |
通常用于二进制特定位上的无条件赋值，例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。
计算过程
第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1，那么结果的第n为也为1，否则为0
例如 5 | 3
5 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
3 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
计 算 结 果：0000 0000 0000 0000 0000 0000 0000 0111与 &
通常用于二进制取位操作，例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数。
计算过程
将2个操作数都转为二进制，第一个操作数的的第n位与第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0
案例 5 & 3 = 1
5 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
3 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
计 算 结 果：0000 0000 0000 0000 0000 0000 0000 0001非 ~
把内存中的0和1全部取反。使用not运算时要格外小心，你需要注意整数类型有没有符号。如果not的对象是无符号整数（不能表示负数），那么得到的值就是它与该类型上界的差，因为无符号类型的数是用$0000到$FFFF依次表示的。
计算过程
操作数的第n位为1，那么结果的第n位为0，反之为1。
案例 ~5
5 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
计 算 结 果：1111 1111 1111 1111 1111 1111 1111 1010
异或 ^
通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。
特点
xor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a xor b) xor b = a。xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19951223作为密钥。1314520 xor 19951223 = 19161263，我就把19161263告诉MM。MM再次计算19161263 xor 19951223的值，得到1314520，于是她就明白了我的企图。
将上述的原理翻译一下就是这个公式：如果a ^ b = c，那么a ^ c = b
- 异或后得到的结果与排列顺序无关 a ^ b = c 那么 b ^ a = c
- 0 与任何数异或的结果都是该数 0 ^ a = a
- 如果一个数异或自己偶数次, 结果为0
- a ^ a = 0
- a ^ a ^ a = a
- a ^ a ^ a ^ a = 0
计算过程
第一个操作数的的第n位于第二个操作数的第n位 相反，那么结果的第n为也为1，否则为0
案例 5 ^ 3
如题目1734. 解码异或后的排列，正向思考，逆向解
5 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
3 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
计 算 结 果：0000 0000 0000 0000 0000 0000 0000 0110应用
有的应用在于题海战术的套路，有的应用在于生产环境上的实践，这些都是在一次次的提高我们对于位计算的认知。
理论应用
前面说道在位计算中的几个特性，将这些特性组合起来的效果，可以分为几点：
- 求值
- 取权重
n & 1位运算等价于n%2取余运算
其实本质上也是求除以2之后的余数，事实上这个操作可以得到n的二进制表示的最低位
- 例如当
n = 3时，n的二进制表示为11，x & 1的值为 1； - 例如当
n = 6时，n的二进制表示为110，x & 1的值为 0。
获取二进制中最右边的 1：n & (-n)
这个方式主要是用于统计一个整数值的二进制数存在多少个1还是多少个0
在leetcode上面的代表性例题，列举的题目都是比较简单的，主要是体验手感
将二进制中最右边的 1 设置为 0：n & (n - 1)
在二进制表示中，数字n 中最低位的1 总是对应n - 1中的0 。因此，将n和n - 1与运算总是能把 n中最低位的1变成0，并保持其他位不变。正如例题：1342. 将数字变成 0 的操作次数，题目的解答的过程就是应用了这个原理。
这个算法也是有名字的叫做Brian Kernighan 算法，它用于清除二进制串中最右边的 1。这个算法的关键在于我们每次对 number 和 number−1 之间进行按位与运算后，number 中最右边的 1 会被抹去变成 0。
处理负数
这个可以用总结的模板套路，不妨尝试这道题371. 两整数之和，使用使用模板，因为在计算加法的时候，第一步都是要先处理符号问题，以及在最后一步再次处理符号问题
a &= 0xFFFFFFFF
b &= 0xFFFFFFFF
while b:
carry = a & b
a ^= b
b = ((carry) << 1) & 0xFFFFFFFF
return a if a < 0x80000000 else ~(a^0xFFFFFFFF)判断n的第k位的值
- 对于十进制整数 n，我们可以用
n & (1 << k)来判断 n 二进制表示的第 k 位（最低位为第 0 位）是否为 1。如果该表达式的值大于零，那么第 k 位为 1：- 例如当 n = 3 时，x 的二进制表示为 1，
n & (1 << 1) = 11 & 10 = 10 > 0，说明第 1 位为 1； - 例如当 n = 5 时，x 的二进制表示为 101，
n & (1 << 1) = 101 & 10 = 0，说明第 1 位不为 1。
- 例如当 n = 3 时，x 的二进制表示为 1，
- 对于十进制整数 n，我们可以用
(n >> k) & 1得到 n 二进制表示的第 k 位（最低位为第 0 位）。如果 n 二进制表示的位数小于 k，那么该表达式的值为零：- 例如当
n = 3时，n 的二进制表示为 11，(n >> 1) & 1 = 1 & 1 = 1，说明第 1 位为 1； - 例如当
n = 5时，n 的二进制表示为 101，(n >> 1) & 1 = 10 & 1 = 0，说明第 1 位为 0。 - 例如当
n = 6时，n 的二进制表示为 110，(n >> 3) & 1 = 0 & 1 = 0，说明第 3 位为 0。
- 例如当
- 不妨尝试一下这道题1318. 或运算的最小翻转次数
集合
一个数的二进制表示可以看作是一个集合（0 表示不在集合中，1 表示在集合中）。比如集合 {1, 3, 4, 8} ，可以表示成 (100011010)2 。而对应的位运算也就可以看作是对集合进行的操作。
操作 | 集合表示 | 位运算语句 | |
|---|---|---|---|
交集 | a∩b | a & b | |
并集 | a∪b | a | b |
补集 | a¯ | ~a （全集为二进制都是 1） | |
差集 | a∖b | a & (~b) | |
对称差 | a△b | a ^ b |
数值应用
类似乘法和除法的计算方式大都可以通过左移或者是右移的方式来，不过对于加减法就不一定了，在范围内确实可以直接加减，不过，大多数情况下还需要考虑溢出的现象。
加法运算
对于每个位相加可以使用异或，因为 0 + 1 = 1，1 + 1 =10，0 + 0 = 0，因为相同位如果同为 0 或 1相加对应位其实都变成 0，唯一的区别是有无进位而已。
所以我们要记录下每次相加会产生的进位，我们注意到其实只有相同位均为 1 的时候下一位相加才会产生进位，所以我们可以使用与，然后左移一位用到下一位的计算上去。
def add(a, b) -> int:
return a if (b == 0) else a^b + (a&b) << 1减法运算
减法其实就是加上这个数的相反数，这个数原来是用正数的补码表示的，现在变成负数的补码形式了:所以只需要将这个数每一位取反再末尾加一就行了
def subtraction(a, b) -> int:
b = ~b + 1
return a + b判断奇偶
a & 1 == 0 # 偶数
a & 1 == 1 # 奇数- 不用临时变量交换两个数，这个其实在python中倒是意义不大，不过在其他语言比如go、java这些倒也还有应用意义x ^= y; y ^= x; x ^= y;
列举组合
面试题 08.04. 幂集和78. 子集，这两道题应该都是一回事
生产应用
商品有多种状态，比如是否支持货到付款、是否虚拟商品、是否预售商品、是否图书商品、是否可开增票等，我们可以用五位的二进制来标识对应的状态，如10010，表示该商品是支持货到付款的图书商品
尾记
位与模在生产环境中应用少的另一个重要原因还是在于思维习惯的问题，我们习惯于十进制的计算，对于二进制的运行方式还是缺少训练，这个训练一来可以通过刷题，而来可以通过学习模拟电路中的门来进阶强化。
参考资料：
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。