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$。

异或 xor

性质：

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

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

异或运算交换2个数（a,b相等时不适用）：

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

Integer.MAX_VALUE:  01111111 11111111 11111111 11111111
				1:  00000000 00000000 00000000 00000001
				相加:10000000 00000000 00000000 00000000
Integer.MIN_VALUE:  10000000 00000000 00000000 00000000