数据结构-位运算_数据结构按位查找

yumo6662小时前技术文章1
  • 左移( << ):操作数的非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

衍生


在编程领域,由位运算操作符衍生出了一系列复合赋值运算符,具体如下:

  • &=:按位与赋值运算符,它将左操作数与右操作数进行按位与运算,并将结果赋值给左操作数。
  • |=:按位或赋值运算符,其作用是把左操作数和右操作数进行按位或运算,然后将所得结果赋值给左操作数。
  • ^=:按位异或赋值运算符,该运算符会对左操作数和右操作数执行按位异或运算,再把运算结果赋值给左操作数。这里原文“按位非赋值”表述有误,正确的是按位异或赋值。
  • >>=:右移赋值运算符,它把左操作数向右移动右操作数指定的位数,然后将结果赋值给左操作数。
  • >>>=:无符号右移赋值运算符,此运算符将左操作数以无符号的方式向右移动右操作数指定的位数,之后把结果赋值给左操作数。原文此处重复写为>>=,应予以纠正。
  • <<=:左移赋值运算符,它把左操作数向左移动右操作数指定的位数,随后将结果赋值给左操作数。

这些位运算复合赋值运算符与+=这类算术复合赋值运算符在概念上有相似之处,都是先进行相应运算,再将结果赋值给左操作数。

相关文章

PLC的位逻辑运算指令_plc中的位怎么理解

PLC(可编程逻辑控制器)的位指令是针对单个二进制位(0 或 1)进行操作的基础指令,主要用于逻辑控制,是梯形图(LD)编程中最常用的指令类型。以下是 PLC 位指令的核心类别及常用指令:常开常闭输出...

【C语言·015】逗号运算符的求值顺序与返回值规则

很多人第一次看到 , 都把它当“分隔符”:函数实参之间的逗号、初始化列表里的逗号……但在表达式里,, 还有另一个身份——逗号运算符。它既能强制求值顺序,又能控制返回值,是解决副作用与顺序问题的一把小刀...

C 语言指针全解析:从门牌号到内存黑魔法,一文带你彻底搞懂!

很多人一提到 C 语言指针 就皱眉:“指针是不是地址?”“数组和指针是不是一样的?”“为什么 * 有时候是解引用,有时候是乘法?”其实指针没那么神秘。只要把它拆开理解,就会发现它不过是一串数字,存的就...

C语言应用笔记:整数字节大小端翻转

在C语言中,实现大小端(Endian)翻转可以通过位操作或内存操作完成。以下提供两种常用方法:方法1:位运算(推荐)通过移位和掩码操作直接交换字节位置:// 16位翻转(安全版本) #define S...

C语言应用笔记:获取结构体成员偏移地址

在C语言中,获取结构体成员的偏移地址(即成员相对于结构体起始地址的字节偏移量)有两种常用方法:1. 使用标准库宏 offsetof(推荐)<stddef.h> 头文件提供了 offseto...