编程技巧：“高端”的位运算
大家好，我是王有志。关注王有志，回复DSA获取数据结构和算法学习资源。
原计划迭代作为预备知识的收尾，不过在解2的幂[1]和4的幂[2]时，想到关于数字2的问题可以通过位运算去解决，因此补充了关于位运算的内容。
“征服”面试官
当我还在校园的时候，听到过一个故事：某位学长去面试腾讯时，要求优化冒泡排序[3]，学长“苦思冥想”后使用位运算交换变量，成功“征服”面试官拿下Offer。
故事我们可以当做段子来看，不过提到的位运算交换变量却值得我们去探究。
先来看下“普通”程序员是如何交换变量的：
int a = 3, b = 5;
int temp = a;
a = b;
b = temp;
那么“高端”程序员是如何使用位运算交换变量的呢？
int a = 3, b = 5;
a = a ^ b;
b = a ^ b;
a = a ^ b;
同样是4行代码，使用位运算无需引入临时变量，因此在空间复杂度上更优，并且位运算更靠近计算机，因此在运算效率上更有优势。
位运算
计算机中，数以二进制的形式存储在内存中，而位运算[4]就是对内存中的二进制数进行操作。
维基百科中是这样定义的：
“位操作是程序设计中对位数组或二进制数的一元和二元操作。在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。在现代架构中，位运算的运算速度通常与加法运算相同（仍然快于乘法运算），但是通常功耗较小，因为资源使用减少。
既然位运算是操作二进制数的，那么我们有必要先了解计算机中二进制数是如何表示的。
原码，反码和补码
计算机中有3种有符号数的表示方法：原码[5]，反码[6]和补码[7]。
原码，反码和补码的共同点是：最高位为符号位，0代表正数，1代表负数。但它们在数值位上有着不同的表示方法。
我们通过十进制数字-11，来展示这3种表示方法的二进制数（使用8位）。
原码表示
使用原码表示时，除了符号位外，数值位和我们通过“除二倒取余法[8]”计算后的数字相同，-11的原码为：1000 1011。
反码表示
反码是原码和补码之间转换的过渡码，原码转换为反码的规则为：
正数时，反码和原码相同； 负数时，符号位保持不变，数值位时原码按位取反。
因此，-11的反码表示为：1111 0100。
补码表示
通过反码，我们可以计算出数字的补码，转换规则为：
正数时，补码和反码相同； 负数时，符号位保持不变，数值位时反码数值位加1。
因此，-11的补码表示为：1111 0101。
补码是计算机系统中普遍使用的表示方式，补码相较于原码和反码有两个特点：
符号位可以参与运算； 加法和减法可以统一处理。
到此为止，我们已经了解了计算机中3种二进制数的表示方式，下面简单的做个总结：当数字为正数时，原码，反码和补码相同。
当数字为负数时，原码，反码和补码遵循以下转换规则：
位运算符
Java中提供了7种位运算操作符：
| 符号 | 描述 | 运算规则 | 优先级 | 示例 |
|---|---|---|---|---|
| ~ | 取反 | 操作一个数，0变为1，1变为0 | 1 | ~ a |
| << | 带符号左移 | 操作两个数，数值位向左移动，高位丢弃，低位补0 | 2 | a << 1 |
| >> | 带符号右移 | 操作两个数，数值位向右移动，低位丢弃，高位补符号位 | 2 | a >> 1 |
| >>> | 无符号右移 | 操作两个数，数值位向右移动，低位丢弃，高位补0 | 2 | a >>> 1 |
| & | 按位与 | 操作两个数，同为1时，结果为1，否则为0 | 3 | a & b |
| ^ | 按位异或 | 操作两个数，相同为0，不同为1 | 4 | a ^ b |
| | | 按位或 | 操作两个数，同为0时，结果为0，否则为1 | 5 | a | b |
用一段程序来展示位运算符的基础操作：
int number = -11;
// 输出Java中的二进制表示(补码),11111111111111111111111111110101
System.out.println("原值，二进制：" + Integer.toBinaryString(number));
// 取反，0变为1，1变为0
System.out.println("取反，十进制" + ~number);
System.out.println("取反，二进制：" + Integer.toBinaryString(~number));
// 按位异或，相同为0，不同为1
System.out.println("按位异或" + (number ^ number));
// 按位与，同为1时，结果为1，否则为0
System.out.println("按位与：" + (number & 1));
// 按位或，同为0时，结果为0，否则为1
System.out.println("按位或：" + (number | ~number));
// 左移，数值位向左移动，高位丢弃，低位补0
System.out.println("左移，十进制：" + (number << 1));
System.out.println("左移，二进制：" + Integer.toBinaryString(number << 1));
// 右移，数值位向右移动，低位丢弃，高位补符号位
System.out.println("右移，十进制：" + (number >> 2));
System.out.println("右移，二进制：" + Integer.toBinaryString(number >> 2));
// 无符号右移，数值位向右移动，低位丢弃，高位补0
System.out.println("无符号右移，十进制：" + (number >>> 1));
System.out.println("无符号右移，二进制：" + Integer.toBinaryString(number >>> 1));
位运算技巧
到目前为止，我们已经了解了二进制数和位运算符，不过这些操作看起平平无奇，好像并没有什么用？那么接下来就介绍一些基础的位运算技巧。
2的幂
还记得2的幂吗？当时使用递归求解，效率上还是有些差强人意的，那么有没有更高效的方法呢？
有一个二进制数字：1101 0101。根据常规的二进制转换为十进制的方法，可以得到如下等式：
显而易见，如果是2的幂，二进制数字中有且仅有1个1。例如：1000 0000。那么判断是否为2的幂就变成了证明二进制数字仅有1个1，或者说是，证明二进制数字中1后面所有位都为0。
如果数字n 是2的幂，那么n-1 一定是比n少一位，且二进制位都为1的数字。可以利用的特性判断是否符合我们的预期，代码如下：
if((n & (n - 1)) == 0) {
return true;
} else {
return false;
}
奇偶性
此外，在二进制转换为十进制的过程中，还可以得到另外一点信息，即如果二进制的最低位为1，则数字为奇数。
那么在判断一个数字的奇偶性时，我们只需要得知二进制数字的最后一位是否为1即可，代码如下：
if ((number & 1) == 0) {
System.out.println("偶数");
} else {
System.out.println("奇数");
}
快速乘/除2
还是在二进制转换为十进制的过程中，我们可以看到，如果想要乘/除2，只需要向左/右移动一位即可，不过对于奇数来说是除2后向下取整。
今天介绍的只是位运算中的基础技巧，算是为大家抛砖引玉。实际上位运算的技巧远不止这些，或者说是二进制数的使用技巧远不止这些。
离我们最近的有Java中ThreadPoolExecutor[9]处理线程状态时使用的技巧，或者叫做位掩码。另外，相信有的小伙伴在面试中被问到过布隆过滤器[10]，这也是一种二进制的进阶用法。
更多的技巧，也可以参考位运算的简单应用[11]和位运算的进阶介绍[12]。
结语
今天的内容到这里就结束了，我们来回顾下都聊了哪些内容：
首先是简单介绍了计算机中的原码，反码和补码，接着是Java中7种位运算操作符，不过并不是所有语言都提供了无符号右移（>>>），最后介绍了一些简单位运算的技巧，但位运算的用法远不止这些，包括听起来很高端的布隆过滤器，也使用了位运算，这也是为什么我说位运算“高端”。
最后补充一篇关于为什么要使用位运算的问答，虽然已经过去了11年，但依旧可以作为参考。What are the advantages of using bitwise operations?
练习
因为后面很少会再出现位运算的内容了，因此这次的题目会比较多。
简单难度：
67.二进制求和[13] 136.只出现一次的数字[14] 190.颠倒二进制位[15] 191.位1的个数[16] 231.2的幂[17] 342.4的幂[18] 693.交替位二进制数[19] 剑指 Offer 65.不用加减乘除做加法[20]
中等难度：
36.有效的数独[21] 89.格雷编码[22] 137.只出现一次的数字 II[23] 201.数字范围按位与[24]
本篇内容的代码仓库：Gitee代码仓库[25]
好了，今天就到这里了，Bye~~
链接
力扣-2的幂: https://leetcode-cn.com/problems/power-of-two
[2]力扣-4的幂: https://leetcode.cn/problems/power-of-four
[3]冒泡排序: https://gitee.com/wyz-A2/DSA/blob/master/Algorithm/src/main/java/com/wyz/sort/BubbleSort.java
[4]位运算: https://zh.wikipedia.org/wiki/%E4%BD%8D%E6%93%8D%E4%BD%9C
[5]原码: https://baike.baidu.com/item/%E5%8E%9F%E7%A0%81/1097586
[6]反码: https://baike.baidu.com/item/%E5%8F%8D%E7%A0%81
[7]补码: https://baike.baidu.com/item/%E8%A1%A5%E7%A0%81
[8]除二倒取余: http://xn--%3F%20-%207oj70d%20-%20%20https-k800c6xa9fna79rba68pczb83ixy0b0qml8b090d275h1v3au9g5w6flwwd8mlvgq2a701psa3967bzv1rdevc//www.zhihu.com/question/343550977/answer/808112570
[9]ThreadPoolExecutor源码: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/concurrent/ThreadPoolExecutor.java
[10]布隆过滤器: https://baike.baidu.com/item/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8/5384697
[11]位运算基础: https://baike.baidu.com/item/%E4%BD%8D%E8%BF%90%E7%AE%97/6888804?fr=aladdin#4
[12]位运算进阶: https://baike.baidu.com/item/%E4%BD%8D%E8%BF%90%E7%AE%97/6888804?fr=aladdin#7
[13]力扣-二进制求和: https://leetcode.cn/problems/add-binary/
[14]力扣-只出现依次的数字: https://leetcode.cn/problems/single-number/
[15]力扣-颠倒二进制位: https://leetcode.cn/problems/reverse-bits/
[16]力扣-位1的个数: https://leetcode.cn/problems/number-of-1-bits/
[17]力扣-2的幂: https://leetcode.cn/problems/power-of-two
[18]力扣-4的幂: https://leetcode.cn/problems/power-of-four
[19]力扣-交替二进制数: https://leetcode.cn/problems/binary-number-with-alternating-bits/
[20]力扣-不用加减乘除做加法: https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/
[21]力扣-有效的数独: https://leetcode.cn/problems/valid-sudoku/
[22]力扣-格雷编码: https://leetcode.cn/problems/gray-code/
[23]力扣-只出现依次的数字 II: https://leetcode.cn/problems/single-number-ii
[24]力扣-数字范围按位与: https://leetcode.cn/problems/bitwise-and-of-numbers-range
[25]Gitee代码仓库: https://gitee.com/wyz-A2/DSA