数据结构与算法之位运算符

位运算就是对二进制数执行计算, 是整数的逐位运算. 例如1+1=2在十进制计算中是正确的, 但是在二进制计算中1+1=10. 对于二进制数 100 取反, 等于 001,而不是 -100

位运算符有 7 个, 分为两类:

  • 逻辑位运算符:位与(&) 位或(|) 位异或(^) 非位(~)
  • 移位运算符:左移(<<) 右移(>>) 无符号右移(>>>)

逻辑位运算符

在逻辑位运算符中&, |无需多说, 这里主要说一下^异或运算符. 异或运算符用于对两个二进制操作数逐位进行比较, 举例: 23 ^ 9

23转换为二进制为10111, 转换过程为23 / 2, 整除为1不能整除为0
9转换为二进制为1001
逐位运算
1 0 1 1 1
0 1 0 0 1
    ||
1 1 1 1 0

1 ^ 0 = 1, 1 ^ 1 = 0, 0 ^ 0 = 0

将11110转换为十进制0*2^1-1 + 1*2^2-1 + 1*2^3-1 + 1*2^4-1 + 1*2^5-1 = 30

10to2

非位(~)运算符运算实际上就是对数字进行取负运算,再减 1, 举例: ~23 = -23-1 = -24

移位运算符

<<运算符执行左移位运算. 在移位运算过程中, 符号位始终保持不变. 如果右侧空出位置, 则自动填充为 0; 超出 32 位的值, 则自动丢弃. 举例5转换为二进制为101

1 0 1 << 2
0 0 0
   ||
1 0 1 0 0

10100转换为十进制为20

左移几位就是原数乘以2^n, 比如5 >> 2 = 5 * 2^2 = 20

“>>”运算符执行有符号右移位运算。与左移运算操作相反, 它把 32 位数字中的所有有效位整体右移, 再使用符号位的值填充空位. 移动过程中超出的值将被丢弃.

1 0 1 >> 2
0 0 0
   ||
1

1转换为十进制为1

通俗点说101右移两位就是删除101最后两位数01,只剩1然后将二进制1转换为十进制, 再举个例子23 >> 3, 23的二进制为10111右移3位变成10, 将10转换为十进制为2