给定一个整数 x,如何检测它是不是 2 幂?即是否能够表示成 2k 的形式,其中 k 是非负整数。

算法 A

因为 2 的幂不包含 2 以外的素因子,我们有:

  1. x 必须是正整数。
  2. 1 = 20 满足要求。
  3. 如果 x 是偶数,就一直除以 2,直到 x 变为奇数为止。
  4. 此时,如果 x = 1,则满足要求,否则就不满足要求。

对应的 C 语言程序如下所示:

int isPowerOf2a(long x)
{
  if (x <= 0) return 0;
  while (x % 2 == 0) x /= 2;
  return x == 1;
}

算法 B

在二进制计算机上,以上对 2 取模和除以 2 的运算可以使用按位与和向右移位运算代替:

int isPowerOf2b(long x)
{
  if (x <= 0) return 0;
  while ((x & 1) == 0) x >>= 1;
  return x == 1;
}

算法 A 和算法 B 的时间复杂度都是 O(log n)。

算法 C

如果 x = 2k,则它的二进制表示只含有一个 1,后面跟着 k 个 0。而且 x-1 由 k 个 1 组成。因此,(x & x-1) == 0。如果 x 是正整数,且不是 2 的幂,则 x 的二进制表示包含不止一个 1。x-1 把 x 从 ???10...0 变为 ???01...1,除了最右边的 1 变为 0 以外,其余的 1 不变,所以 (x & x-1) != 0。因此,我们有:

int isPowerOf2c(long x) { return x > 0 && (x & x-1) == 0; }

1 10 11 100 101 110 111 1000 1001 1010 x
0 01 10 011 100 101 110 0111 1000 1001 x-1
0 00 10 000 100 100 110 0000 1000 1000 x & x-1

如果 x 是正整数,则 x & x-1 把 x 的二进制表示最右端的 1 变为 0。

算法 D

在二进制计算机上,如果负数以补码(即反码加 1)表示,我们有以下算法:

int isPowerOf2d(long x) { return x > 0 && (x & -x) == x; }

01 010 011 0100 0101 0110 0111 01000 01001 01010 x
11 110 101 1100 1011 1010 1001 11000 10111 10110 -x
01 010 001 0100 0001 0010 0001 01000 00001 00010 x & -x

如果 x 是正整数,则 x & -x 是 2 的幂,其二进制表示只包含一个 1,且这个 1 是 x 最右端的 1。也就是说,x & -x 把 x 的二进制表示中除最右端以外的 1 都变为 0。

算法 C 和算法 D 的时间复杂度都是 O(1)。

算法 A 是通用的,可以用于十进制计算机。算法 B、C 和 D 只能用于二进制计算机。算法 D 还要求负数以补码表示。

测试程序

#include <stdio.h>
#include <time.h>

// 上述 4 个函数放在这里

void test(char id, int (*isPowerOf2)(long), long max)
{
  long z = 0;
  clock_t t = clock();
  for (long i = 0; i <= max; i++)
    if (isPowerOf2(i)) z++;
  printf("isPowerOf2%c: %5.1lf seconds, %ld\n",
    id, (double)(clock()-t)/CLOCKS_PER_SEC, z);
}

int main(void)
{
  long max = 12345678901;
  test('a', isPowerOf2a, max);
  test('b', isPowerOf2b, max);
  test('c', isPowerOf2c, max);
  test('d', isPowerOf2d, max);
  return 0;
}

编译和运行

$ clang -O isPowerOf2.c && ./a.out

isPowerOf2a:  49.7 seconds, 34
isPowerOf2b:  41.5 seconds, 34
isPowerOf2c:  29.7 seconds, 34
isPowerOf2d:  32.7 seconds, 34

算法 C 和算法 D 的速度差不多,而算法 A 和算法 B 也不算太慢。