java 位运算详解
前言
在日常开发中位运算不会很常用到，如果能够巧妙的使用位运算可以大量减少运行开销，优化算法。博主在日常学习和开发中几乎没有用到过位运算，所以一直没想着学这个知识点，但是最近刷 leetcode 刷到了相关的题目，那就趁这个机会把位运算的相关知识点总结一下吧，如有错误还请批评指正。
一、位运算符
&：按位与
两个操作数对应位同为 1 时，结果为 1，其余全为 0。
（或者是只要有一个操作数为 0，结果就为 0）。
练习：
public class Test {
public static void main(String[] args) {
System.out.println(5 & 3);//结果为1
}
}
将 2 个操作数和结果都转换为二进制进行比较：
5 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
3 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
1 按位与运算后：0000 0000 0000 0000 0000 0000 0000 0001
|：按位或
两个操作数对应位同为 0 时，结果为 0，其余全为 1。
（或者是只要有一个操作数为 1，结果就为 1）。
练习：
public class Test {
public static void main(String[] args) {
System.out.println(5 | 3);//结果为7
}
}
5 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
3 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
7 按位或运算后：0000 0000 0000 0000 0000 0000 0000 0111
~：按位非
第 n 位为 1，那么按位非的结果是第 n 位变为 0，反之亦然。
练习：
public class Test {
public static void main(String[] args) {
System.out.println(~5);//结果为-6
}
}
5 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
-6 按位非运算后：1111 1111 1111 1111 1111 1111 1111 1010
补：有朋友对这里 - 6 怎么算的不太理解，我简单解释一下：
5 的 2 进制表示（假设只用 4 比特表示，最高比特为符号位）是 0101，0101 按位取反后是 1010。1010 是补码，取反（符号位不变）加 1 后就是原码。取反后是 1101，加 1 后是 1110（是 10 进制的 - 6），所以~ 5 等于 - 6。
^：按位异或
第一个操作数的第 n 位与第二个操作数的第 n 位不同，结果为 1，否则为 0。
练习：
public class Test {
public static void main(String[] args) {
System.out.println(5 ^ 3);//结果为6
}
}
5 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0101
3 转换为二进制：0000 0000 0000 0000 0000 0000 0000 0011
6 按位异或运算：0000 0000 0000 0000 0000 0000 0000 0110
<<：左位移运算符
符号位不变，低位补 0。移几位补几个 0。正数或者负数左移，低位都是用 0 补。
练习：
public class Test {
public static void main(String[] args) {
System.out.println(5<<2);//运行结果是20
}
}
0000 0000 0000 0000 0000 0000 0000 0101 左移 2 位，低位补 0：
0000 0000 0000 0000 0000 0000 0001 0100 换算成 10 进制为 20
>>：右位移运算符
如果值为正，则在高位补 0，如果值为负，则在高位补 1.
练习：
public class Test {
public static void main(String[] args) {
System.out.println(5>>2);//运行结果是1
}
}
0000 0000 0000 0000 0000 0000 0000 0101 右移 2 位，高位补 0
0000 0000 0000 0000 0000 0000 0000 0001
<<<：无符号右移运算符
无符号的意思是将符号位当作数字位看待。
即无论值的正负，都在高位补 0.
练习：
public class Test {
public static void main(String[] args) {
System.out.println(5>>>3);//结果是0
System.out.println(-5>>>3);//结果是536870911
}
}
5 换算成二进制： 0000 0000 0000 0000 0000 0000 0000 0101
-5 换算成二进制： 1111 1111 1111 1111 1111 1111 1111 1011
5 无符号右移 3 位后结果为 0，0 的二进制为： 0000 0000 0000 0000 0000 0000 0000 0000 // (用 0 进行补位)
-5 无符号右移 3 位后的结果 536870911 换算成二进制： 0001 1111 1111 1111 1111 1111 1111 1111 // (用 0 进行补位)
二、位运算符结合赋值操作
&= 按位与赋值
|= 按位或赋值
^= 按位非赋值
>>= 右移赋值
>>>= 无符号右移赋值
<⇐ 赋值左移
这些操作和 “+=” 一个概念
练习：
public class Test {
public static void main(String[] args) {
int a = 5;
a &= 3;
System.out.println(a);//结果是1
}
}
三、位运算符常见使用
（1） 公式：m*2^n = m << n
练习：
@Test
public void test() {
System.out.println("2^3=" + (1 << 3));//2^3=8
System.out.println("3*2^3=" + (3 << 3));//3*2^3=24
}
法则一：任何数左移（右移）32 的倍数位等于该数本身。
法则二：在位移运算 m<<n 的计算中，若 n 为正数，则实际移动的位数为 n%32，若 n 为负数，则实际移动的位数为 (32+n%32)，右移，同理。
左移是乘以 2 的幂，对应着右移则是除以 2 的幂。
（2）判断一个数 n 的奇偶性
n&1 == 1?” 奇数”:” 偶数”
为什么与 1 能判断奇偶？所谓的二进制就是满 2 进 1，那么好了，偶数的最低位肯定是 0（恰好满 2，对不对？），同理，奇数的最低位肯定是 1.int 类型的 1，前 31 位都是 0，无论是 1&0 还是 0&0 结果都是 0，那么有区别的就是 1 的最低位上的 1 了，若 n 的二进制最低位是 1（奇数）与上 1，结果为 1，反则结果为 0.
练习：
@Test
public void test() {
int n = 2;
int m = 3;
System.out.println((n & 1) == 1 ? "奇数" : "偶数"); //偶数
System.out.println((m & 1) == 1 ? "奇数" : "偶数"); //奇数
}
（3）不用临时变量交换两个数
这个知识点面试的时候有可能会被问到
在 int[] 数组转置的过程中，是不看到过这样的代码：
public static int[] reverse(int[] nums){
int i = 0;
int j = nums.length-1;
while(j>i){
nums[i]= nums[i]^nums[j];
nums[j] = nums[j]^nums[i];
nums[i] = nums[i]^nums[j];
j--;
i++;
}
return nums;
}
连续三次使用异或，并没有临时变量就完成了两个数字交换，怎么实现的呢？
解释：
public void test2() {
int n = 2;
int m = 3;
n = n ^ m;
m = m ^ n; //m = m ^ (n ^ m) => m=n
n = n ^ m; //n = (n ^ m)^[m ^ (n ^ m)] => n=m
System.out.println(n + ";" + m); //3;2
}
常见的计算法则：
① a ^ a =0 （任何数异或本身结果为 0）
② a ^ b =b ^ a （交换律）
③ a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c （结合律）
④ 0 ^ a = a （异或 0 具有保持的特点）
⑤ a ^ b ^ a = b （根据①②④可得）
（4）取绝对值
公式： |a| = (a^(a>>31))-(a>>31)
先整理一下使用位运算取绝对值的思路：若 a 为正数，则不变，需要用异或 0 保持的特点；若 a 为负数，则其补码为源码翻转每一位后 + 1，先求其源码，补码 - 1 后再翻转每一位，此时需要使用异或 1 具有翻转的特点。
任何正数右移 31 后只剩符号位 0，最终结果为 0，任何负数右移 31 后也只剩符号位 1，溢出的 31 位截断，空出的 31 位补符号位 1，最终结果为 - 1. 右移 31 操作可以取得任何整数的符号位。
那么综合上面的步骤，可得到公式。a>>31 取得 a 的符号，若 a 为正数，a>>31 等于 0，a^0=a，不变；若 a 为负数, a>>31 等于 - 1 ，a^-1 翻转每一位。
练习：
public void test1() {
int a = -10;
System.out.println((a ^ (a >> 31)) - (a >> 31)); //10
}
四、有趣的位运算符操作
- 利用或操作 | 和空格将英文字符转换为小写
('a' | ' ') = 'a'
('A' | ' ') = 'a'
- 利用与操作 & 和下划线将英文字符转换为大写
('b' & '_') = 'B'
('B' & '_') = 'B'
- 利用异或操作 ^ 和空格进行英文字符大小写互换
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
以上操作能够产生奇特效果的原因在于 ASCII 编码。字符其实就是数字，恰巧这些字符对应的数字通过位运算就能得到正确的结果，有兴趣的读者可以查 ASCII 码表自己算算，本文就不展开讲了。
- 判断两个数是否异号
int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true
int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false
这个技巧还是很实用的，利用的是补码编码的符号位。如果不用位运算来判断是否异号，需要使用 if else 分支，还挺麻烦的。读者可能想利用乘积或者商来判断两个数是否异号，但是这种处理方式可能造成溢出，从而出现错误。
- 不用临时变量交换两个数
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1
- 加一
int n = 1;
n = -~n;
- 减一
int n = 2;
n = ~-n;
五、参考文章
参考文章 1：https://labuladong.gitee.io/algo/4/30/97/
参考文章 2：https://www.cnblogs.com/findbetterme/p/10787118.html
参考文章 3：https://blog.csdn.net/xiaochunyong/article/details/7748713