数据结构与算法 - 位运算

一、位运算介绍

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

Java定义了位运算符，应用于整数类型(int)，长整型(long)，短整型(short)，字符型(char)，和字节型(byte)等类型。

下表列出了位运算符的基本运算，假设整数变量A的值为60和变量B的值为13：

位运算.png

&（与）

示例：

int a = 60; /* 60 = 0011 1100 */ 
int b = 13; /* 13 = 0000 1101 */
int c = 0;
c = a & b;       /* 12 = 0000 1100 */
System.out.println("a & b = " + c );

|（或）

示例：

int a = 60; /* 60 = 0011 1100 */ 
int b = 13; /* 13 = 0000 1101 */
int c = 0;
c = a | b;  /* 61 = 0011 1101 */
System.out.println("a | b = " + c );

〜（非）

示例：

int a = 60; /* 60 = 0011 1100 */ 
int c = 0;
c = ~a;     /*-61 = 1100 0011 */
System.out.println("~a = " + c );

^（异或）

示例：

int a = 60; /* 60 = 0011 1100 */ 
int b = 13; /* 13 = 0000 1101 */
int c = 0;
c = a ^ b;       /* 49 = 0011 0001 */
System.out.println("a ^ b = " + c );

<<（左移）

示例：

int a = 60; /* 60 = 0011 1100 */ 
int c = 0;
c = a << 2;     /* 240 = 1111 0000 */
System.out.println("a << 2 = " + c );

>> （右移）

示例：

int a = 60; /* 60 = 0011 1100 */ 
int c = 0;
c = a >> 2;     /* 15 = 1111 */
System.out.println("a >> 2  = " + c );

>>>（无符号左移）

示例：

int a = 60; /* 60 = 0011 1100 */ 
int c = 0;
c = a >>> 2;     /* 15 = 0000 1111 */
System.out.println("a >>> 2 = " + c );

二、位运算应用

1. 位运算(&)来实现取模运算(%)

我们知道乘除法使用位运算进行替换时有这样的规律：对二进制数左移一位相当于其对应的十进制数值乘以2，右移一位相当于除以2。

有求商操作：被除数为X，除数为2^K，求（X / 2^K ）。

根据上面的规则我们使用位运算来进行操作，也就是说X的二进制右移K位即可。

System.out.println("5/2=" + (5 >> 1) );
System.out.println("5/4=" + (5 >> 2) );
System.out.println("5/8=" + (5 >> 3) );

执行结果为：

5/2=2
5/4=1
5/8=0

有求余操作：被除数为X，除数为2^K，求（X % 2^K ）。

仍然从位操作的角度来思考，我们来看一下下面的操作展示：

求余位操作.png

通过上面的图示我们可以发现一个规律，通过位移操作后，被移出的位所对应的十进制数值即为余数。

也就是说求(X%2^K)，通过位操作来运算的话就是保留X后K位。

5%2^1 = 保留5的二进制数的后1位
5%2^2 = 保留5的二进制数的后2位
5%2^3 = 保留5的二进制数的后3位

被除数是2的K次方，相对应的2进制有如下的表示形式：

2的k次方.png

后K全为0。做2^K-1操作，二进制形式如下：

2的k次方减1.png

后K为全为1。那么就可以想到要保留X的后K位的话，就可以与上面的二进制数进行&操作即可。

与操作.png

总结：当a=2^k(k为自然数)时，x % a = x & (a - 1 )

注意用位运算代替取模运算有两个限制：

被除数为正整数
除数为2^k（k为自然数）

JDK的HashMap的源码中，也是采用位操作代替取模这种方式来确定键值在哈希表中的索引：

i = (n - 1) & hash

2. 整数的奇偶性判断

整数中，能被2整除的数是偶数，不能被2整除的数是奇数。

奇偶数.png

从上述二进制格式的表示可以看到，奇数对应的二进制数最低位为1，偶数对应的最低位为0。则通过位运算来判断奇偶性就可以这么操作：

设有整数a, 执行 a & 1操作，若结果为1则表示a为奇数；若结果为0，则表示a为偶数。