Java 位运算技巧

二进制

二进制（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，表示没有新增的权限；

总结

二进制是计算机中数据表示的基础，位运算必不可少
特殊的运算使用位运算的方式可以提升效率，尤其是有乘除运算时
二进制可以用来表示多种状态的组合，结合位运算使用效果最佳

Java 位运算技巧

二进制

Java 中进制的表示

负数如何用二进制表示

Java 位运算

按位与（&）

按位或（|）

按位异或（^）

按位取反（~）

左位移运算（<<）

右位移运算（>>）

无符号右位移（>>>）

Java 哪些地方用到了位运算

1.HashMap源码

2.StampedLock源码

位运算常用技巧

整乘或整除2的N次方

不借助第三个变量交换两个变量的值

判断一个数是否是 2 的幂次方

判断一个数是奇数还是偶数

异或技巧

实战技巧

一、位运算符实现一个简单的用户权限控制功能

总结

按位与（`&`）

按位或（`|`）

按位异或（`^`）

按位取反（`~`）

左位移运算（`<<`）

右位移运算（`>>`）

无符号右位移（`>>>`）