二进制
二进制（binary）通常用0和1来进行表示，在数字电子电路中，逻辑门直接采用了二进制，现代计算机和依赖计算机设备里面也都用到了二进制，而位运算就是直接对整数在内存中的二进制位进行操作。
比如二进制：0000 1000
对应的十进制是：8
Java 中进制的表示
在Java7之前，Java是不支持直接书写二进制的，但在Java7开始就支持直接书写二进制。
- 二进制（前缀：0b/0B）
- 8进制（前缀：0）
- 16进制（前缀：0x/0X）
下面是10进制数32，在Java语言中的4种不同进制表示方式
public static void main(String[] args){
// 二进制
int a = 0b00100000;
// 8进制
int b = 040;
// 十进制
int c = 32;
// 十六进制
int d = 0x20;
System.out.println(a);
System.out.println(b);
System.out.println(c);
System.out.println(d);
}
负数如何用二进制表示
将其原码除符号位外的所有位取反（0变1，1变0，符号位变为1）后加1；
比如-9；
+9的原码为:1001；
-9为：先取反（+9）得到0110，符号位要变为1，得到10110，最后加上1，得到最后结果 10111；
Java 位运算
Java支持的位运算有：
- 按位与（
&） - 按位或（
|） - 按位异或（
^） - 按位取反（
~） - 左位移（
<<） - 右位移（
>>） - 无符号右位移（
>>>）
按位与（&）
计算规则：如果相对应位都是1，则结果为1，否则为0
运算示例：
System.out.println(32 & 16);
// 计算过程：
0010 0000
& 0001 0000
= 0
按位或（|）
计算规则：如果相对应位都是 0，则结果为 0，否则为 1（只要有一个是1，那结果ji）；
运算示例：
System.out.println(32 & 16);
// 计算过程：
0010 0000
| 0001 0000
= 0011 0000
按位异或（^）
计算规则：如果相对应位值相同，则结果为0，否则为1（不同才为1）；
运算示例：
System.out.println(32 & 16);
// 计算过程：
0010 0000
^ 0001 0000
= 0011 0000
按位取反（~）
计算规则：按位取反运算符翻转操作数的每一位，即0变成1，1变成0；
运算示例：
System.out.println(~16);
// 计算过程：
~ 0001 0000
= 1110 1111
左位移运算（<<）
计算规则：将一个二进制数中的每一位全部都向左方向移动指定位数；溢出的部分被舍弃，空缺的部分全部填0；
运算示例：
System.out.println(16 << 1);
// 计算过程：
0001 0000（十进制16）
<< 1（左位移1位）
= 0010 0000（十进制32）
右位移运算（>>）
计算规则：将一个二进制数中的每一位全部都向右方向移动指定位数；溢出的部分被舍弃，空缺的部分全部填0；
运算示例：
System.out.println(16 << 1);
// 计算过程：
0001 0000（十进制16）
>> 1（右位移1位）
= 0000 1000（十进制8）
无符号右位移（>>>）
计算规则：忽略操作数的符号向右移动指定的位数；溢出的部分被舍弃，空缺的部分全部填0；
运算示例：
System.out.println(16 << 1);
// 计算过程：
0001 0000（十进制16）
>>> 1（无符号右位移1位）
= 0000 1000（十进制8）
Java 哪些地方用到了位运算
位运算在某些时候不仅能够提升我们的运算速度，还能基于二进制位运算计数来简化我们的业务设计。
1.HashMap源码
在HashMap的源码中，初始容量和最大容量，以及索引定位，都是通过位运算计算而来的。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
// 使用位运算计算位置索引（传统的计算是hash % n），位运算算余数要求(n-1)中的n必须是2的幂
// 这也是为什么HashMap 要求桶的个数的2的N次方-1的一个原因
int index = (n - 1) & hash
2.StampedLock源码
在升级版的读写锁StampedLock中，仅用一个state字段就表示了读锁、写锁的状态和版本，就是通过二进制位的思想来完成的。
// 用来计算state值的常量
private static final long RUNIT = 1L; // 读单位
// 写锁的标识位 十进制：128 二进制位标示：1000 0000
private static final long WBIT = 1L << LG_READERS;
// 读状态标识 admol 十进制：127 二进制： 0111 1111
private static final long RBITS = WBIT - 1L;
// 读锁的最大标识 十进制：126 二进制 ：0111 1110
private static final long RFULL = RBITS - 1L;
// 用来读取读写状态 十进制：255 二进制：1111 1111
private static final long ABITS = RBITS | WBIT;
StampedLock源码分析可以查看之前的文章：StampedLock源码分析
位运算常用技巧
通过位运算可以实现很多计算上的骚操作，比如：
整乘或整除2的N次方
右移N位相当于除以2的N次方，左移N位相当于乘以2的N次方；
10 * 2 可以写成 10 << 1;
10 / 2 可以写成 10 >> 1;
快速求余数：当两个整数a % b , 恰好b等于2的N次方的时候, 可以使用a & (b-1)计算，比如: 9 % 4 = 9 & 3；
不借助第三个变量交换两个变量的值
传统的做法：
int a= 3; int b = 5;
a = a + b;
b = a - b;
a = a - b;
虽然使用传统的做法也可以实现功能，但是其中在做a = a + b加法运算的时候，结果可能会溢出，超出int的最大值，从而导致BUG的产出。
使用位运算：
int a= 3; int b = 5;
a = a ^ b;
b = a ^ b ;
a = a ^ b;
使用位运算不会有溢出的问题。
判断一个数是否是 2 的幂次方
这是LeetCode上面的一道题：2的幂；通过位运算技巧可以实现O(1)的时间复杂度解决问题；
两种方法：
-
获取二进制中最右边的 1
x & (-x)
具体原理为什么可以，可以查看LeetCode的分析；
然后通过(x & (-x)) == x;即可判断数是否是 2 的幂次方。 -
去除二进制中最右边的 1
x & (x - 1)
具体原理为什么可以，可以查看LeetCode的分析；
因此判断是否为 2 的幂可以用：判断x & (x - 1) == 0
判断一个数是奇数还是偶数
因为在二进制的表示方式下偶数的最低位肯定是0，奇数的最低位肯定是1。
所以可以使用(x & 1) == 0 来判断一个数的奇偶性。
异或技巧
-
两个相同的数异或后为0
n ^ n => 0 -
任何数于0异或后仍为任何数
0 ^ n => n
实战技巧
一、位运算符实现一个简单的用户权限控制功能
假设一个系统希望可以赋予不同用户有不同的操作权限，分别是可查看权限、可新增权限、可修改权限、可删除权限。
传统的做法可能需要用到用户表、权限表、用户权限表；
位运算的方式可以使用一个字段（p_value）即可表示一个用户拥有的功能。
用二进制的4位来分别代表可查看权限、可新增权限、可修改权限、可删除权限。
- 0001：表示拥有可查看权限（十进制1）
- 0010：表示拥有可新增权限（十进制2）
- 0100：表示拥有可修改权限（十进制4）
- 1000：表示拥有可删除权限（十进制8）
假如一个用户张三同时拥有4种权限，那用二进制表示就是：1111（十进制15）
1.如何给用户添加权限？
假如张三之前的权限是0000，现在要给他添加可查看权限（0001）；
计算过程就是：p_value =(old_p_value | 0001)
假如张三已经拥有了可查看权限（0001），现在要给他添加可修改权限（0100）；
计算过程就是：p_value =(old_p_value | 0100)
所以添加权限的计算过程就是：p_value =(old_p_value | 添加的权限值)
2.如何删除用户的某一权限？
假如张三拥有所有的操作权限（1111），现在要将他的删除权限给下掉；
计算思路就是要把代表删除权限的第4位给置为0；这里要用到位运算取反和与；
计算过程是：p_value = (1111 & (~1000)) ⇒ 0111；也就代表没有删除权限；
3.如何校验用户是否拥有删除权限？
加入张三现在只有可查看、可新增、可修改权限，也就是（0111）；
现在要校验张三是否有可新增权限：
计算思路：校验第2位是否为1即可。
计算过程：return (0111 & 0010) == 1，如果计算为false，表示没有新增的权限；
总结
- 二进制是计算机中数据表示的基础，位运算必不可少
- 特殊的运算使用位运算的方式可以提升效率，尤其是有乘除运算时
- 二进制可以用来表示多种状态的组合，结合位运算使用效果最佳
