Zohar's blog

算法笔记 - 位运算

Algorithmalgorithmbit operation

记录常见/常用的位运算技巧,有新的知识点会持续更新,一起学习。

运算技巧

乘 2

a * 2 == a << 1,正负通用,即左移一位,二进制全体位数左移一位,整数翻倍,与普通运算一样有可能超出整型边界。

由于负数采用补码表示,左移高位符号位丢失,但是符号位后方同样是 1,因此正负通用,如:

-1024 = 0b11111111111111111111110000000000
-2048 = 0b11111111111111111111100000000000

乘 2 加 1

a * 2 + 1 == a << 1 | 1,正负通用,左移乘 2,左移之后最低位必定为 0,通过“or 1” 操作将最低位转为 1 实现加一。

由于负数采用补码表示,低位表示数的规则和正数是一致的,将最低位 0 转为 1,同样会加一,如:

-1024 = 0b11111111111111111111110000000000
-1023 = 0b11111111111111111111110000000001

除 2

a / 2 == a >> 1,即带符号右移一位,二进制全体位数右移一位,最高位补原有符号位,由于是整数除法,必定会出现无法整除的情况,此时正负数的结果是不同的:

  • 正数:与普通除法一致,若无法整除,向下取整,如 11 / 2 == 11 >> 1 == 5

  • 负数:与普通除法不一致,若无法整除,向下取整,普通除法向上取整,如:

      // 普通除法
      -11 / 2 = -5
      // 带符号右移除法
      -11 >> 1 = -6
      -11 = 0b11111111111111111111111111110101
      -6  = 0b11111111111111111111111111111010
    

    事实上个人感觉右移除法更为合理,因为是移位运算,其结果跟正数是一样的,都是向下取整。

取相反数

~a + 1,正负通用,根据补码表示法,整数取反加一即可转化为对应的相反数,如:

  1024 = 0b00000000000000000000010000000000
 -1024 = 0b11111111111111111111110000000000
 ~1024 = 0b11111111111111111111101111111111
~-1024 = 0b00000000000000000000001111111111

消去最低位的 1

a & (a - 1),对于二进制数,减去最低位的 1 之后,该位变为 0,高位不变,更低位全部变为 1。如

0b00010110 -1 = 
0b00010101

0b00011000 -1 = 
0b00010111

0b11111000(-8) -1 =
0b11110111(-9)

因此,通过 a &= (a - 1) 的方式,可以消去 a 最低位的 1。

获取最低位 1(lowbit)

a & (-a),负数的补码是正数补码加一。正数低位的 0 取反后为 1,再加 1 则会进位直到将遇到的第一个 0 转为 1。因此负数补码的最低位 0 就是正数补码的最低位 1。因此 a-a 的最低位 1 是相同的,其他位 1 均不相同。因此 a & (-a) 可以获取最低位 1,此操作也被称为 lowbit 操作。

因为 -a 等于 a 取反加一,因此 a & (-a) == a & (~a + 1)

 22 = 0b00010110
~22 = 0b11101001
 +1 = 0b11101010(-22)
 &  = 0b00000010

高低位交换

  • 折半高低位交换:
      a = (a >>> 4) | (a << 4)
    

    假设一个单字节数高四位和低四位进行交换,直接左移和右移,最后异或即可,如:

      0b11001110 >>> 4 = 0b00001100
      0b11001110 << 4  = 0b11100000
      0b00001100 | 0b11100000 = 0b11101100
    

    其他字节数折半高低位交换依此类推。

  • 非折半首尾高低位交换:
      a = (a & 0b_0000_1111_1111_0000) | ((a >>> 12) | (a << 12))
    

    假设一个双字节数高四位和低四位交换,依旧是上面的思想,左移右移再异或,如:

      0b1100_xxxx_xxxx_0011(n) >>> 12 = 0b0000_0000_0000_1100
      0b1100_xxxx_xxxx_0011(n) <<  12 = 0b0011_0000_0000_0000
      0b0000_0000_0000_1100    | 0b0011_0000_0000_0000 = 0b0011_0000_0000_1100
      0b1100_xxxx_xxxx_0011(n) & 0b0000_1111_1111_0000 = 0b0000_xxxx_xxxx_0000
      0b0000_xxxx_xxxx_0000    | 0b0011_0000_0000_1100 = 0b0011_xxxx_xxxx_1100
    
  • 间隔高低位交换:

    aaaabbbbccccdddd 交换为 bbbbaaaaddddcccc

      a = (a & (0b0000_1111_0000_1111) << 4) | (a & (0b1111_0000_1111_0000) >>> 4)
    

    分解:

      0baaaa_bbbb_cccc_dddd & 0b0000_1111_0000_1111 = 0b0000_bbbb_0000_dddd
      0b0000_bbbb_0000_dddd << 4                    = 0bbbbb_0000_dddd_0000
      0baaaa_bbbb_cccc_dddd & 0b1111_0000_1111_0000 = 0baaaa_0000_cccc_0000
      0baaaa_0000_cccc_0000 >>> 4                   = 0b0000_aaaa_0000_cccc
      0bbbbb_0000_dddd_0000 | 0b0000_aaaa_0000_cccc = 0bbbbb_aaaa_dddd_cccc
    

判断

判断奇偶

a & 1,“and 1” 操作保留最后一位,由于奇数最后一位为 1,偶数最后一位为 0,因此:

  • a & 1 == 1,a 为奇数。
  • a & 1 != 1,a 为偶数。

判断是否为 2 的幂方

a & (a - 1) == 0,上文所推断,a & (a - 1) 可以消去最低位的 1。如果一个数是二的幂方,那么它的二进制表示中必定只有一个 1,因此消去该低位 1 之后,所有位数都将是 0。

判断整型相加是否溢出

整型 x、y 相加存在以下情况:

  1. 正负相加不会溢出。
  2. 正正相加不溢出,结果符号为正。
  3. 正正相加产生溢出,结果符号为负。
  4. 负负相加不溢出,结果符号为负。
  5. 负负相加产生溢出,结果符号为正。

因此只有结果与二参数符号位都不同的情况是溢出,因此判断这一个即可:如果结果 $r$ 与 $x$ 和 $y$ 的符号都不相同,则产生溢出。

public static int addExact(int x, int y) {
    int r = x + y;
    if (((x ^ r) & (y ^ r)) < 0) {
        throw new ArithmeticException("integer overflow");
    }
    return r;
}

位算法

交换两个数

通过二进制交换两个数。

a ^= b;
b ^= a;
a ^= b;

一个数与两个相同的数进行异或运算,结果必定等于自己;因为异或的结果是保留对方与自身位值不同的地方,也就是两个二进制数有差异的位,再拿这些有差异的位去对方身上异或运算,那就是我自己了。如:

0b1010 ^ 0b1111 = 0b0101
0b0101 ^ 0b1111 = 0b1010

a ^= b 时,a 的值为 a ^ b
b ^= a 等于 b = b ^ (a ^ b) 等于 a;
a ^= b 等于 a = (a ^ b) ^ a 等于 b;

注意!数组存在特殊情况,nums[i]nums[i] 交换时 nums[i] 将变成 0。因为异或交换两个数的前提是两个数分开存储,如果对于同一数组元素进行这么操作,由于只有一个存储单元,自己与自己异或会清空所有的 1 位,将变为 0,原理等同于 aa 使用异或交换。

统计 1 位个数(人口统计)

统计一个数中 1 位的数量。

  • 通过逐步消去低位 1 直至 0 来判断。时间复杂度:$O(k)$

      public static int bitCount(int n) {
          int count = 0, tmp = n;
          while (tmp != 0) {
              count++;
              tmp = tmp & (tmp - 1);
          }
          return count;
      }
    
  • 通过 lowbit 来逐步判断,其背后的原理其实就是逐步消去低位 1,因此和上面的是一样的。时间复杂度:$O(k)$

      public static int bitCount(int n) {
          int count = 0;
          int lowbit;
          while ((lowbit = n & -n) != 0) {
              n -= lowbit;
              count++;
          }
          return count;
      }
    
  • Java 的默认实现,暂未了解,待详解后更新

      public static int bitCount(int i) {
          // HD, Figure 5-2
          i = i - ((i >>> 1) & 0x55555555);
          i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
          i = (i + (i >>> 4)) & 0x0f0f0f0f;
          i = i + (i >>> 8);
          i = i + (i >>> 16);
          return i & 0x3f;
      }
    

求绝对值

利用位运算求绝对值。

public static int abs(int n) {
    int i = n >> 31;
    return (n ^ i) - i;
}

正数的绝对值为本身,负数绝对值为相反数,因此先通过右移获取符号位信息。若 n 为正数,则 n >> 31 为 0,若 n 为负数,则 n >> 31 为 -1。

任何数与 0 异或结果都为本身,任何数减去 0 结果都为本身,因此,若为正数,n == (n ^ 0) - 0
任何数与 -1 异或结果等同于取反,任何数减去 -1 结果都为加一,取反加一是取相反数的算法,因此,若为负数,-n == (n ^ -1) - (-1)

知道有这种用法就好了,写的时候请写成 n < 0 ? -n : n,否则容易被人打。

二进制位逆序

翻转一个数的所有二进制位。

a = ((a & 0b10101010_10101010) >>> 1) | ((a & 0b01010101_01010101) << 1) // 两两翻转
a = ((a & 0b11110000_11110000) >>> 4) | ((a & 0b00001111_00001111) << 4) // 四四翻转
a = ((a & 0b11111111_00000000) >>> 8) | ((a & 0b00000000_11111111) << 8) // 八八翻转
// 依此类推

逆序要么重复相应位数的次数,要么采用分区交换的方法逆序,此处使用分区交换的方式逆序,先两两交换,四四交换,八八交换,如果是 32 位整型最后还要十六十六交换。

实现加法

public int getSum(int a, int b) {
    return a == 0 ? b : getSum((a & b) << 1, a ^ b);
}

异或被称为不进位加法,即丢弃进位,同时保留差异位。

13 = 01101
 6 = 00110
 ^ = 01011

不进位加法 + 进位 = 加法,因此我们实现进位即可。与运算可以实现进位,只需要将与运算结果左移一位即可。

13 = 01101
 6 = 00110
 & = 00100
<< = 01000

将“进位”和“不进位加法”的结果进行一次“不进位加法”即可求得一次新的没有进位的加法,我们只需要不断重复这个步骤,就可以将所有进位消除了。

01011 & 01000 = 01000
01000 << 1    = 10000
01011 ^ 01000 = 00011

10000 & 00011 = 00000
10000 ^ 00011 = 10011 = 19 = 16 + 3