【题目描述】
Using O(1) time to check whether an integernis a power of2.
用O(1) 时间检测整数n是否是2的幂次。
【题目链接】
www.lintcode.com/en/problem/o1-check-power-of-2/
【题目解析】
简单点来考虑可以连除2求余，看最后的余数是否为1，但是这种方法无法在 O(1) 的时间内解出，所以必须要想点别的办法。2的整数幂若用二进制来表示，则其 中必只有一个1，其余全是0，那么怎么才能用一个式子把这种特殊的关系表示出来了？传统的位运算如按位与、按位或和按位异或等均无法直接求解，比较下x - 1和x的关系试试.以x=4为例。
0100 ==> 4
0011 ==> 3
两个数进行按位与就为0了.如果不是2的整数幂则无上述关系，反证法可证之。
【参考答案】
