位运算

灵神题单：分享丨【算法题单】位运算（基础/性质/拆位/试填/恒等式/思维） - 讨论 - 力扣（LeetCode）

场景：

2 的幂

231. 2 的幂 - 力扣（LeetCode）

• 2的幂 n 的二进制特点：10 100 1000 -> 最高位为1，其他位为0，2的幂减一 (n−1) ：1 11 111，n&(n−1) 一定是 0
• 反之，如果 n 不是 2 的幂，那么 n 的二进制至少有两个 1，则把 n 减一后最高位必为 1，所以 n&(n−1) 必不为 0，例如：

1
2

9   = 1001
9−1 = 1000

4的幂

• 发现4^x = 2^2x，也就是如果是4的幂则必然是2的幂，前面知道如何判断 是否为2的幂，也就是要继续加条件限制即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

4的幂的二进制：
1
100
10000
⋮

2的幂但不是4的幂的二进制：
10
1000
100000
⋮

• 直观特点：True 的情况为 位数为奇数，False 的情况为 位数为偶数。如何尝试用与或非体现这个区别？…0101010….与即可。
• tips：把二进制数前面也补0带入思考： 100-> …00100。