位运算: 基本知识

Posted on 2024-09-19 Edited on 2025-12-31 In Algorithm , Trick Word count in article: 1.7k Reading time ≈ 6 mins.

硬件加速的二进制算法

求最高有效位

定义末位为第零位
__builtin_clz()：原理bsr(bit scan reserve,逆向位扫描)，可视作O(1)，能求出前导零个数

参数为零时返回结果未定义

最高有效位为31-__builtin_clz()
__lg()：直接给出，实际上编译后代码与上述方法一致

且该方法是log2()的优替，快速返回一个整数的以2为底对数的下取整

与运算

基本性质

与运算只保留两个操作数共同拥有的1

掩码

判奇偶性：A&1 = 1?奇 : 偶
模2ⁿ：A%2ⁿ = A&((1<<n)−1)
判断二进制码子集：若B是A的子集，则A&B = B

计1的个数

调用库函数：C++:__builtin_popcount()、Java:Integer.bitCount()

暴力算法：

  while (x) {
      ans += x & 1;
      x >>= 1;
  }

- `Brian Kernighan`算法：跳过最右$1$和末位中间的零，直接对该一计数

  $k=x\&(x-1)$的性质是：$k$和$x$相差最右边的$1$

  迭代直到$x=0$，循环次数即一的个数

  ```c++
  while (x) {
      x &= x - 1;
      ++ans;
  }

分治算法(Java bitCount()所用方法)：

问题难点在于不知道哪里有1，也就无从统计

暴力算法是遍历所有位(优化后的BK算法也是O(n))使1加起来，换言之，就是将n位数分成n组

那么，分治算法的思想是遍历所有两位，将其分为$\frac n2$组，使1/2加起来
1
2
3
4
5
while (x) {
// 这里需要先以每两位为一组, 求得1的个数, 覆盖回x
ans += x & 3; // 3 == 0b0000....0011
x >>= 2;
}
那么首先就要知道每个组是0/1/2中的哪个数：
将整数以每两位为一组划分，要求出每组的1的个数，就是要求每组中所有位的加和

其对应关系为$\begin{matrix}原码&(1的个数)_2\\00&00\\01&01\\10&01\\11&10\end{matrix}$，那么如何将这个计量关系快速算出，且每组间互不影响？

首先，取掩码$\rm 0b0101..0101$，即$\rm 0x55..5$，相与后能将每组中位于奇位置的1保留，偶位置全为零

让原整数右移一位，则原本处于偶位置的1移到奇位置，原本处于奇位置的1移位相与后为零(故不影响其它组)

将两次相与的结果相加，每组中1的个数就得到了，因为加和最大为2，故每组是独立的
当然，分治算法不能满足于如此，这样还需遍历$\frac n2$次

既然一次合并就能降低一半复杂度了，尝试继续合并，最后ans = x&(全1) = x

重复上述过程，但以每四位为一组划分：

类似上述掩码，取$\rm 0b0011..0011$，即$\rm 0x33..3$，结果为x&M + (x>>2)&M

形象表达：将x看作四进制数，每两位四进制数(即每四位为一组)为一组，求每组所有位的加和；即$\begin{matrix}(原码)_4&(所有位的加和)_4\\00&00\\01/10&01\\02/20/11&02\\21/12&03\\22&10\end{matrix}$，因为加和最大为4，故每组间独立计算，互不影响

重复每2n一组的划分，直到只剩下一组，对这一组完成最后的统计后，则剩余整数就是所求

以32位整数为例，最终一次运算应以32位为一组，$M={\rm 0x0000ffff}、x=x\&M+(x>>16)\&M$，此时x就是所求

```c++ // 对int/unsigned int 32位整数: x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f); x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff); x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff); // 此时x为所求


- 分治算法在位运算上的优化(我也没想到这还能优化)：

  - 对第一步：每组中原码和统计后码值的关系可优化为**原码减去偶数位值**：节省一次与运算

    $\begin{matrix}原码&计算过程&1的个数\\00&00-0&00\\01&01-0&01\\10&10-1&01\\11&11-1&10\end{matrix}$，即`x -= (x >> 1) & 0x55555555`

  - 对第三步：因为经过前两步后，以每$8$位为一组时，组中所有位加和最多为$8$，最多占四位，因此可以先让高位和低位相加后再相与(**相与**为了**去除组间**的影响)：

    `x = (x + (x >> 4)) & 0x0f0f0f0f`

    根据这个思路，第一、二步无法通过这种方法优化，第一步最多占两位，第二步最多占三位，因此不能先加再与；第三步以后均可通过该方法优化

  - 对更后面的步骤(第四步及以后)：每组加和的最大值所需位数远小于每组位数的一半，例如第四步中，每组加和最大为$16$，占五位；而每组位数的一半为$8$

    因此从上一个组移到下一个组的位不会有影响，例如：

     第三步后：$\rm0x\ 0a_0\ 0a_0..0a_0$，$a_0\le1000$，若后续**不和掩码相与**

     第四步后：$\rm0x\ 0a_0bb_0\ aa_1bb_0..aa_1bb_0$

     $bb_0=a_{0h}+a_{0l}\le10000、aa_1=a_{0up}+a_{0h}\le10000$

     第五步后：$\rm0x\ 0a_0bb_0\ aa_2cc_0\ aa_3cc_0..aa_3cc_0$

     $cc_0=bb_{0h}+bb_{0l}\le100000、aa_2=0a_0+aa_1\le11000、aa_3=aa_1+aa_1\le100000$

     若和掩码相与：第四步$\rm0x00bb00bb..00bb$、第五步$\rm0x000000cc..000000cc$

    上述$cc$(有效位)只要在八位之内，多余位就可在最后一步和掩码相与后除去

    换言之，只要在计数之前除去多余位即可；由于$32$位整数本就**只用$6$位**，因此第四、五步可以不与：

    ```c++
    x -= (x >> 1) & 0x55555555;
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0f0f0f0f;
    x += x >> 8;
    x += x >> 16;
    x &= 0x3f; // 最后保留末6位即可
    // 推广到64位, 因为有效位为7, 故:
    // (在第五步之后)
    x += x >> 32;
    x &= 0x7f;

和乘法的结合：和上述思想类似，因为有效位只有六位，在第三步后每组八位，就可在第三步后将末三组移到最高八位相加(末三组总和不超过六位，故不会影响最高组)

即：(x+x<<8+x<<16+x<<24) > > 24，分配律到乘法

即：$(x\cross\rm0x1010101)>>24$，乘法得出的高位应强制转换成int来舍去它们

乘法效率其实不如上述优化强，但代码更简洁：

```c++ unsigned int y = x; y -= (y >> 1) & 0x55555555; y = (y & 0x33333333) + ((y >> 2) & 0x33333333); y = (((y >> 4) & 0x0f0f0f0f) * 0x1010101) >> 24;

异或运算

基本性质

异或运算后，两操作数相同位得零、不同位得一
异或运算是一种对称加密：A = (A⊕B) ⊕ B、B = (A⊕B) ⊕ A
- 不通过第三个变量交换两个整数：A ⊕ B → A、A ⊕ B → B、A ⊕ B → A
- A ⊕ Ā = 全1、A ⊕ A = 0
满足差分性质：

汉明距离

汉明距离：两个整数中不同位的个数
计算一：调用库函数

```c++ __builtin_popcount(x ^ y);