位运算应用：加法器、位翻转与数字处理

用位运算实现加法器

加法的本质：无进位和（XOR）+ 进位（AND 左移）。

  0101 (5)
+ 0011 (3)
─────────
无进位和：0101 ^ 0011 = 0110  (位不同的加了，相同的归零)
进位：    (0101 & 0011) << 1 = 0010 (两个1相加产生进位，左移一位)

再对 0110 和 0010 做加法：
无进位和：0110 ^ 0010 = 0100
进位：    (0110 & 0010) << 1 = 0100

再对 0100 和 0100 做加法：
无进位和：0100 ^ 0100 = 0000
进位：    (0100 & 0100) << 1 = 1000

再对 0000 和 1000：
无进位和：1000
进位：    0

结果：1000 = 8 ✓

int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;  // 计算进位
        a ^= b;                     // 无进位相加
        b = carry;                  // carry 变成下一轮的加数
    }
    return a;
}

递推到减法：a - b = a + (~b + 1) = a + (-b)（利用补码）

颠倒二进制位（LeetCode 190）

将 32 位整数按位颠倒（最高位变最低位）：

方法 1：逐位移位（直观）

int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res = (res << 1) | (n & 1);  // 取 n 最低位，放入 res 最低位
        n >>= 1;                      // n 右移，处理下一位
    }
    return res;
}

方法 2：分治位交换（O(1) 掩码技巧）

int reverseBits(int n) {
    // 交换16位组
    n = (n >>> 16) | (n << 16);

    // 交换每16位中的8位组
    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);

    // 交换每8位中的4位组
    n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);

    // 交换每4位中的2位组
    n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);

    // 交换相邻位
    n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);

    return n;
}

掩码含义：

0xff00ff00 = 1111_1111_0000_0000_1111_1111_0000_0000  → 奇数字节
0x00ff00ff = 0000_0000_1111_1111_0000_0000_1111_1111  → 偶数字节
0xf0f0f0f0 = 1111_0000_1111_0000_...                  → 高4位
0x0f0f0f0f = 0000_1111_0000_1111_...                  → 低4位
0xcccccccc = 1100_1100_...                             → 高2位
0x33333333 = 0011_0011_...                             → 低2位
0xaaaaaaaa = 1010_1010_...                             → 奇数位
0x55555555 = 0101_0101_...                             → 偶数位

汉明距离（LeetCode 461 / 477）

汉明距离：两个整数对应二进制位不同的位数。

单对汉明距离

int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y);  // XOR 使不同位变1，统计1的个数
}

汉明距离总和（LeetCode 477）

数组中所有整数对的汉明距离之和：

// 暴力 O(n^2) 会超时，改为按位分析
int totalHammingDistance(int[] nums) {
    int total = 0, n = nums.length;
    for (int i = 0; i < 32; i++) {
        int ones = 0;
        for (int num : nums) ones += (num >> i) & 1;  // 统计第 i 位是1的数有多少个
        // 该位：ones 个1，(n-ones) 个0
        // 贡献的汉明距离 = ones × (n-ones)（每对 0-1 各贡献1个不同位）
        total += ones * (n - ones);
    }
    return total;
}

原理：对于某一位，ones 个数包含 1，zeros = n - ones 个数包含 0。 这一位贡献的汉明对数 = ones × zeros（任意一个 1 和任意一个 0 配对，汉明距离在该位为 1）。

缺失数字（LeetCode 268）

数组包含 [0, n] 中 n 个不同数字（缺一个），找到缺失的数：

// XOR 方法：完整序列 0..n XOR 数组所有元素，成对出现的消去，剩下缺失的
int missingNumber(int[] nums) {
    int xor = nums.length;   // 最后要 XOR n
    for (int i = 0; i < nums.length; i++)
        xor ^= i ^ nums[i];  // 相当于 XOR 了 0,1,...,n 和数组所有值
    return xor;
}

// 数学方法（溢出风险小时可用）
int missingNumber2(int[] nums) {
    int n = nums.length;
    int expected = n * (n + 1) / 2;
    for (int num : nums) expected -= num;
    return expected;
}

数字范围按位与（LeetCode 201）

求 [left, right] 范围内所有整数的按位 AND：

关键观察：如果某一位在 [left, right] 中有数在该位为 0，有数在该位为 1，则 AND 结果该位为 0。只有 left 和 right 的公共前缀部分能保留。

int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    while (left != right) {
        left >>= 1;
        right >>= 1;
        shift++;
    }
    return left << shift;  // left 的公共前缀，左移还原
}

另一种写法（Brian Kernighan）：

int rangeBitwiseAnd(int left, int right) {
    while (right > left) 
        right &= (right - 1);  // 消去 right 最低位的1，直到 right < left 或相等
    return right;              // 此时 right 就是公共前缀
}

整数反转与溢出检测（LeetCode 7）

int reverse(int x) {
    long res = 0;
    while (x != 0) {
        res = res * 10 + x % 10;
        x /= 10;
    }
    // 溢出检测：Java 的 int 范围 [-2^31, 2^31-1]
    return (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) ? 0 : (int) res;
}

注意：x % 10 在 Java 中对负数保留符号（-123 % 10 = -3），所以直接用 x % 10 处理负数也是正确的。

最大 XOR 值（LeetCode 421）

数组中两数的最大异或值：

// 方法：从高位到低位贪心，尝试能否让当前位为1
int findMaximumXOR(int[] nums) {
    int max = 0, mask = 0;
    for (int i = 31; i >= 0; i--) {
        mask |= (1 << i);
        Set<Integer> prefixes = new HashSet<>();
        for (int n : nums) prefixes.add(n & mask);  // 收集所有数的前缀
        
        int greedyTry = max | (1 << i);  // 假设当前位能为1
        for (int prefix : prefixes) {
            // XOR 性质：若 a ^ b = target，则 a ^ target = b
            if (prefixes.contains(greedyTry ^ prefix)) {
                max = greedyTry;  // 能找到对应前缀，贪心成功
                break;
            }
        }
    }
    return max;
}

原理：对最高位贪心，判断是否存在两个前缀 XOR = 当前目标。若能，则最高位为1；否则为0。逐位确定答案。

小结