Leetcode / 位运算

合理的运用位运算能显著提高代码在机器上的执行效率。

右移运算符:>>

将一个数a向右移动n位记为:a>>n。

  • 逻辑右移/无符号右移(java: >>>),在移动过程中,空位都以0补齐。
  • 算术右移(java: >>): 符号位不变,剩下位右移,空位补上符号位。

如:a = 00110111,则a>>2 = 00001101,b=11010011,则b>>2 = 11110100
如:a = 00110111,则a>>>2 = 00001101,b=11010011,则b>>>2 = 00110100。

左移运算符:<<

将一个数a向左移动n位记为:a<<n。
在左移的过程中,右边一律用0去填充。左边的二进制丢弃。

比如,将10左移2位,由于10的二进制为:00001010,那么左移2位,右边用零填充的结果为:00101000。
将一个数左移N位相当于将一个数乘以$2^N$,将一个数算数右移(>>)N位相当于将这个数除以$2^N$。

异或

性质:

  • n^n = 0
  • n^0 = n
  • 异或操作满足交换律和结合律

136 唯一出现奇数次的数字 / 389 找不同 / 540. 有序数组中的单一元素
剑指56-1 唯二出现次数为奇数的数(分组异或)
剑指56-2 出现一次的数(除了一个数字以外,其余数字都出现 m 次 的通用问题:记录数组中所有数字每一位的和,对m取余)
268 丢失的数字
剑指53 - II 0~n-1中缺失的数字
318 最大单词长度乘积

异或运算交换2个数:

1
2
3
4
5
int a=10; 
int b=20;
a=a^b;
b=a^b;
a=a^b;

二进制位

  • a的二进制末位为1,那么a & 1 =1。如果a的二进制末位为0,那么a & 1=0。
    • 判断a的二进制第i位是否是1: (a >> i & 1) == 1 ? true : false
  • n & (n−1),其运算结果为把 n 的二进制位中的最低位的 1 变为 0 。
  • 一个整数如果是 2 的整数次方,则其二进制表示中仅有1位1。
    • 判断整数是否为2的次方:n & (n−1) == 0 ? true : false

191 / 剑指 Offer 15 二进制中1的个数(无符号数)
(对有符号数:不断左移flag,和整数进行与运算。)
(两个整数 m 和 n,需要改变m中的多少位得到n:首先 m ^ n,然后求结果中1的位数)
338 比特位计数(dp + 位运算)
【如果 i 为偶数,那么 f(i) = f(i/2) ,因为 i/2 本质上是i的二进制左移一位,低位补零,所以1的数量不变】
【如果 i 为奇数,那么f(i) = f(i - 1) + 1, 因为如果i为奇数,那么 i - 1必定为偶数,而偶数的二进制最低位一定是0,那么该偶数 +1 后最低位变为1且不会进位,所以奇数比它上一个偶数bit上多一个1,即 f(i) = f(i - 1) + 1】

补码

计算机系统主要原因:使用补码,可以将符号位和其它位统一处理;同时,减法也可按加法来处理。另外,两个用补码表示的数相加时,如果最高位(符号位)有进位,则进位被舍弃。

求补码

最高位是符号位,0表示正,1为负

  • 正数的补码:与原码相同。
    例如,+9的补码 00001001。
  • 负数的补码:符号位为1,其余位为该数绝对值的原码按位取反;然后整个数加1。

例如,-7的补码:因为是负数,则符号位为“1;-7的绝对值+7的原码0000111按位取反为1111000;再加1,所以-7的补码是11111001。

已知补码求原码

  • 如果补码的符号位为“0”,表示是一个正数,所以补码就是该数的原码。
  • 如果补码的符号位为“1”,表示是一个负数,求原码:符号位为1,其余各位取反,然后再整个数加1。

补码的表示范围

$-2^{n-1} —2^{n-1} -1$

  • 8位二进制带符号数表示范围:-128—127

补码加减法运算

计算机中,符号数一律用补码表示,运算时符号位和数字位一起参加运算。运算结果也用补码表示。

X, Y表示原数值

两符号数相加公式:[X+Y]补=[X]补+[Y]补
两符号数相减公式:[X-Y]补=[X]补+[-Y]补

java

Integer.MAX_VALUE,(2147483647),2^31 - 1, 0x7FFFFFFF
Integer. MIN_VALUE,(-2147483648),-2^31,

Integer.MAX_VALUE + 1 = Integer. MIN_VALUE
Math.abs(Integer.MIN_VALUE) = Integer.MIN_VALUE
-Integer.MIN_VALUE == Integer.MIN_VALUE

1
2
3
4
5
Integer.MAX_VALUE:  01111111 11111111 11111111 11111111
1: 00000000 00000000 00000000 00000001
相加:10000000 00000000 00000000 00000000
Integer.MIN_VALUE: 10000000 00000000 00000000 00000000