数据结构与算法|数据结构与算法 - 位运算数据结构与算法-位运算

一、位运算介绍程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。
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进制有如下的表示形式：