位运算技巧：常用位操作、状态压缩、经典例题

位运算这东西，说实话，很多同学觉得它又偏又难。但我在实际项目中遇到过好几次——内存不够用、性能卡脖子，最后都是靠位运算救回来的。说白了，位运算就是计算机的“母语”，你想想看，CPU 处理位操作比加减乘除快多了。

这一章，我会带你系统梳理位运算的核心技巧。从最基础的位操作，到状态压缩这种高级玩法，再到两道经典面试题。嗯，咱们一步步来。

一、位运算基础操作

先过一遍最常用的位操作。我个人习惯把它们分成三类：

操作	符号	说明	示例
按位与	&	同1为1，否则为0	5 & 3 = 1 (101 & 011 = 001)
按位或	|	有1为1，否则为0	5 | 3 = 7 (101 | 011 = 111)
按位异或	^	相同为0，不同为1	5 ^ 3 = 6 (101 ^ 011 = 110)
取反	~	0变1，1变0	~5 = -6 (补码表示)
左移	<<	左移n位，低位补0	5 << 1 = 10
右移	>>	右移n位，高位补符号位	5 >> 1 = 2

这里有个小技巧：左移1位相当于乘以2，右移1位相当于除以2。我在做性能优化时，经常用移位代替乘除法，能省不少时钟周期。

二、常用位操作技巧

光知道基础操作还不够，得会用。下面这几个技巧，我建议你背下来——面试和实战都经常用到。

1. 判断奇偶

// 偶数返回0，奇数返回1
int isOdd(int x) {
    return x & 1;
}

为什么？因为二进制最低位是1就是奇数，是0就是偶数。比取模运算快多了。

2. 交换两个数

// 不用临时变量交换 a 和 b
a ^= b;
b ^= a;
a ^= b;

这个技巧我第一次看到时觉得挺酷的。但说实话，实际项目中我很少这么写——可读性太差了。不过面试时偶尔露一手，能加分。

3. 获取最低位的1

// 返回 x 中最低位的1所代表的值
int lowbit(int x) {
    return x & (-x);
}

这个在树状数组里特别常用。我曾经在写一个日志分析系统时，用这个技巧把某个 O(n²) 的操作优化到了 O(n log n)。

4. 清除最低位的1

// 将 x 的最低位的1变成0
x = x & (x - 1);

这个技巧在统计二进制中1的个数时特别好用。每次清除一个1，直到x变成0，循环次数就是1的个数。

三、状态压缩：用整数表示集合

状态压缩，说白了就是用二进制位来表示状态。比如一个集合有 n 个元素，每个元素选或不选，就可以用一个 n 位的二进制数来表示。

举个例子：假设有 3 个元素 {a, b, c}，那么：

• 000 = {}（空集）
• 001 = {a}
• 010 = {b}
• 011 = {a, b}
• ...以此类推

这样，一个 int 类型（32位）就能表示最多 32 个元素的子集。我在做旅行商问题（TSP）时，就是用状态压缩把指数级的状态存下来的。

状态压缩的常用操作

操作	代码	说明
检查第i位是否为1	(mask >> i) & 1	判断元素i是否在集合中
将第i位置为1	mask | (1 << i)	将元素i加入集合
将第i位置为0	mask & ~(1 << i)	将元素i从集合中移除
翻转第i位	mask ^ (1 << i)	切换元素i的状态

四、经典例题

例题1：只出现一次的数字

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

这道题，我第一次做的时候想的是用哈希表。但面试官说：能不能不用额外空间？

嗯，这时候异或就派上用场了。异或有个重要性质：a ^ a = 0，a ^ 0 = a。而且异或满足交换律和结合律。

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

为什么能行？因为成对出现的数字异或后变成0，最后剩下的就是那个只出现一次的数字。时间复杂度 O(n)，空间复杂度 O(1)。

例题2：子集枚举

题目：给定一个不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

这道题，用状态压缩来做特别直观。假设数组有 n 个元素，那么子集总数就是 2ⁿ 个。每个子集对应一个 n 位的二进制数。

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    
    // 枚举所有状态，从0到2^n - 1
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();
        
        // 检查每一位
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subset.add(nums[i]);
            }
        }
        result.add(subset);
    }
    return result;
}

这个代码的核心逻辑就两行：外层循环枚举所有状态，内层循环检查每一位。我建议你把这个模板背下来——很多状态压缩的题目都是这个套路。

五、知识体系总览

下面这张图，是我自己总结的位运算知识体系。你可以把它当作学习路线图：

六、避坑指南

最后，分享几个我踩过的坑：

• 优先级问题：位运算符的优先级比比较运算符低。比如 if (x & 1 == 0) 会被解析成 if (x & (1 == 0))。我建议你永远加括号，别省这个功夫。
• 有符号右移：C/C++ 中右移负数时，高位补的是符号位，不是0。如果你想要逻辑右移（高位补0），用 >>>（Java）或 unsigned 类型。
• 溢出问题：1 << 31 在 int 类型中会溢出。如果你要操作第31位，用 1L << 31 或者 1U << 31。

好了，位运算的核心内容就这些。记住：基础操作是工具，常用技巧是招式，状态压缩是心法。三者结合，你就能在算法题和实际项目中游刃有余了。