2025-03-15-位运算

这篇文章上次修改于 227 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

参考资料
https://oi-wiki.org/math/bit/

1. 位运算简介

位运算是一种基于整数二进制表示的运算方式。由于计算机内部以二进制形式存储数据，位运算的速度非常快，通常比普通算术运算更高效。

2. 基本位运算操作

按位与（&）：两个二进制位都为 1 时，结果为 1；否则为 0。
按位或（|）：两个二进制位中至少有一个为 1 时，结果为 1；否则为 0。
按位异或（^）：两个二进制位相同为 0，不同为 1。

异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即

按位取反（~）：将二进制位的 0 变为 1，1 变为 0。
左移（<<）：将二进制表示向左移动若干位，右侧补 0。
右移（>>）：将二进制表示向右移动若干位，左侧补符号位（有符号数）或补 0（无符号数）。

3. 位运算的特殊性质

异或运算的逆运算：异或运算具有自反性，即 a ^ b ^ b = a。
补码表示：计算机中负数以补码形式存储，正数的补码是其本身，负数的补码是其绝对值的二进制表示取反后加 1。

4. 位运算的应用

位运算在编程中有多种高效应用，包括但不限于：

高效运算：例如，通过左移和右移实现乘除 2 的幂次方。
集合操作：利用位运算表示集合，常用于状态压缩动态规划（状压 DP）。
特定问题的优化：例如，快速求解汉明权重（二进制中 1 的个数）。

5. 位运算的实用技巧

5.1 取绝对值

int Abs(int n) {
    return (n ^ (n >> 31)) - (n >> 31);
}

通过位运算实现取绝对值，避免分支判断。

5.2 求最大/最小值

int max(int a, int b) {
    return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31));
}

利用位运算实现高效的求最大值和最小值操作。

5.3 判断符号是否相同

bool isSameSign(int x, int y) {
    return (x ^ y) >= 0;
}

通过异或运算判断两个数的符号是否相同。

5.4 操作二进制位

获取某一位的值：

int getBit(int a, int b) { return (a >> b) & 1; }

设置某一位为0或1：

int unsetBit(int a, int b) { return a & ~(1 << b); }
int setBit(int a, int b) { return a | (1 << b); }

6. 汉明权重与二进制操作

汉明权重是指一个二进制数中 1 的个数。可以通过循环或 lowbit 操作快速求解：

int popcount(int x) {
    int cnt = 0;
    while (x) {
        cnt++;
        x -= x & -x;
    }
    return cnt;
}

7. 内建函数

GCC 提供了一些位运算相关的内建函数，例如：

__builtin_popcount(x)：计算二进制中 1 的个数。
__builtin_clz(x)：计算前导 0 的个数。
__builtin_ctz(x)：计算末尾 0 的个数。

这些函数经过编译器优化，运行速度极快。

8. 更多位数的处理

对于更大的数据集，可以使用 bitset 等数据结构进行高效位操作。

9.应用

状态

异或加密

TK的小站