m**r 发帖数: 574 | 1 public int isPowerOfTwo(int x)
{
return(
x == 1 || x == 2 || x == 4 || x == 8 || x == 16 || x == 32 ||
x == 64 || x == 128 || x == 256 || x == 512 || x == 1024 ||
x == 2048 || x == 4096 || x == 8192 || x == 16384 ||
x == 32768 || x == 65536 || x == 131072 || x == 262144 ||
x == 524288 || x == 1048576 || x == 2097152 ||
x == 4194304 || x == 8388608 || x == 16777216 ||
x == 33554432 || x == 67108864 || x == 134217728 ||
x == 268435456 || x == 536870912 || x == 1073741824 ||
x == 2147483648);
);
}
这种算O(1)吧,算是最快了吗? |
r******l 发帖数: 10760 | 2 你这么算的话,几乎所有问题都可以算是O(1)的了。因为精度有限制,即使O(2^n)这种
指数级的复杂度,其实也不会超过2^2147483647这个常数(假设n是32位整数)。 |
j**********3 发帖数: 3211 | |
m**r 发帖数: 574 | 4 谢谢上面的回复
要是这样写呢?这样写O(n)我直接不会说了
public in isPowerOfTwo(int x)
{
while (((x & 1) == 0) && x > 1)
x >>= 1;
return (x == 1);
} |
e*****i 发帖数: 182 | 5 (x & (x-1)) == 0
【在 m**r 的大作中提到】 : public int isPowerOfTwo(int x) : { : return( : x == 1 || x == 2 || x == 4 || x == 8 || x == 16 || x == 32 || : x == 64 || x == 128 || x == 256 || x == 512 || x == 1024 || : x == 2048 || x == 4096 || x == 8192 || x == 16384 || : x == 32768 || x == 65536 || x == 131072 || x == 262144 || : x == 524288 || x == 1048576 || x == 2097152 || : x == 4194304 || x == 8388608 || x == 16777216 || : x == 33554432 || x == 67108864 || x == 134217728 ||
|
n*****n 发帖数: 5277 | |
m*****k 发帖数: 18 | 7 should add: x != 0
【在 e*****i 的大作中提到】 : (x & (x-1)) == 0
|
s********k 发帖数: 2352 | 8 干嘛不弄个数组放进去。。。
【在 m**r 的大作中提到】 : public int isPowerOfTwo(int x) : { : return( : x == 1 || x == 2 || x == 4 || x == 8 || x == 16 || x == 32 || : x == 64 || x == 128 || x == 256 || x == 512 || x == 1024 || : x == 2048 || x == 4096 || x == 8192 || x == 16384 || : x == 32768 || x == 65536 || x == 131072 || x == 262144 || : x == 524288 || x == 1048576 || x == 2097152 || : x == 4194304 || x == 8388608 || x == 16777216 || : x == 33554432 || x == 67108864 || x == 134217728 ||
|
n***s 发帖数: 234 | 9 x > 0
【在 m*****k 的大作中提到】 : should add: x != 0
|