位运算

常用 trick

• 学会用 bitset
• x & 1 检测 x 是否为奇
• x & (x-1) 可以检测是否是2的整数次幂 (x&x-1 可以清除最右边的1,如果这个1是第一位的1, 那这个数就变为0)
  • x & 0xaaaaaaaa 判断 1 是不是都在偶数上，结合 x & x - 1 可以判断 4 的幂
  • x & 0x55555555 > 0 也可以判断 1 是不是在偶数，这个可以自己设计，可以变动的
  • 在golang里 貌似 x - 1 不加括号结果是错的
• (x >> i) & 1 取出 x 的第 i 位二进制

基础知识

Binary，Octal和 Hexadecimal的表示 (通用)

• Binary: 0b
• Octal: 0 or 0o (Python和JS允许0o)
• Hexadecimal: 0x or 0X

​

运算符，运算符顺序

位运算的赋值运算符

其他运算符

运算符优先级 「由高到低」

1
2
3
4
5
6

0xaaaaaaaa = 10101010101010101010101010101010 (偶数位为1，奇数位为0） (4的幂)
0x55555555 = 1010101010101010101010101010101 (偶数位为0，奇数位为1）
0x33333333 = 110011001100110011001100110011 (1和0每隔两位交替出现)
0xcccccccc = 11001100110011001100110011001100 (0和1每隔两位交替出现)
0x0f0f0f0f = 00001111000011110000111100001111 (1和0每隔四位交替出现)
0xf0f0f0f0 = 11110000111100001111000011110000 (0和1每隔四位交替出现)

190. 颠倒二进制位 「>>= 和 >> 的区别」

1
2
3
4
5
6
7
8
9

// res 一开始为0, 每次我们都将 res左移, 将n右移
uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i) {
            res = (res << 1) | (n & 1);   
            n >>= 1;
        }
        return res;
    }

XOR 的性质:

1. x⊕x=0 , x⊕0 = x

2. x⊕y=y⊕x (交换律)

3. (x⊕y)⊕z=x⊕(y⊕z) (结合律) 「不支持分配律」

4. x⊕y⊕y=x (自反性)

5. ∀i∈Z，有 4i⊕(4i+1)⊕(4i+2)⊕(4i+3)=0

如何取按照要求 取一个整型中的某些二进制位？

• 对于x , 取其第i位的二进制 $\rightarrow$ (x >> i) & 1 (从0开始)

• 对于x，清除第 i 位的二进制

• 如果我们框定了x的范围，比如我们确认x <= 1024 那么32位中必然只需要使用其中最右边的10位

  • 想取 高4位(即10位中左边的4位) 那显然 res = x >> 6
  • 想取 低6位 则不需要移位，可以通过==与运算(和全1与)==直接取 比如这里 2^6 -1 res = x & 63;

关于进制转换问题

• 我们使用的进制转换是短除法的进制转换，因此最后有一个 reverse 操作，不要忘记

交换x y

• 直接交换法: a = a - b , b = a + b, a = b - a;
• 异或法 : x = x ^ y, y = x ^ y, x = x ^ y

__builtin_popcount(i) 计算32位整型里 1的个数

• 一句话逻辑运算
  • or => 只要有 1 结果为 1
  • and => 只有 1 & 1 = 1,其他为 0
    • 取奇偶(配合移位取二进制)
    • 分组(见找出 2 个只出现 1 次的数， 核心思想：按照某一位是否为 1 来把数组分成两个部分)
  • xor => 两个二进制不同, 结果为 1 / 二进制不进位加法
    • 抵消 / 二进制交换