Amazon ：最简捷的方法判断一个数是否为2的幂

最简捷的方法判断一个数是否为2的幂

EE飘过，我打酱油的……反选看答案
二进制看结尾是不是0？

楼上说的是如何判断是否2的倍数，如果是2的整数幂，那应该是除了第一个1以外后面全是零。

这个我主要是不知道怎么才算简捷，如果是指时间复杂度的话，就反复右移就好了，O(logn)，难道还会有O(1)的解法？

楼上说的是如何判断是否2的倍数，如果是2的整数幂，那应该是除了第一个1以外后面全是零。

这个我主要是不知道怎么才算简捷，如果是指时间复杂度的话，就反复右移就好了，O(logn)，难道还会有O(1)的解法？
Jawley 发表于 2011-8-5 06:34

    有，a & (a - 1)

有，a & (a - 1)
wwwyhx 发表于 2011-8-5 08:03

果然精妙

不过隐约觉得还是有点投机取巧的感觉……其实对一个为n的数做减法，本身的复杂度就是O(logn)了……

楼上说的是如何判断是否2的倍数，如果是2的整数幂，那应该是除了第一个1以外后面全是零。

这个我主要是不知道怎么才算简捷，如果是指时间复杂度的话，就反复右移就好了，O(logn)，难道还会有O(1)的解法？
Jawley 发表于 2011-8-4 17:34

嗯嗯 我就那个意思
4L牛
你们CS果然不是一般人能弄得

回复 5# Jawley
你说的对，如果把操作一位作为O(1)的话，其实减法和按位&复杂度都是O(logn)，应该没有比这更好的办法。上面那种操作确实很巧妙，更普遍的应用是在统计一个数的二进制表示中1的个数：
while(n) {
    n = n & (n-1);
    count++;
}

有，a & (a - 1)
wwwyhx 发表于 2011-8-5 08:03

    Cool!

转化为二进制，最左边为1，且其他位为0即是。