1.4.1 基本位运算符

位运算是直接对整数在内存中的二进制位进行操作的一种运算方式。与常规的算术运算相比，位运算通常具有更高的执行效率，因为它直接操作底层二进制数据，避免了复杂的算术逻辑。

1.4.2 基本位操作

一. 移位运算

n << m  // n乘以2^m
n >> m  // n除以2^m，向下取整
temp >>= 1  // 除以2，向下取整

移位运算是最基础且最高效的位操作之一。

<<将二进制位向左移动，右侧空位补0，相当于乘以2的幂次。>>将二进制位向右移动，对于无符号数左侧补0，对于有符号数补符号位，相当于除以2的幂次（向下取整）。

左移运算 n << m 将数值 n 的二进制表示向左移动 m 位，相当于乘以 2 的 m 次方。右移运算 n >> m 则将二进制表示向右移动 m 位，相当于除以 2 的 m 次方，十分优秀的，这是向下取整的除法，与常规除法向零取整不同，即使是负数，也可以向下取整，而不会向上。

temp >>= 1 可以快速实现除以2的操作。

二. 位构建和提取

ans = (ans << 1) | bit  // 把bit追加到ans的末尾
ans = (ans << 1) | 0    // 第i位为0
ans = (ans << 1) | 1    // 第i位为1
bit = (x >> i) & 1      // 提取x的第i位

位构建时，我们一般习惯从高位开始构建。

ans = (ans << 1) | bit 这个操作实现了从高位到低位逐步构建二进制数的功能：首先通过左移为新的位腾出空间，然后通过或运算将新的位值设置到最低位。

类似的，ans = (ans << 1) | 0 和 ans = (ans << 1) | 1 分别用于设置特定位为0或1。

位提取操作 bit = (x >> i) & 1 通过组合右移和与运算来获取特定位置的值。首先通过右移将目标位移到最低位，然后通过与1进行与运算来隔离该位的值，因为1只有一位，所以一定可以得到选择的特定位置。

三. 位设置和清除

x | (1 << i)     // 将第i位设为1
x & ~(1 << i)    // 将第i位设为0
x ^ (1 << i)     // 将第i位取反

设置位操作 x | (1 << i) 首先通过左移生成一个只有第i位为1的掩码，然后通过或运算将该位设置为1，其他位保持不变。这是因为或运算的特性：任何位与1或运算结果都为1，与0或运算保持原值。

清除位操作 x & ~(1 << i) 首先生成目标位的掩码，然后取反得到除目标位外全为1的掩码，最后通过与运算将目标位清零。

取反操作 x ^ (1 << i) 利用异或运算的特性：与1异或会翻转该位，与0异或保持原值。

1.4.3 特殊数值生成

一. 生成掩码

(1LL << i) - 1        // i个1
(1 << i)              // 只有第i位为1
~((1 << (i+1)) - 1)   // 高位的掩码

掩码生成是位运算中的重要技术，用于创建特定的位模式来选择和操作数据的某些部分。

(1LL << i) - 1 生成一个包含i个低位1的掩码，其原理是：首先将1左移i位得到2^i，然后减1得到从第0位到第i-1位全为1的掩码。

(1 << i) 生成仅第i位为1的掩码，用于选择或设置单个位。

~((1 << (i+1)) - 1) 生成高位的掩码，其构造过程相对复杂：先创建低i+1位为1的掩码，然后取反得到高位为1、低位为0的掩码。

二. 全1检测

bool allOne(ll x, int pos) {
    for (int i = pos; i >= 0; i--) {
        ll xbit = (x >> i) & 1;
        if(!xbit) {
            return false;
        } 
    }
    return true;
}

全1检测函数用于验证从指定位置到最低位是否所有位都为1。这个函数通过循环从高位到低位逐个检查每一位的状态，使用 (x >> i) & 1 来提取第i位的值。如果发现任何位为0，立即返回false；如果所有检查的位都为1，则返回true。

1.4.4 位统计和分析

一. 汉明权重

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

汉明权重（popcount）是指一个二进制数中1的个数，在信息论、编码理论和算法设计中具有重要作用。第一种方法采用逐位检查的策略：通过循环每次检查最低位是否为1，然后右移一位，直到数值变为0。这种方法逻辑简单直观，易于理解，但对于包含大量0的数值效率较低，因为需要遍历所有位。

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

除此之外，也可以使用lowbit优化，利用了 x & -x 来快速找到并清除最低位的1。x & -x 的结果是只保留x中最低位的1，其他位全为0。通过每次清除最低位的1并计数，循环次数正好等于1的个数，这对于稀疏的二进制数（1的个数较少）特别高效。

二. 前缀和位统计

vector<vector<int>> prefix(31, vector<int>(n+2, 0));
for(int i = 30; i >= 0; i--) {           
    for(int j = 1; j <= n; j++) {
        int temp = (a[j] >> i) & 1;
        prefix[i][j] = prefix[i][j-1] + temp;
    }
}

前缀和位统计为每个二进制位单独维护一个前缀和数组，prefix[i][j] 表示第i位在前j个元素中1的个数。

这种数据结构构建完成后，可以在O(1)时间内回答任意区间 [l, r] 内第i位1的个数：prefix[i][r] - prefix[i][l-1]。

1.4.5 数值操作

一. 绝对值

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

工作原理基于补码表示法的特性：对于正整数，右移31位得到0，表达式简化为 n ^ 0 - 0 = n；对于负整数，右移31位得到-1（因为符号位扩展），表达式变为 n ^ (-1) - (-1)。异或-1相当于按位取反，而减去-1相当于加1，这正好是计算补码的步骤。

需要注意的是，这种方法对于最小负数值（如-2^31）可能产生未定义行为，因为其绝对值超出了正数表示范围。

二. 最大最小值

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

通过纯位运算实现最大最小值计算，避免了传统的条件判断。其核心思想是利用算术右移的特性：当 a - b >= 0 时，(a - b) >> 31 结果为0；当 a - b < 0 时，结果为-1（所有位为1）。通过这个差异来控制选择a还是b。

在最大值函数中，当 a >= b 时，掩码为0，结果来自a的部分；当 a < b 时，掩码为全1，结果来自b的部分。最小值函数逻辑类似但选择相反。

三. 交换两个数

void swap(int &a, int &b) {
    a ^= b ^= a ^= b;
}

这个交换函数利用异或运算的性质实现无需临时变量的数值交换。异或运算具有以下重要性质：x ^ x = 0，x ^ 0 = x，且满***换律和结合律。交换过程分为三步：首先 a ^= b 将a变为a和b的异或值；然后 b ^= a 相当于 b ^ (a ^ b) = a，将b变为原来的a；最后 a ^= b 相当于 (a ^ b) ^ a = b，将a变为原来的b。

需要注意的是，当a和b指向同一内存位置时，这种方***将值清零，产生错误结果，而且可读性差得离谱，多数情况下，使用临时变量temp或者std::swap更好。

1.4.6 位运算在算法中的应用

一. 区间位运算

count_ones = prefix[i][r] - prefix[i][l-1];

if(count_ones * 2 < r - l + 1) {
    ans = (ans << 1) | 1;
} else {
    ans = (ans << 1) | 0;
}

区间位运算结合了前缀和技术和位构建技术，首先通过前缀和数组快速计算区间内某一位上1的个数：count_ones = prefix[i][r] - prefix[i][l-1]。然后基于统计结果进行决策：如果1的个数少于区间长度的一半，说明该位在多数元素中为0，因此在答案中设置该位为1；否则设置该位为0。

二. 位运算模拟

int bit0 = 0, bit1 = -1;  // bit0为32位全0，bit1为32位全1
bit0 &= t;  bit1 &= t;  // AND操作
bit0 |= t;  bit1 |= t;  // OR操作
bit0 ^= t;  bit1 ^= t;  // XOR操作

位运算模拟技术用于跟踪某个位在经过一系列位操作后的状态变化。通过维护两个状态变量 bit0 和 bit1，分别表示当该位初始为0或1时，经过操作序列后的最终状态。

1.4.7 边界检测和优化

一. 位数计算

int bitCnt = 0;
while(temp) {
    bitCnt++;
    temp >>= 1;
}

位数计算用于确定一个数值在二进制表示中所需的位数，即最高有效位的位置加1。这个循环通过不断右移数值直到变为0来统计位数，每次右移相当于除以2，循环次数就是二进制位数。

二. 符号检测

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

符号检测函数利用异或运算和比较运算来快速判断两个数是否同号。其原理基于补码表示法的特性：最高位是符号位，0表示正数，1表示负数。当两个数同号时，它们的符号位相同，异或结果的符号位为0，因此异或结果是非负数；当两个数异号时，符号位不同，异或结果的符号位为1，因此异或结果是负数。

1.4.8 高级技巧

一. Lowbit操作

x & -x        // 获取最低位的1
x & (x - 1)   // 清除最低位的1

Lowbit操作是位运算中的经典技巧，用于快速定位和操作最低位的1。x & -x 利用补码表示法的特性：负数的补码是正数的按位取反加1。因此 -x = ~x + 1，当x与-x进行与运算时，只有最低位的1会被保留，其他位都被清零。这个操作在树状数组（Fenwick Tree）中至关重要，用于高效计算前缀和。

x & (x - 1) 用于清除最低位的1，其原理是：x-1会将最低位的1变为0，该位之后的所有0变为1，因此与x进行与运算后，最低位的1被清零。这个操作在汉明权重等计算中非常有用。例如判断一个数是否是2的幂次方，只需要检查 x & (x - 1) 是否为0。

二. 位段操作

// 提取位段
int extractBits(int x, int start, int length) {
    return (x >> start) & ((1 << length) - 1);
}

// 设置位段
int setBits(int x, int start, int length, int value) {
    int mask = ((1 << length) - 1) << start;
    return (x & ~mask) | (value << start);
}

位段操作用于高效地访问和修改二进制数中的连续位组。提取位段操作首先通过右移将目标位段移动到最低位，然后通过与掩码进行与运算来隔离这些位。掩码 (1 << length) - 1 生成一个低length位为1的位模式，用于选择所需的位段。

设置位段操作稍微复杂：首先创建位段掩码并将其左移到目标位置，然后取反得到清除掩码，用于将目标位段清零，最后将新值左移到正确位置并通过或运算设置到位段中。

三. 奇偶校验

bool isOdd(int x) {
    return x & 1;
}
bool isEven(int x) {
    return !(x & 1);
}

奇偶校验是最简单但极其常用的位运算技巧，用于快速判断整数的奇偶性。x & 1 提取最低位的值，如果为1说明是奇数，如果为0说明是偶数。

四. 判断是否为2的幂

bool isPowerOfTwo(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

2的幂次方在二进制中只有一个1（比如：1=1, 2=10, 4=100, 8=1000），x & (x - 1) 会清除最低位的1,如果清除后等于0，说明原来只有一个1，也就是2的幂。

需要注意的是，因为0和负数不是2的幂，也需要对此进行判断。

五. 获取最高有效位

int highestOneBit(int x) {
    while (x & (x - 1)) {
        x &= x - 1;
    }
    return x;
}

反复清除最低位的1，直到只剩下最高位的1，x &= (x - 1)清除一个最低位的1，当只剩一个1时停止，可以得到小于x且最大的，最高位为1，以后都是0的数，也就是的2的幂。