位运算之2的幂数

高效代码中底层框架经常会使用位运算来提高算法的计算效率.
一般应用开发中并不太推荐使用复杂的位运算逻辑, 其一: 过于烧脑的位运算可读性,维护性差些, 其二: 一般的编译器会对于相关的表达式进行优化,直接编译出位运算相关的代码.
不过, 学习位运算对于开发思维还是很有好处的, 实际生产中底层框架使用云运算也很常见.

今天的算法是关于 幂数

输入整数 n , 算法是判断整数是不是2的幂数, 输出 bool (true/false); 要求: 时间复杂度为 O(1) 

解析: 一定与位运算相关,直觉 哈哈

其实这样的题, 不会的话, 先查找规律, 枚举几个, 所谓的 归纳演绎法 学习或者探寻未知的知识,这种思路很重要!!

幂数的规律

2^0  0 001
2^1  0 010
2^2  0 100
2^3  1 000
2^4  10 000
2^5  100 000
...

也就是: 能被2^N整除（N >= 1），则a的二进制表示中，低N位全为0.

解决的话, 一般可以尝试一些特殊值 比如 整数的二进制全是 0 或者 全是 1 , 或者与本身做处理, 或这本身的差值做处理.

尝试过特殊值后发现不能解决这个问题, 再尝试与自身的处理

举例:

4 & (4 - 1) == 0

4 & 3     == 0
2 & 1     == 0
8 & 7     == 0
16 & 15   == 0

0 100
'与' 上
0 011

也就是得到 如下的判断公式 :

n & (n-1)

可以使用这个计算器对比一下: https://tool.lu/calc/

升级版

• 4 的幂

参考

• 位运算有什么奇技淫巧？