位运算

位运算（Bit Manipulation）是直接对整数在内存中的二进制位进行操作的运算方式。由于计算机底层就是使用二进制存储和处理数据，位运算通常比算术运算更快速，在某些算法场景中能够提供巧妙的 O(1) 解法。

理解位运算不仅是掌握底层编程的基础，也是解决特定算法题的重要技巧。本章将系统介绍位运算的原理、常用技巧和经典应用场景。

二进制基础

在深入学习位运算之前，我们需要先理解二进制表示。

二进制表示法

计算机中的所有数据最终都以二进制形式存储。二进制只有 0 和 1 两个数字，每一位称为一个比特（bit）。例如，十进制数字 13 的二进制表示是 1101：

$1101 = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 8 + 4 + 0 + 1 = 13$

在 Java 和 Python 中，可以用 0b 前缀表示二进制数字：

int a = 0b1101;  // 等价于十进制的 13
int b = 0b1010;  // 等价于十进制的 10

# Python
a = 0b1101  # 13
print(bin(13))  # 输出: '0b1101'
print(int('1101', 2))  # 二进制转十进制: 13

原码、反码与补码

计算机使用补码来表示有符号整数，理解这一点对处理负数的位运算很重要：

概念	说明	示例（-5 的 8 位表示）
原码	最高位为符号位，0 表示正，1 表示负	`10000101`
反码	正数同原码，负数除符号位外按位取反	`11111010`
补码	正数同原码，负数为反码加 1	`11111011`

补码的设计使得减法可以转换为加法运算，简化了计算机的算术逻辑单元设计。

位运算符详解

按位与（AND）- `&`

两个对应的二进制位都为 1 时，结果才为 1，否则为 0。

  1100  (12)
& 1010  (10)
------
  1000  (8)

应用场景：

判断奇偶性：n & 1（结果为 1 是奇数，0 是偶数）
取指定位：n & 0xFF 取低 8 位
清零特定位：n & ~mask 清除 mask 对应的位

// 判断奇偶
boolean isOdd = (n & 1) == 1;

// 取低 4 位
int low4 = n & 0xF;

// 判断 n 是否是 2 的幂（只有一个 1）
boolean isPowerOfTwo = (n > 0) && ((n & (n - 1)) == 0);

按位或（OR）- `|`

两个对应的二进制位有一个为 1，结果就为 1。

  1100  (12)
| 1010  (10)
------
  1110  (14)

应用场景：

设置特定位为 1：n | mask
合并权限标志

// 设置第 3 位为 1
n = n | (1 << 3);

// 权限组合
int READ = 1;      // 001
int WRITE = 2;     // 010
int EXECUTE = 4;   // 100
int permission = READ | WRITE;  // 011，可读可写

按位异或（XOR）- `^`

两个对应的二进制位不同时结果为 1，相同时结果为 0。

  1100  (12)
^ 1010  (10)
------
  0110  (6)

异或的重要性质：

性质	表达式	说明
恒等律	`x ^ 0 = x`	任何数与 0 异或结果不变
归零律	`x ^ x = 0`	任何数与自己异或结果为 0
交换律	`x ^ y = y ^ x`	异或满足交换律
结合律	`(x ^ y) ^ z = x ^ (y ^ z)`	异或满足结合律
自反性	`x ^ y ^ y = x`	两次异或同一个数结果不变

这些性质是很多位运算技巧的基础：

// 交换两个变量（无需临时变量）
a = a ^ b;
b = a ^ b;  // 等价于 (a ^ b) ^ b = a
a = a ^ b;  // 等价于 (a ^ b) ^ a = b

// 简化写法
a ^= b;
b ^= a;
a ^= b;

按位取反（NOT）- `~`

对每一位取反，0 变 1，1 变 0。

~ 00001100  (12)
--------
  11110011  (-13，补码表示)

注意：由于计算机使用补码，~n = -(n + 1)。

左移运算 - `<<`

将二进制位全部左移若干位，右边补 0。左移 n 位相当于乘以 $2^n$ 。

00001100  (12)
<< 2
--------
00110000  (48)

int a = 3;       // 二进制: 11
int b = a << 2;  // 二进制: 1100，十进制: 12
// 3 << 2 = 3 * 2² = 12

右移运算 - `>>` 和 `>>>`

算术右移 >>：右移后左边补符号位（正数补 0，负数补 1）。右移 n 位相当于除以 $2^n$ （向下取整）。

00110000  (48)
>> 2
--------
00001100  (12)

逻辑右移 >>>（仅 Java）：右移后左边始终补 0，不考虑符号位。

int a = -8;       // 二进制: 11111111111111111111111111111000
int b = a >> 1;   // 算术右移: -4（保持符号）
int c = a >>> 1;  // 逻辑右移: 2147483644（高位补 0）

经典位运算技巧

技巧一：判断奇偶性

// 传统方法
boolean isOdd = n % 2 != 0;

// 位运算方法（更快）
boolean isOdd = (n & 1) == 1;

原理：奇数的最低位是 1，偶数的最低位是 0。n & 1 只保留最低位。

技巧二：判断是否为 2 的幂

一个数如果是 2 的幂，它的二进制表示中只有一个 1。

boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

原理：n - 1 会将 n 的最低位 1 变为 0，并将其后的所有 0 变为 1。例如：

n     = 10000  (16)
n - 1 = 01111  (15)
n & (n-1) = 00000  (0)

技巧三：统计二进制中 1 的个数（汉明重量）

int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);  // 清除最低位的 1
        count++;
    }
    return count;
}

原理：n & (n - 1) 可以消除 n 的最低位 1，每次消除一个 1，计数加 1，直到 n 变为 0。这种方法的时间复杂度取决于 1 的个数，而不是位数。

另一种方法是逐位检查：

int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if ((n & (1 << i)) != 0) {
            count++;
        }
    }
    return count;
}

技巧四：获取最低位的 1（Lowbit）

int lowbit = n & (-n);

原理：-n 在补码中等于 ~n + 1，与原数进行与运算后，只保留最低位的 1。

n    = 101100  (44)
-n   = 010100
n&-n = 000100  (4)

这个技巧常用于树状数组（Binary Indexed Tree）的实现中。

技巧五：交换两个数

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

原理：利用异或的自反性。不过在实际编程中，建议使用临时变量，代码更清晰。

技巧六：判断第 n 位是否为 1

boolean isBitSet(int num, int n) {
    return (num & (1 << n)) != 0;
}

技巧七：设置第 n 位为 1

int setBit(int num, int n) {
    return num | (1 << n);
}

技巧八：清除第 n 位

int clearBit(int num, int n) {
    return num & ~(1 << n);
}

技巧九：翻转第 n 位

int toggleBit(int num, int n) {
    return num ^ (1 << n);
}

经典算法应用

应用一：只出现一次的数字（LeetCode 136）

问题描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现一次的元素。

解题思路：利用异或的性质——相同元素异或结果为 0，任何数与 0 异或结果为其本身。将数组中所有元素异或，出现两次的元素互相抵消，最终结果就是只出现一次的元素。

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

复杂度分析：时间复杂度 O(n)，空间复杂度 O(1)。

应用二：只出现一次的数字 II（LeetCode 137）

问题描述：给定一个整数数组，除一个元素只出现一次外，其余每个元素都出现了三次。找出那个只出现一次的元素。

解题思路：统计每一位上 1 出现的次数，如果某一位上 1 的个数不是 3 的倍数，说明目标数在该位为 1。

public int singleNumber(int[] nums) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        int count = 0;
        for (int num : nums) {
            if ((num >> i & 1) == 1) {
                count++;
            }
        }
        if (count % 3 != 0) {
            result |= (1 << i);
        }
    }
    return result;
}

更优化的解法使用有限状态机思想：

public int singleNumber(int[] nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    return ones;
}

应用三：只出现一次的数字 III（LeetCode 260）

问题描述：给定一个整数数组，恰好有两个元素只出现一次，其他元素都出现两次。找出这两个元素。

解题思路：

先对所有元素异或，得到两个目标元素的异或结果 xor
找到 xor 中任意为 1 的位（这一位上两个目标元素不同）
根据这一位将数组分成两组，分别异或

public int[] singleNumber(int[] nums) {
    // 第一步：异或所有元素
    int xor = 0;
    for (int num : nums) {
        xor ^= num;
    }
    
    // 第二步：找到最右边的 1
    int diff = xor & (-xor);
    
    // 第三步：分组异或
    int a = 0, b = 0;
    for (int num : nums) {
        if ((num & diff) == 0) {
            a ^= num;
        } else {
            b ^= num;
        }
    }
    
    return new int[]{a, b};
}

应用四：丢失的数字（LeetCode 268）

问题描述：给定一个包含 [0, n] 中 n 个数的数组 nums，找出 [0, n] 范围内没有出现在数组中的那个数字。

解题思路：利用异或运算，将数组中所有数字与 [0, n] 异或，最终结果就是缺失的数字。

public int missingNumber(int[] nums) {
    int n = nums.length;
    int result = n;
    for (int i = 0; i < n; i++) {
        result ^= i ^ nums[i];
    }
    return result;
}

应用五：2 的幂（LeetCode 231）

问题描述：判断一个整数是否是 2 的幂次方。

public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

应用六：位 1 的个数（LeetCode 191）

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

应用七：比特位计数（LeetCode 338）

问题描述：给定整数 n，对于 0 <= i <= n 的每个 i，计算其二进制表示中 1 的个数，返回一个数组。

解题思路：使用动态规划 + 位运算。对于数字 i，其 1 的个数等于 i >> 1 的 1 的个数加上最后一位是否为 1。

public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i >> 1] + (i & 1);
    }
    return bits;
}

另一种思路：bits[i] = bits[i & (i - 1)] + 1，即去掉最低位 1 后的结果加 1。

public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bits[i] = bits[i & (i - 1)] + 1;
    }
    return bits;
}

状态压缩

位运算常用于状态压缩，将多个状态用二进制位表示，从而节省空间或简化逻辑。

子集枚举

用整数的每一位表示对应元素是否被选中：

// 枚举 {0, 1, 2, ..., n-1} 的所有子集
void enumerateSubsets(int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        // 处理子集 mask
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                // 元素 i 在子集中
            }
        }
    }
}

N 皇后问题（位运算优化）

使用位运算可以大幅优化 N 皇后问题的求解速度：

class Solution {
    private int count = 0;
    
    public int totalNQueens(int n) {
        solve(0, 0, 0, n);
        return count;
    }
    
    // cols: 列占用，diag1: 主对角线占用，diag2: 副对角线占用
    private void solve(int row, int cols, int diag1, int diag2, int n) {
        if (row == n) {
            count++;
            return;
        }
        
        // 可放置的位置（1 表示可放置）
        int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
        
        while (available != 0) {
            // 取最低位的 1 作为放置位置
            int pos = available & (-available);
            available &= (available - 1);  // 移除该位置
            
            solve(row + 1, 
                  cols | pos, 
                  (diag1 | pos) << 1, 
                  (diag2 | pos) >>> 1, 
                  n);
        }
    }
}

Python 中的位运算

Python 的位运算语法与 Java 类似，但需要注意 Python 整数没有固定位数：

# 基本位运算
a = 12  # 1100
b = 10  # 1010

print(a & b)   # 8 (1000)
print(a | b)   # 14 (1110)
print(a ^ b)   # 6 (0110)
print(~a)      # -13
print(a << 2)  # 48
print(a >> 2)  # 3

# 二进制转换
print(bin(12))        # '0b1100'
print(int('1100', 2)) # 12

# Python 特有：位长度
n = 12
print(n.bit_length())  # 4（需要的最少位数）
print(bin(n).count('1'))  # 2（1 的个数）

常见错误与注意事项

1. 运算符优先级

位运算符的优先级低于比较运算符，容易出错：

// 错误：先计算 n & 1 == 1，相当于 n & (1 == 1)
if (n & 1 == 1) { ... }

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

2. 移位范围

在 Java 中，int 是 32 位，移位操作会对移位数取模 32：

int a = 1;
int b = a << 32;  // 相当于 a << 0 = a
int c = a << 33;  // 相当于 a << 1 = 2

3. 负数右移

算术右移会保留符号位：

int a = -8;  // 11111111111111111111111111111000
int b = a >> 1;  // -4，符号位不变

4. 无符号整数

Java 没有无符号整数类型，但可以使用 Integer.toUnsignedLong() 或 Integer.parseUnsignedInt() 处理：

int a = -1;  // 全 1
long unsigned = Integer.toUnsignedLong(a);  // 4294967295

练习题推荐

难度	题目	知识点
简单	LeetCode 136：只出现一次的数字	异或性质
简单	LeetCode 191：位 1 的个数	汉明重量
简单	LeetCode 231：2 的幂	2 的幂判断
简单	LeetCode 268：丢失的数字	异或应用
中等	LeetCode 137：只出现一次的数字 II	位计数
中等	LeetCode 260：只出现一次的数字 III	分组异或
中等	LeetCode 338：比特位计数	位运算 + DP
困难	LeetCode 52：N 皇后 II	状态压缩

小结

位运算是一种高效且优雅的编程技巧，本章介绍了：

基础知识：二进制表示、原码反码补码、六种位运算符
核心技巧：判断奇偶、2 的幂、汉明重量、Lowbit 等
经典应用：只出现一次的数字系列、丢失数字等
状态压缩：子集枚举、N 皇后优化

位运算的魅力在于用最底层的操作解决复杂的问题，掌握这些技巧不仅能提升代码效率，还能开拓解题思路。在实际编程中，要根据场景选择是否使用位运算——有时清晰的代码比微小的性能提升更重要。

参考资料

Bit Twiddling Hacks
《算法导论》
LeetCode 位运算专题

二进制基础​

二进制表示法​

原码、反码与补码​

位运算符详解​

按位与（AND）- &​

按位或（OR）- |​

按位异或（XOR）- ^​

按位取反（NOT）- ~​

左移运算 - <<​

右移运算 - >> 和 >>>​

经典位运算技巧​

技巧一：判断奇偶性​

技巧二：判断是否为 2 的幂​

技巧三：统计二进制中 1 的个数（汉明重量）​

技巧四：获取最低位的 1（Lowbit）​

技巧五：交换两个数​

技巧六：判断第 n 位是否为 1​

技巧七：设置第 n 位为 1​

技巧八：清除第 n 位​

技巧九：翻转第 n 位​

经典算法应用​

应用一：只出现一次的数字（LeetCode 136）​

应用二：只出现一次的数字 II（LeetCode 137）​

应用三：只出现一次的数字 III（LeetCode 260）​

应用四：丢失的数字（LeetCode 268）​

应用五：2 的幂（LeetCode 231）​

应用六：位 1 的个数（LeetCode 191）​

应用七：比特位计数（LeetCode 338）​

状态压缩​

子集枚举​

N 皇后问题（位运算优化）​

Python 中的位运算​

常见错误与注意事项​

1. 运算符优先级​

2. 移位范围​

3. 负数右移​

4. 无符号整数​

练习题推荐​

小结​

参考资料​