位运算之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/
升级版