判断整数是否为 2 的幂
哪些公司问过
答案要点
- 判断:n > 0 且 (n & (n-1)) == 0
- 原理:2 的幂二进制只有一位 1;n & (n-1) 清除最低位的 1
- 时间复杂度 O(1),优于循环除以 2 的 O(log n)
- 边界:0 和负数不是 2 的幂;1 是 2 的零次幂
- 等价写法:n & (-n) == n,取出最低位的 1
易错点
- 忘了判断 n 大于 0,把 0 当作 2 的幂
- 对负数没有处理
- 用浮点数 log2 判断,有精度问题
- 把 n & (n-1) 的作用说反
面试官常见追问
- 怎么统计一个数的二进制中 1 的个数?
- 怎么求大于等于 n 的最小 2 的幂?
- n & (-n) 是什么意思?
- 为什么哈希表容量常取 2 的幂?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。