进阶 · 数论
是不是 2 的幂？
判断一个数是不是 2 的幂（1、2、4、8……）。一道短题，里面藏着一个漂亮的位运算技巧。
一句话答案正整数 n 是 2 的幂，当且仅当 n & (n - 1) 等于 0 —— 0 要单独处理，因为 0 & -1 也是 0，但 0 不是 2 的幂。
题目
输入: 一个整数 n（0 <= n <= 1000000）。
输出: 是 2 的幂输出 yes，否则 no。
样例:
| 输入 | 输出 |
|---|---|
8 | yes |
你的解答
「运行我的输入」用的自定义输入
判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。
卡住了？提示
提示 1 — 小心 0
0 不是 2 的幂，而且那个循环在 0 上永不终止。先处理 n < 1。
提示 2 — 位运算技巧（加分）
2 的幂只有一位是 1，所以 n > 0 时 (n & (n - 1)) == 0。纸上验算：8 = 1000，7 = 0111，与 = 0000。
题解（先自己试试！）
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n < 1) {
cout << "no" << endl;
return 0;
}
while (n % 2 == 0) n /= 2;
if (n == 1) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}位运算技巧是 O(1)，循环是 O(log n) —— 和素数判断的平方根捷径是同一种快感。
深度解析
为什么这样做对
2 的幂恰好只有一位是 1，所以 n & (n-1) 把它清掉之后结果必为 0。一个循环变成一条指令。
代价
O(1)，而反复除 2 是 O(log n)——何况编译器本来就是这么生成的。
常见错法
n & (n-1) == 0会被解析成n & ((n-1) == 0)，因为 == 比 & 优先。必须加括号。- 这个技巧会告诉你 0 是 2 的幂。要把 n <= 0 显式排除。
下一步
换个方向数位：数一数 1 的个数。
记住这两句
- n & (n-1) 清掉最低位的 1。
- == 比 & 优先——括号别省。
🐞 这段是错的 —— 点开,亲手让它挂一次
== 比 & 优先，这个判断根本不是本意
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n & (n - 1) == 0) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}