1. 问题背景与核心挑战LeetCode 137题只出现一次的数字 II是位运算领域的经典问题。题目给定一个整数数组其中某个元素只出现一次其余每个元素均出现三次要求找出那个单一的数字。这个问题的常规解法可能包括哈希表统计或数学计算但位运算解法才是真正考验算法功底的方案。我第一次遇到这个问题时尝试用哈希表记录每个数字的出现次数。虽然这种方法时间复杂度是O(n)但空间复杂度也是O(n)不符合题目进阶要求中常数空间复杂度的提示。这促使我深入研究位运算的解法发现其中蕴含着精妙的二进制位操作逻辑。2. 位运算解法原理剖析2.1 二进制位统计思想位运算解法的核心思路是统计所有数字在各个二进制位上1出现的次数。由于除了目标数字外其他数字都出现三次因此每个位上1的总次数应该是3的倍数可能加上目标数字在该位的1。具体来说对于32位整数中的每一位初始化一个长度为32的数组count遍历所有数字统计每个数字在每一位上是否为1最后检查count数组如果某位的计数不是3的倍数说明目标数字在该位是12.2 位运算优化技巧直接使用数组统计虽然直观但空间效率不高。更优雅的做法是用两个整数变量ones和twos来记录状态ones表示某位出现1的次数是否为1次模3余1twos表示某位出现1的次数是否为2次模3余2每次处理新数字时通过位运算更新这两个变量的状态ones (ones ^ num) ~twostwos (twos ^ num) ~ones这种状态机的设计非常巧妙通过异或和与运算实现了模3计数器。3. 完整代码实现与逐行解析3.1 Python实现版本def singleNumber(nums): ones, twos 0, 0 for num in nums: ones (ones ^ num) ~twos twos (twos ^ num) ~ones return ones代码解析初始化ones和twos为0遍历数组中的每个数字num更新ones先用异或记录出现奇数次的位再用与运算确保该位不在twos中更新twos同样先用异或记录再确保该位不在ones中最终ones保存的就是只出现一次的数字3.2 状态转移过程示例以输入[2,2,3,2]为例初始状态ones0, twos0处理2ones (0^2)~0 2twos (0^2)~2 0处理2ones (2^2)~0 0twos (0^2)~0 2处理2ones (0^2)~2 0twos (2^2)~0 0处理3ones (0^3)~0 3twos (0^3)~3 0 最终返回ones34. 算法复杂度与边界条件4.1 时间复杂度分析该算法只需要一次线性扫描数组时间复杂度为O(n)其中n是数组长度。对于每个数字的处理都是常数时间操作32位整数的位运算。4.2 空间复杂度优势仅使用了两个额外整数变量ones和twos空间复杂度是O(1)远优于哈希表解法的O(n)。4.3 边界条件处理需要注意的特殊情况包括空数组题目保证有解实际可以不做处理最大/最小整数32位整数范围是-2^31到2^31-1算法自动处理所有数字都出现三次题目保证有唯一解5. 位运算技巧扩展应用5.1 通用解法框架这类问题可以抽象为找出在n次重复中出现一次的数字。对于一般情况我们可以设计一个状态机用k个变量来记录模n的余数状态。5.2 类似题目推荐LeetCode 136只出现一次的数字其他数字出现两次LeetCode 260只出现一次的数字 IIILeetCode 477所有汉明距离总和位统计思想5.3 位运算优化技巧在实际编码竞赛中位运算技巧还包括快速判断奇偶num 1交换两个数a ^ b; b ^ a; a ^ b取绝对值(num ^ (num 31)) - (num 31)6. 常见错误与调试技巧6.1 典型错误模式混淆ones和twos的更新顺序必须先更新ones再更新twos忽略负数的二进制表示Python使用补码表示但算法自动处理错误初始化ones和twos必须初始化为06.2 调试建议打印中间状态在处理每个数字后打印ones和twos的值小规模测试先用简单例子验证如[1,1,1,2]边界测试测试最大/最小整数和零的情况7. 性能优化与替代方案7.1 位统计法的变体另一种思路是分别计算每一位上1的个数然后模3def singleNumber(nums): result 0 for i in range(32): mask 1 i count 0 for num in nums: if num mask: count 1 if count % 3: result | mask return result if result (1 31) else result - (1 32)这种方法更直观但效率稍低32次循环。7.2 数学方法利用集合和数学计算sum(set(nums))*3 - sum(nums) 然后除以2 但需要注意整数溢出问题。8. 实际应用场景这类位运算技巧在以下场景有实际应用错误检测与纠正奇偶校验位数据压缩位级编码密码学位操作是许多加密算法的基础硬件编程直接操作寄存器位我在实际工作中曾用类似技巧处理过设备状态寄存器需要从多个重复状态信号中提取异常事件。位运算解法的高效性在这种底层系统编程中尤为重要。9. 学习路径建议对于想精通位运算的开发者我建议的学习顺序掌握基本位操作与、或、非、异或、移位理解补码表示特别是负数的二进制形式练习简单题目如136题异或技巧挑战中等难度如本问题和260题研究高级应用布隆过滤器、位图等10. 个人实战心得经过多次练习这类题目我总结了几个关键点画状态转移图有助于理解ones/twos的更新逻辑对于复杂位运算先写注释再写代码测试时要包含正数、负数和零的混合情况在竞赛中这类技巧往往能大幅提升性能最后分享一个小技巧当不确定位运算结果时可以先用bin()函数打印数字的二进制表示这在调试时非常有用。例如print(bin(ones), bin(twos))可以清晰看到状态变化过程。