题目描述#

哎呀，这题听着就有点绕——给你一个整数数组 nums，里头除了某一个元素只出现 一次，其余每个元素都恰好出现 三次。咱要做的，就是把那个落单的家伙找出来返回。

而且题目还提了俩硬条件：时间得是 线性 的、空间只能用 常数级。也就是说，拿哈希表数次数那种 $O(n)$ 空间的偷懒办法，这回行不通哦。

思路#

咱第一眼看，这题的突破口藏在"三次“这个数字里。既然大部分元素都出现三次，那要是咱把所有数字的二进制按位摊开来看，每一个比特位上的 1，要么来自那些出现三次的数（贡献 3 的倍数个 1），要么来自那个只出现一次的落单数（贡献 0 个或 1 个 1）。

所以本姑娘的招数是这样：逐位统计，再对 3 取余。咱挨个枚举第 0 到第 31 这 32 个比特位，对每一位，把数组里所有数字在这一位上的取值（(v >> i) & 1，不是 0 就是 1）全加起来得到 cnt。出现三次的那些数在这一位上贡献的 1 必然是 3 的整数倍，所以 cnt %= 3 一抹，剩下的就只剩落单数在这一位的真实取值了——余 1 说明答案这一位是 1，余 0 说明是 0。

把每一位还原出来的结果用 cnt << i 移回原位、累加进 ans，32 位全扫完，那个只出现一次的数字就被咱一位一位拼回来啦。

这里有个容易被忽略的细节：代码用的是 int32，第 31 位正好是符号位。靠着补码的特性，当落单数是负数时，符号位那一格 cnt << 31 会把 ans 自动变成对应的负值，所以负数也能正确还原，不用额外特判——这点设计得挺巧妙。整个算法只用了几个计数变量，空间是 $O(1)$；外层固定跑 32 位、内层扫一遍数组，时间是 $O(32n) = O(n)$，两个硬条件都稳稳达标。

照片当然不是现实，但只要拼够了 32 张"每一位的快照”，落单的那个数也就显形了——位运算的浪漫大概就在这儿吧～

知识边界#

• 逐位投票 + 模 3：本题核心手法。利用"出现 3 次的数在每个比特位上贡献 3 的倍数个 1"，对每位计数后 % 3 即可剥离出答案在该位的取值。这是从经典异或（出现两次）推广到出现三次的关键思路。
• 取指定位：(v >> i) & 1 先右移再按位与，取出第 i 位的值；cnt << i 再把统计结果移回原位累加。
• 符号位与补码：用 int32 时第 31 位是符号位，借补码能让负数答案自然还原，无需特判负数——这点容易想漏哦。
• 常数空间约束：题目卡死 $O(1)$ 空间，所以哈希表计数法不可用；逐位统计法只占常数个变量，正好契合。

代码#

下面这版咱一行没动，逐位投票再模 3：

func singleNumber(nums []int) int {
	ans := int32(0)
	for i := 0; i < 32; i++ {
		cnt := 0
		for _, v := range nums {
			cnt += (v >> i) & 1
		}
		cnt %= 3

		ans += int32(cnt << i)
	}
	return int(ans)
}

好啦，位运算章节又添一道狠活儿～咱去整理今天的照片咯，下次再来收拾更刁钻的比特题！