统计二进制中 1 的个数与常用位运算
哪些公司问过
答案要点
- n & (n-1) 每次消去最低位的 1,循环计数,次数等于 1 的个数
- 其他方法:逐位判断、查表、并行位计数;GCC 内建 __builtin_popcount(硬件 popcnt)
- 判断 2 的幂:n > 0 && (n & (n-1)) == 0
- 取最低位的 1:n & -n;判断奇偶:n & 1
- 置位 |=,清零 &= ~,翻转 ^=;嵌入式中常用于操作寄存器
易错点
- 对负数用有符号右移逐位判断,造成死循环
- 判断 2 的幂时漏掉 n 大于 0 的条件
- 混淆按位与和逻辑与
- 忘了运算符优先级,位运算要加括号
面试官常见追问
- 为什么 n & (n-1) 能消去最低位的 1?
- 位运算在嵌入式里有哪些常用场景?
- 负数怎么统计 1 的个数?
- 如何判断一个数是不是 2 的幂?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。