【第三轮】7.24-7.31 CareerCup 5.4

5.4 Explain what the following code does: ((n & (n-1)) == 0).

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

The only way that n & n-1 == 0 is n -1 flip all bits in n.

When would this happen? only when n has the pattern 1+multiple 0s.
and 1+multiple 0s would only happen when n is 2^x (x >0)

So it is used to check whether n is power of 2

这个貌似最简单，就是判断n是不是2的x次方，相等布尔值为真，不相等为假。
n与n-1位相与要为0必须每一位都错位，稍微试一试两个数就猜到只有2的x次方时候满足

测试n是不是2的X次方


               

((n & (n - 1) == 0) will test if n is 0, 1 or the power of 2

to determine if n is a power of 2

check whether n is the power of 2

倒着推导，n & (n-1) == 0，就是判断n是不是2进制下2的倍数 或者 n是不是0

【解题思路】
本来想着是判断1的个数不大于1…其实也就是power of 2了……

check if n is power of 2