整数二进制中 1 的个数
哪些公司问过
答案要点
- 逐位法:n&1 判断最低位后右移,循环次数等于位数,O(n)
- n&(n−1) 消去最低位的 1,循环次数等于 1 的个数,O(k)
- 负数处理:Java 用 >>>,C++ 转 unsigned,Python 先与 0xFFFFFFFF
- 算术右移负数会持续补 1,导致死循环
- 工程可用 Integer.bitCount、__builtin_popcount 等内建函数
易错点
- 负数用算术右移导致死循环
- Python 中直接对负数右移,结果不符合 32 位补码预期
- 把 n&(n−1) 的复杂度说成与位数相关
面试官常见追问
- 为什么 n&(n−1) 能消掉最低位的 1?
- 如何判断一个数是不是 2 的幂?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。