回顾

在“图灵社区:检测 2 的幂”中,我给出了以下函数:

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

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

while ((x & 1) == 0) x >>= 1;

在 Arch Linux 64-bit 操作系统中使用 clang 编译器进行优化编译后,得到以下结果:

$ 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

反汇编

使用 objdump -d a.out 进行反汇编,经整理后得到:

可以看出,在 isPowerOf2a 函数中,clang 编译器优化x % 2x & 1,避免了除法运算。但是,x /= 2被优化为以下 4 条指令(在此之前,已经执行了z = x):

  1. z >>>= 63; // z = (x < 0) ? 1 : 0;
  2. z += x;     // z = (x < 0) ? (x+1) : x;
  3. z >>= 1;   // z /= 2;
  4. x = z;

这是为了处理负整数的情形。负整数用二进制补码表示时,算术右移 1 位的效果,相当于除以 2 时向负无穷大截断。而在主流的 C 编译器中,整数除法是向 0 截断的。

如果能够保证x是非负整数,x /= 2可以直接优化为x >>= 1。实际上,因为前面有:

if (x <= 0) return 0;

执行到这里时,x必定是非负整数,但是 clang 编译器的优化功能还没有达到这个水平。

使用无符号整数

把 isPowerOf2.c 中的所有 long 修改为 unsinged long 后,再次编译和运行,得到:

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

isPowerOf2a:  38.1 seconds, 34
isPowerOf2b:  38.9 seconds, 34
isPowerOf2c:  25.0 seconds, 34
isPowerOf2d:  32.9 seconds, 34

使用 objdump -d a.out 进行反汇编,整理后得到:

 0:
 1:
 2:
 3:
 4:
 5:
 6:
 7:
 8:
 9:
10:
11:
0000000000400520 <isPowerOf2a>:
  400520:  xor    %eax,%eax
  400522:  test   %rdi,%rdi
  400525:  je     400544
  400530:  mov    %rdi,%rax
  400533:  shr    %rdi
  400536:  test   $0x1,%al
  400538:  je     400530
  40053a:  cmp    $0x1,%rax
  40053e:  sete   %al
  400541:  movzbl %al,%eax
  400544:  retq   
0000000000400550 <isPowerOf2b>:
  400550:  xor    %eax,%eax
  400552:  test   %rdi,%rdi
  400555:  je     400574
  400560:  mov    %rdi,%rax
  400563:  shr    %rdi
  400566:  test   $0x1,%al
  400568:  je     400560
  40056a:  cmp    $0x1,%rax
  40056e:  sete   %al
  400571:  movzbl %al,%eax
  400574:  retq 

可见,对于非负整数,clang 编译器能够很好地优化x /= 2x >>= 1。与上一小节的使用有符号整数的 isPowerOf2b 函数对比:

  • 第 3 行:jle指令改为je指令,即x <= 0改为x == 0
  • 第 5 行:sar指令改为shr指令,即算术右移改为逻辑右移

奇怪的是,isPowerOf2a 居然比 isPowerOf2b 更快,这没道理啊,两者的汇编语言代码是一样的。