note/algorithm/1、位运算.md

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

2^32^-1二进制为

11111111 11111111 11111111 11111111

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

# 打印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