位运算：底层原理、补码与生产高频技巧

整数的二进制表示：补码

Java（以及大多数语言）中的 int 使用 32位补码表示：

补码规律：

• 正数的补码 = 原码自身
• 负数的补码 = 取反 + 1（即 ~n + 1 = -n）
• 因此 -n = ~n + 1 → n & (-n) = n & (~n + 1) = 最低位的1

为什么补码能让加法统一处理正负数：

5 + (-3)  →  0101 + 1101 = 10010 → 溢出截断32位 → 0010 = 2 ✓

符号位与算术右移

int n = -8;                // 二进制：1111...1000
int a = n >> 1;            // 算术右移：1111...1100 = -4（正确的除法）
int b = n >>> 1;           // 逻辑右移：0111...1100 = 正数！（只适合无符号场景）

应用：二分查找的安全中点（避免溢出）：

// 错误：(left + right) / 2 可能溢出
int mid = left + (right - left) / 2;

// 等价写法（无溢出）：
int mid = (left + right) >>> 1;  // 逻辑右移：正确处理大正数（left+right可能溢出int但>>>1仍正确）

符号数转换技巧

// 获取符号（1表示正，-1表示负）
int sign(int n) {
    return 1 | (n >> 31);  // 正数/0: 1|0=1, 负数: 1|(-1)=-1
}

// 正负数的绝对值（不用if/abs）
int abs(int n) {
    int mask = n >> 31;    // 正数: mask=0, 负数: mask=-1(全1)
    return (n + mask) ^ mask;  // 等价于 n >= 0 ? n : -n
}

// 判断两数是否异号
boolean diffSign(int a, int b) {
    return (a ^ b) < 0;  // 异号时最高位不同，XOR后最高位为1，即负数
}

无分支选择（位运算代替 if）

某些场景（如 SIMD、性能敏感代码）中用位运算代替条件分支：

// 选择 a 或 b（不用 if）
// cond = 0 或 1
int select(int cond, int a, int b) {
    // cond 为 1 时选 a，为 0 时选 b
    int mask = -cond;  // cond=1时mask=-1=全1，cond=0时mask=0=全0
    return (a & mask) | (b & ~mask);
}

// 求两数最大值（不用 if）
int max(int a, int b) {
    int diff = a - b;
    int sign = (diff >> 31) & 1;  // diff < 0 时 sign=1，否则 sign=0
    return a - sign * diff;       // diff>=0时返回a，否则返回a-diff=b
}

查找第 k 个置位（树状数组中的 lowbit）

lowbit 操作：取出整数最低位的 1，用于树状数组（Binary Indexed Tree）：

int lowbit(int x) {
    return x & (-x);  // -x = ~x + 1，与 x 相与保留最低位
}

// 树状数组：单点更新和前缀查询
class BIT {
    int[] tree;
    int n;

    BIT(int n) {
        this.n = n;
        tree = new int[n + 1];
    }

    // 单点加
    void update(int i, int delta) {
        for (; i <= n; i += lowbit(i)) tree[i] += delta;
    }

    // 前缀和查询 [1..i]
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= lowbit(i)) sum += tree[i];
        return sum;
    }
}

常见的位操作陷阱

1. 运算符优先级

// 错误：& 优先级低于 ==
if (n & 1 == 1) { ... }   // 等价于 n & (1 == 1) = n & 1，恰好对但容易误解

// 正确：加括号
if ((n & 1) == 1) { ... }

2. 移位超界

int x = 1 << 31;   // 有定义：MIN_INT = -2147483648（最高位为1，其余为0）
int y = 1 << 32;   // 未定义行为！Java 中等同于 1 << (32 % 32) = 1 << 0 = 1
int z = 1 << -1;   // Java 中等同于 1 << 31 = MIN_INT

3. 负数与 >>> vs >>

int n = -1;          // 1111...1111
n >> 1;              // 1111...1111 = -1（算术右移，符号位复制）
n >>> 1;             // 0111...1111 = Integer.MAX_VALUE（逻辑右移，高位补0）

4. byte 运算溢出

byte b = (byte) 0xFF;    // 转为 byte 是 -1
int n = b & 0xFF;        // 先零扩展到 int，再 AND = 255（提取无符号字节值的正确写法）

位运算在字符串中的应用

判断两个字符串是否有公共字符

boolean hasCommon(String a, String b) {
    int maskA = 0, maskB = 0;
    for (char c : a.toCharArray()) maskA |= 1 << (c - 'a');
    for (char c : b.toCharArray()) maskB |= 1 << (c - 'a');
    return (maskA & maskB) != 0;
}

统计 26 个字母各出现的次数（压缩到一个 long）

// 注意：只适合每种字母出现次数 <= 7 的场景（3 bits per letter）
long compress(String s) {
    long mask = 0;
    for (char c : s.toCharArray()) {
        int idx = c - 'a';
        int count = (int)((mask >> (idx * 3)) & 7);  // 取该字母的3位计数
        mask &= ~(7L << (idx * 3));                   // 清空该字母的3位
        mask |= ((long)(count + 1) & 7) << (idx * 3); // 写入新计数
    }
    return mask;
}

生产高频位运算题单

总结：位运算的"第一性原理"

1. 符号位（第31位）决定正负，补码让加法统一
2. 右移保留符号位（>>），逻辑右移高位补0（>>>）
3. XOR 是无进位加法，与 AND 组合可模拟全加器
4. n & (n-1) 清最低1位，是 O(k) 汉明重量的核心
5. n & (-n) 取最低1位，是树状数组 lowbit 的核心
6. 位掩码是集合的高效表示，2^n 个子集用 0 到 2^n-1 枚举
7. 状态压缩 = 集合状态 DP，适合 n ≤ 20 的组合问题