LeetCode 137题位运算解法逻辑深度解析
2026-6-14
理解LeetCode 137题的位运算解法：只出现一次的数字II
先贴出你提到的核心代码：
class Solution { public: int singleNumber(vector<int>& nums) { int ones = 0, twos = 0; for(int i=0; i < nums.size(); i++) { ones = (ones ^ nums[i]) & ~twos; twos = (twos ^ nums[i]) & ~ones; } return ones; } };
这个解法的核心是用ones和twos两个变量，分别记录二进制每一位出现1次和2次的状态，每一位的状态变化遵循「00→01→10→00」的循环（对应该位被0次、1次、2次、3次覆盖）。你困惑的点在于计算顺序——代码中是先更新ones，再用更新后的ones计算twos，这是关键，下面用数字3（二进制11）的两次出现过程来拆解：
第一次遇到3：
初始状态：ones=0，twos=0
- 更新ones：
(0 ^ 11) & ~0 = 11 & 全1 = 11→ 此时ones=11（对应该位出现1次） - 更新twos：
(0 ^ 11) & ~11 = 11 & 全0 = 0→ twos保持0
第二次遇到3：
注意，这里计算twos时用的是刚更新后的ones：
- 先更新ones：
(11 ^ 11) & ~0 = 0 & 全1 = 0→ ones变为0（该位出现次数从1次清零，准备转移到twos） - 再更新twos：
(0 ^ 11) & ~0 = 11 & 全1 = 11→ twos变为11（该位出现次数变为2次）
你之前误以为计算twos时用的是更新前的ones（11），但实际上代码里ones已经先被更新成0了，所以~ones是全1，自然能把3加入twos桶。
状态转移表（单二进制位）
我们可以把每一位的状态单独拎出来看，更清晰：
| 当前(ones位, twos位) | 遇到1时新状态 | 遇到0时新状态 |
|---|---|---|
| (0, 0) | (1, 0) | (0, 0) |
| (1, 0) | (0, 1) | (1, 0) |
| (0, 1) | (0, 0) | (0, 1) |
因为题目中除了目标元素，其他元素都出现3次，所以这些元素的每一位都会走完「00→01→10→00」的循环，最终回到00状态；而目标元素只出现1次，对应的位会停在「01」状态，也就是ones中对应的位为1，所以最终返回ones就是答案。
内容的提问来源于stack exchange，提问作者Gopika J
相关产品推荐
相关产品推荐
