O(1) Check Power of 2
简单点来考虑可以连除2求余,看最后的余数是否为1,但是这种方法无法在 O(1) 的时间内解出,所以我们必须要想点别的办法了。2的整数幂若用二进制来表示,则其中必只有一个1,其余全是0,那么怎么才能用一个式子把这种特殊的关系表示出来了?传统的位运算如按位与、按位或和按位异或等均无法直接求解,我就不卖关子了,比较下和的关系试试?以为例。
除了考虑正整数之外,其他边界条件如小于等于0的整数也应考虑在内。在比较0和的值时,需要用括号括起来避免优先级结合的问题。
关于2的整数幂还有一道有意思的题,比如 Next Power of 2 - GeeksforGeeks,有兴趣的可以去围观下。