C语言统计两个整数二进制位不同的个数
哪些公司问过
答案要点
- 核心:a ^ b 的结果中1的位就是不同位,问题转化为统计1的个数(汉明距离)
- Kernighan 法:x &= x - 1 每次消去最低位的1,循环次数等于1的个数
- 逐位法:x & 1 判断后右移,循环位宽次;查表法、SWAR 分组相加可做到常数步
- 参数用 unsigned / uint32_t,对有符号负数右移是实现定义的,可能补1导致死循环
- 工程可用 __builtin_popcount(ll),时间 O(位宽) 或 O(1的个数),空间 O(1)
易错点
- 用 int 处理负数右移,可能因算术右移补符号位而死循环
- 忘记 a ^ b 这一步,直接分别统计两数的1个数相减,结果是错的
- __builtin_popcount 只接 unsigned int,64 位数要用 __builtin_popcountll
面试官常见追问
- 如果输入是两个长度不同的二进制字符串怎么办?
- x &= x - 1 为什么能消掉最低位的1?
- 如何判断一个数是不是2的幂?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。