note/algorithm/1、位运算.md

一个数的相反数为取反加1.
取反的结果和原来的数相加结果为2^32^-1,再加1则进位为0。

2^32^-1二进制为

```shell
11111111 11111111 11111111 11111111
```

```shell
# 例如 int a = 1024;二进制为
00000000 00000000 00001000 00000000
# 取反后
11111111 11111111 11110111 11111111
# 相加为
11111111 11111111 11111111 11111111 
a+~a+1=0;则-a=~a+1;
```

```Java
# 打印int类型二进制字符串方法
private static void printCompleteBinaryStr(int num){
    for (int i = 31; i >= 0; i--) {
        System.out.print((num & (1 << i)) == 0 ? "0" : "1");
        if (i < 31 && (i + 1) % 8 == 0) {
            System.out.print(" ");
        }
    }
    System.out.println();
}
```

Integer.MIN_VALUE取反加一后仍然为Integer.MIN_VALUE，这不是bug。
Integer.MAX_VALUE加1后溢出为Integer.MIN_VALUE，Integer.MIN_VALUE减一则溢出为Integer.MAX_VALUE。

异或运算满足交换律和结合律
a^b=b^a
(a^b)^c=a^(b^c)
a、b交换
a=a^b
b=a^b
a=a^b

给定数组arr，只有一个数出现了奇数次，其它数都是偶数次，找到并打印这个数。
偶数次异或为0，奇数次异或为本身，遍历每一个元素并异或，最后结果就是奇数次的数字。

拿到一个数二进制最右侧的1
a&(~a+1)

给定数组arr，只有一种数出现了K次，其他数都出现M次。
假设a出现k次，b出现m次
将所有数字的二进制位相加，则t[i] % m就是a的二进制在i位置次数，要么是0，要么是k