位运算符以及常见的使用场景

旧城等待， 2022-05-16 13:50 301阅读 0赞

Java中的位运算有七种：

<<   左移
    >>   右移
    >>>  无符号右移
    &    位与
    | 位或
    ~    位非
    ^    位异或

其中位非（~）是一元运算符，其他六个都是二元运算符。

这些位运算符都是作用在二进制的数上的，先列一个表描述一下这几种位运算符：

![位运算符][E4_BD_8D_E8_BF_90_E7_AE_97_E7_AC_A6.png]

下面来一一介绍一下这几种位运算符

### 位运算符介绍 ###

#### 1、<< 左移 ####

两个左尖括号表示左移运算符，运算符规则是：各二进位全部左移若干位，高位丢弃，低位补0。

例如：6 << 2 = 24

0000 0000 0000 0000 0000 0000 0000 0110     -> 6
    0000 0000 0000 0000 0000 0000 0001 1100     -> 6 << 2 = 24

*  我们将6的二进位向左移动两位，低位补上两个0，高位丢弃，得出来的结果就是24。

左移常被用来做 \* (2 ^ n)的运算，因为直接基于二进制运算，所以左移效率比 \* (2 ^ n)高。

#### 2、>> 右移 ####

两个右尖括号表示右移运算符，运算符规则是：各二进位全部右移若干位，正数高位补0，负数高位补1，低位丢弃。

例如: 12 >> 2 = 3

0000 0000 0000 0000 0000 0000 0000 1100     -> 12
    0000 0000 0000 0000 0000 0000 0000 0011     -> 12 >> 2 = 3

*  因为12是正数，右移过程中高位补上两个0，低位丢弃，得出来的结果就是3。

例如：-12 >> 2 = -3

1111 1111 1111 1111 1111 1111 1111 0100    -> -12
    1111 1111 1111 1111 1111 1111 1111 1101    -> -12 >> 2 = -3

*  因为-12是负数，右移过程中高位补上两个1，低位丢弃，得出来的结果就是-3。

右移常被用来做 / (2 ^ n)的运算，因为直接基于二进制运算，所以右移效率比 / (2 ^ n)高。

#### 3、>>> 无符号右移 ####

三个右尖括号表示无符号右移运算符，运算符规则是：各二进位全部右移若干位，高位补0，低位丢弃。

例如: 12 >>> 2 = 3

0000 0000 0000 0000 0000 0000 0000 1100     -> 12
    0000 0000 0000 0000 0000 0000 0000 0011     -> 12 >>> 2 = 3

*  我们将12的二进位向右移动两位，高位补上两个0，低位丢弃，得出来的结果就是24。

例如：-12 >>> 2 = 1073741821

1111 1111 1111 1111 1111 1111 1111 0100    -> -12
    0011 1111 1111 1111 1111 1111 1111 1101    -> -12 >> 2 = 1073741821

*  我们将-12的二进位向右移动两位，高位补上两个0，低位丢弃，得出来的结果就是1073741821。

#### 4、& 位与 ####

运算规则是：当运算符两边相同位置都是1时，结果返回1，其他情况都返回0。

例如：3 & 5 = 1

0000 0000 0000 0000 0000 0000 0000 0011     -> 3
    0000 0000 0000 0000 0000 0000 0000 0101     -> 5
    0000 0000 0000 0000 0000 0000 0000 0001     -> 3 & 5 = 1

*  其中3和5的只有第一位共同为1，所以3 & 5 = 1。

#### 5、| 位或 ####

运算规则是：当运算符两边相同位置都是0时，结果返回0，其他情况都返回1。

例如：3 | 5 = 1

0000 0000 0000 0000 0000 0000 0000 0011     -> 3
    0000 0000 0000 0000 0000 0000 0000 0101     -> 5
    0000 0000 0000 0000 0000 0000 0000 0111     -> 3 \| 5 = 7

*  其中3和5的第一到第三位都有不为0的，所以 3 | 5 = 7。

#### 6、~ 位非 ####

运算规则是：将运算符后二进制数反转，0变1，1变 。

例如：~ 3 = -4

0000 0000 0000 0000 0000 0000 0000 0011     -> 3
    1111 1111 1111 1111 1111 1111 1111 1100     -> ~ 3 = -4

*  将3的所有二进制位全部反转，所以~ 3 = -4。

#### 7、^ 位异或 ####

运算规则是：当运算符两边相同位置都是相同，结果返回0，不相同时返回1。

例如：3 ^ 5 = 1

0000 0000 0000 0000 0000 0000 0000 0011     -> 3
    0000 0000 0000 0000 0000 0000 0000 0101     -> 5
    0000 0000 0000 0000 0000 0000 0000 0110     -> 3 ^ 5 = 6

*  其中3和5的第一和第三位不相同，所以 3 ^ 5 = 6。

### 位运算符使用技巧 ###

#### 1、判断奇偶数 ####

我们可以利用 & 运算符的特性，来判断二进制数第一位是0还是1。

用if ((a & 1) == 0) 代替 if (a % 2 == 0)来判断a是不是偶数。

#### 2、交换两个数 ####

##### 借助临时变量 #####

通常我们交换两个数会使用一个临时变量来帮忙：

int temp = a;
    a = b;
    b = temp;

##### 借助累加和 #####

如果考虑到内存，不希望使用临时变量（其实就是为了炫酷），可以这样实现：

a = a + b;
    b = a - b;
    a = a - b;

从数学角度来分析一下（这个解释很违和，需要在一个频道才能看懂）：  
\- 第一步：a = a + b  
\- 第二步：b = a - b = (a + b) - b = a  
\- 第三步：a = a - b = (a + b) - b = (a + b) - a = b

##### 使用 ^ 位运算符 #####

如果想要更炫酷一点可以使用 ^ 来帮忙实现：  
先来了解一下 ^ 的几个特性：  
\- a ^ a = 0  
\- a ^ 0 = a  
\- (a ^ b) ^ c = a ^ (b ^ c)

a ^= b;
    b ^= a;
    a ^= b;

从数学角度来分析一下这个解释也很违和，需要在一个频道才能看懂）：  
\- 第一步：a = a ^ b  
\- 第二步：b = a ^ b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a  
\- 第三步：a = a ^ b = (a ^ b) ^ b = (a ^ a) ^ b = b ^ 0 = b

#### 3、取余 ####

其实取余算法和上面的判断奇偶数原理是一样的。

比如说我们要让a对16进行取余，那么就可以让 a & 15 得出来的结果就是余数。

可以看出15的二进制表示为：

0000 0000 0000 0000 0000 0000 0000 1111

所以 a & 15 返回值就是a二进制的最低四位，也就是 a & 15 = a / 16。

使用 & 来进行取余的算法比使用 / 效率高很多，虽然只能对2^n的数值进行取余计算，但是在JDK源码中也是经常被使用到，比如说HashMap中判断key在Hash桶中的位置。

#### 4、生成第一个大于a的满足2^n的数 ####

这个标题可能显得不那么容易理解，下面结合场景来解释一下。

在HashMap中我们需要生成一个Hash桶，用来存储键值对（或者说存储链表）。

当我们查询一个key的时候，会计算出这个key的hashCode，然后根据这个hashCode来计算出这个key在hash桶中的落点，由于上面介绍的使用 & 来取余效率比 / 效率高，所以HashMap中根据hashCode计算落点使用的是 & 来取余。

使用 & 取余有一个局限性就是除数必须是2^n，所以hash桶的size必须是2^n。

由于HashMap的构造器支持传入一个初始的hash桶size，所以HashMap需要对用户传入的size进行处理，生成一个第一个大于size的并且满足2^n的数。

这个算法的使用场景介绍完毕了，那么再来看一下算法实现：

##### 循环判断 #####

public static final int tableSizeFor(int cap) {
        int size = 1;
        while (size < cap) {
            size *= 2;
        }
        return size;
    }

##### | 运算符实现 #####

public static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

HashMap就是使用这个算法来修改用户使用构造器传进来的size的，这个算法是使用移位和或结合来实现的，性能上比循环判断要好。

#### 5、其他简单应用 ####

*  求相反数： ~a + 1
 *  求绝对值： a >> 31 == 0 ? a : (~a + 1)

--------------------

喜欢这篇文章的朋友，欢迎扫描下图关注公众号**lebronchen**，第一时间收到更新内容。  
![这里写图片描述][70]

[E4_BD_8D_E8_BF_90_E7_AE_97_E7_AC_A6.png]: /images/20220516/6cb882abfb0647d596ca9864ce70522e.png
[70]: /images/20220516/5e272b23225e4e129abee1d9a1ade0d5.png