数据结构-位运算_数据结构按位查找
- 左移( << ):操作数的非0位左移n位,低位补0
- 右移( >> ):操作数的非0位右移n位,高位补0
- 无符号右移( >>> ):正数右移,高位用0补,负数右移,高位用1补,当负数使用无符号右移时,用0进行补位
- 位非( ~ ):操作数为1则为0,否则为1
- 位与( & ):第一个数和第二个数,都为1则为1,否则为0
- 位或( | ):第一个数和第二个数,有一个为1则为1,否则为0
- 位异或( ^ ):第一个数和第二个数,有一个不相同则为1,否则为0
a^a=0; // 自己和自己异或等于0
a^0=a; // 任何数字和0异或还等于他自己
a^b^c=a^c^b; // 异或运算具有交换律
左移( << )
案例如下:
5<<2=20
在进行“5 << 2 = 20”这一运算时,首先需将数字 5 转换为二进制表示形式。在 Java 编程语言里,整数默认采用 int 类型,即 32 位二进制数。数字 5 的 32 位二进制表示为:0000 0000 0000 0000 0000 0000 0000 0101。
接着,对该二进制数执行左移 2 位的操作。在左移过程中,低位会自动补 0,左移 2 位后的二进制数变为:0000 0000 0000 0000 0000 0000 0001 0100。
最后,将此二进制数换算为十进制数,得到的结果为 20。
右移( >> )
案例如下:
5>>2=1
还是先将5转为2进制表示形式:
0000 0000 0000 0000 0000 0000 0000 0101 然后右移2位,高位补0
0000 0000 0000 0000 0000 0000 0000 0001
无符号右移( >>> )
在 Java 编程领域,我们了解到 int 类型的数据占用 32 位存储空间,它既能够用于表示正数,也可用于表示负数。具体而言,当正数换算为二进制形式时,其最高位为 0;而负数的二进制表示中,最高位为 1。
在进行右移操作时,对于正数而言,右移过程中高位会用 0 进行补位;对于负数,右移时高位则用 1 进行补位。值得注意的是,当对负数执行无符号右移操作时,高位将使用 0 来进行补位。
案例如下:
5>>3=1
-5>>-1
-5>>>536870911
我们来看看它的移位过程(可以通过其结果换算成二进制进行对比):
5换算成二进制: 0000 0000 0000 0000 0000 0000 0000 0101
5右移3位后结果为0,0的二进制为: 0000 0000 0000 0000 0000 0000 0000 0000 // (用0进行补位)
-5换算成二进制: 1111 1111 1111 1111 1111 1111 1111 1011
-5右移3位后结果为-1,-1的二进制为: 1111 1111 1111 1111 1111 1111 1111 1111 // (用1进行补位)
-5无符号右移3位后的结果 536870911 换算成二进制: 0001 1111 1111 1111 1111 1111 1111 1111 // (用0进行补位)
位非( ~ )
若操作数的第 n 位为 1,则结果的第 n 位为 0;反之,若操作数的第 n 位为 0,则结果的第 n 位为 1。
案例如下:
~5=-6
5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101
-6转换为二进制:1111 1111 1111 1111 1111 1111 1111 1010
位与( & )
在逻辑运算规则中,当两个操作数对应位均为 1 时,结果对应位为 1;若不满足此条件,即至少有一个操作数对应位为 0 时,结果对应位为 0。
具体而言,对于第一个操作数的第 n 位和第二个操作数的第 n 位,若二者均为 1,那么运算结果的第 n 位亦为 1;反之,只要第一个操作数的第 n 位和第二个操作数的第 n 位中有一个为 0,结果的第 n 位则为 0。
案例如下:
5&3=1
将2个操作数和结果都转换为二进制进行比较: 5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101
3转换为二进制:0000 0000 0000 0000 0000 0000 0000 0011
1转换为二进制:0000 0000 0000 0000 0000 0000 0000 0001
位或( | )
在进行相关位运算时,针对第一个操作数的第 n 位与第二个操作数的第 n 位,若这两个对应位中至少有一个为 1,那么运算结果的第 n 位即为 1;若这两个对应位均为 0,那么运算结果的第 n 位则为 0。
案例如下:
5|3=7
5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101
3转换为二进制:0000 0000 0000 0000 0000 0000 0000 0011
7转换为二进制:0000 0000 0000 0000 0000 0000 0000 0111
位异或( ^ )
在进行按位异或运算时,若第一个操作数的第 n 位与第二个操作数的第 n 位相反(即一个为 0,另一个为 1),则运算结果的第 n 位为 1;若二者相同(都为 0 或者都为 1),则结果的第 n 位为 0。
依据此运算规则,任意操作数 a 与 0 进行按位异或运算,其结果仍为操作数 a,即 a^0 = a。
a^0=a
案例如下:
5^3=6
5转换为二进制:0000 0000 0000 0000 0000 0000 0000 0101
3转换为二进制:0000 0000 0000 0000 0000 0000 0000 0011
6转换为二进制:0000 0000 0000 0000 0000 0000 0000 0110
衍生
在编程领域,由位运算操作符衍生出了一系列复合赋值运算符,具体如下:
- &=:按位与赋值运算符,它将左操作数与右操作数进行按位与运算,并将结果赋值给左操作数。
- |=:按位或赋值运算符,其作用是把左操作数和右操作数进行按位或运算,然后将所得结果赋值给左操作数。
- ^=:按位异或赋值运算符,该运算符会对左操作数和右操作数执行按位异或运算,再把运算结果赋值给左操作数。这里原文“按位非赋值”表述有误,正确的是按位异或赋值。
- >>=:右移赋值运算符,它把左操作数向右移动右操作数指定的位数,然后将结果赋值给左操作数。
- >>>=:无符号右移赋值运算符,此运算符将左操作数以无符号的方式向右移动右操作数指定的位数,之后把结果赋值给左操作数。原文此处重复写为>>=,应予以纠正。
- <<=:左移赋值运算符,它把左操作数向左移动右操作数指定的位数,随后将结果赋值给左操作数。
这些位运算复合赋值运算符与+=这类算术复合赋值运算符在概念上有相似之处,都是先进行相应运算,再将结果赋值给左操作数。