5.判断整数是否为2的幂次方
5.1 题目
给出函数判断一个整数是不是2的n次方。请问 if 语句中应该如何书写？
5.2 深入解析
若 n 为 2 的幂，其二进制中恰好有一个 1（如 8 = 0b1000）。此时 n - 1 会把该位变 0、低位全变 1，n & (n - 1) 必为 0。反之，若 n 有多个 1 位，则 n & (n - 1) 不为 0。注意先排除 n <= 0。
时间复杂度 O(1)，常作为位运算基础题。
5.3 答题示例
// 判断一个整数是否为2的幂次方 public bool IsPowerOfTwo(int n) { // 如果 n <= 0，则不是2的幂次方 if (n <= 0) { return false; } // 如果 n & (n - 1) 等于 0，则是2的幂次方 return (n & (n - 1)) == 0; }思路：2 的幂在二进制中仅有一个 1；
n-1会把该位清 0、低位全置 1，故n & (n-1)为 0。若n有多个 1，则n & (n-1)仍非 0。先排除n<=0。
5.4 关键词联想
- 位运算
& - 二进制表示
n & (n - 1)消去最低位 1- 时间复杂度
O(1)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
