Python中32位掩码法解LeetCode Single Number II的原理疑问

解法代码 #

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        number = 0
        for i in range(32):
            count = 0
            for num in nums:
                if num & (1 << i):
                    count += 1
            if count % 3:
                number |= (1 << i)
        
        if number & (1 << 31):
            number -= (1 << 32)

        return number

核心疑问解答 #

1. 为什么能假设数字适配32位，且1<<31是符号位？ #

LeetCode这类编程题的输入整数通常遵循32位有符号整数规范，范围限定在[-2^31, 2^31-1]。解法基于这个题目隐含的输入前提，模拟32位有符号数的行为，1<<31对应32位有符号数的最高位（符号位），是符合题目场景的合理假设。

2. 为何仅循环range(32)？次数更少不行吗？ #

不行。32位有符号数的所有有效信息都集中在0到31位：0-30位是数值位，31位是符号位。如果循环次数少于32次，会漏掉高位（尤其是符号位）的统计，导致负数或大正数的结果错误。比如输入负数时，符号位的统计是还原原数的关键，少循环必然丢失该信息。

3. 输入小整数（如2、3等）未占满32位时，检查第31位为何可靠？ #

小正数的31位在32位有符号数规则下是0，统计时num & (1<<31)的结果为0，对应count始终是0，count%3为0，不会对number的第31位产生修改。这种统一检查32位的逻辑，既能正确处理小整数，也能兼容负数的符号位统计，不会干扰结果正确性。

4. Python整数的任意精度特性为何未破坏该逻辑？ #

解法全程只关注0到31位的位信息，主动屏蔽了Python整数的高位特性：

• 统计阶段，num & (1<<i)仅提取当前数的第i位（i<32），更高位会被与运算过滤为0，不会计入统计；
• 最终转换阶段，通过number & (1<<31)判断是否为32位负数，再用number -= (1<<32)把32位无符号值转换为Python的负整数（相当于把0x80000000到0xFFFFFFFF映射为-2^31到-1）。
  Python的任意精度只是允许存储更大的数，但解法从未操作32位以外的位，因此不会破坏逻辑。

补充疑问解答 #

• 为何在Python中安全使用32位模拟？
  因为题目输入的整数范围是标准32位有符号数，解法严格只处理这32位的位信息，对Python的大整数特性做了“隔离”——只提取需要的位，最后再把32位结果转换为Python的整数表示，完全适配题目要求。

• 检查1<<31在Python中为何有意义？
  1<<31对应32位有符号数的符号位，解法通过该位判断统计出的number是否为32位下的负数。如果该位为1，说明原数是负数，需要把当前的无符号32位值转换为Python的负整数（Python负数用补码的任意精度形式表示，减2^32刚好完成这个转换）。

• Python整数的任意精度特性为何未破坏该逻辑？
  解法的位运算仅针对0-31位，更高位在统计时不会被计入（num & (1<<i)对i<32时，更高位都是0），最后转换负数的步骤也基于32位规则，和Python整数的高位无关。相当于把Python整数当作32位容器来用，只操作指定范围内的位，所以任意精度不会干扰结果。

内容的提问来源于stack exchange，提问作者Sourav Mandal