求一个2的非负整数次幂的次数的方法比较一文中,我们比较了多种方法,但大多离不开循环和条件判断。按理说这种二进制操作,应该有更低级的指令才对,通过网络搜索,我找到了这个指令,即bsr。
在c语言中可以嵌入汇编,但msvc和gcc的语法不同。
1. msvc版本

#include <cstdio>
static inline int ilog2_x86(int x) 
{
    int retval;
    __asm {
        bsr eax, x
        mov retval, eax
    }
    return retval;
}
/*
static inline int ilog2_x86_bad(int x) //这个写法报错error C2415: 不正确的操作数类型
{
    __asm {
        bsr x, x
    }
    return x;
}
*/
int main()
{
for(int i=0;i<32;i++)
printf("%d\n",ilog2_x86(1<<i));
return 0;
}
  1. gcc版本1
  2. gcc版本2
    按照书写的简便性,从简到繁如下:(msvc不支持第1种两个操作数都是变量的形式)
int log2_x86_asm2(int x) 
{
 asm ("bsr %0,%0" : "=r" (x) : "r" (x));
 return x;
}
int log2_x86_asm(int x) 
{
 int retval;
 asm ("bsr %1,%0" : "=r" (retval) : "r" (x));
 return retval;
}

int _bsr_int32_(__int32 num) {
    __int32 count;
    __asm__(
            "bsrl %1, %0\n\t"
            "jnz 1f\n\t"
            "movl $-1,%0\n\t"
            "1:"
            :"=r"(count):"r"(num));
    return count;
}

两种语法的比较,参考
把gcc的版本用在前文的测试用例中,结果如下:

D:\>a
test case 0
use divide log(2)       199229440,2184ms
use switch      199229440,125ms
use for 199229440,405ms
use std::log2   199229440,1092ms
use while       199229440,234ms
use map 199229440,219ms
use hash map    199229440,421ms
use bin search  199229440,140ms
use tab32       199229440,125ms
use _bsr_int32_ 199229440,93ms
use log2_x86_asm        199229440,62ms
use log2_x86_asm2       199229440,78ms
test case 1
use divide log(2)       335544480,2153ms
use switch      335544480,93ms
use for 335544480,577ms
use std::log2   335544480,1123ms
use while       335544480,297ms
use map 335544480,219ms
use hash map    335544480,344ms
use bin search  335544480,124ms
use tab32       335544480,141ms
use _bsr_int32_ 335544480,93ms
use log2_x86_asm        335544480,78ms
use log2_x86_asm2       335544480,78ms

汇编指令的方法不出意料是最快的。 在Fast computing of log2 for 64-bit integers - Stack Overflow中提到,gcc还有一个内置函数,__builtin_clzll(x)返回x二进制表示中前导0的个数。用变量长度减去它,就是从右边开始的1的位置了,因此,可以 #define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1)),文中也提到,对于x86和AMD64 GCC,这个内置函数最终会编译成bsr指令。

int LOG2(int X) 
{
 return((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1));
}

use _bsr_int32_ 335544480,78ms
use log2_x86_asm        335544480,78ms
use log2_x86_asm2       335544480,63ms
use __builtin_clzll     335544480,94ms

在msvc方法的文章中,还提到一种利用float类型求log的方法,虽然看不懂,也列在这里。

int ilog2(int a)
{
    float x=a;
    unsigned int ix = (unsigned int&)x;
    unsigned int exp = (ix >> 23) & 0xFF;
    int log2 = int(exp) - 127;

    return log2;
}

经测试,与__builtin_clzll(x)的速度差不多。

#include <intrin.h>  
using namespace std;

static inline int log2_bsr_fun(int x) 
{
    int retval;
        _BitScanReverse((unsigned long*)&retval, x);
    return retval;
}

#pragma intrinsic(_BitScanReverse)

use asm 335544480,110ms
use bsr fun     335544480,93ms

以下汇编代码证明_BitScanReverse确实调用了bsr。

11. static inline int log2_bsr_fun(int x) 
12. {
13.     int retval;
14.         _BitScanReverse((unsigned long*)&retval, x);
15.     return retval;
16. }
17. 
18. #pragma intrinsic(_BitScanReverse)
19. static inline int log2_bsr_asm(int x) 
20. {
21.     int retval;
22.     __asm {
23.         bsr eax, x
24.         mov retval, eax
25.     }
26.     return retval;
27. }

; Function compile flags: /Ogtpy
;    COMDAT ?log2_bsr_asm@@YAHH@Z
_TEXT    SEGMENT
_retval$ = -4                        ; size = 4
_x$ = 8                            ; size = 4
?log2_bsr_asm@@YAHH@Z PROC                ; log2_bsr_asm, COMDAT
; File d:\power2ms2.cpp
; Line 20
    push    ecx
; Line 23
    bsr    eax, DWORD PTR _x$[esp]
; Line 24
    mov    DWORD PTR _retval$[esp+4], eax
; Line 26
    mov    eax, DWORD PTR _retval$[esp+4]
; Line 27
    pop    ecx
    ret    0
?log2_bsr_asm@@YAHH@Z ENDP                ; log2_bsr_asm
_TEXT    ENDS
; Function compile flags: /Ogtpy
;    COMDAT ?log2_bsr_fun@@YAHH@Z
_TEXT    SEGMENT
_retval$ = -4                        ; size = 4
_x$ = 8                            ; size = 4
?log2_bsr_fun@@YAHH@Z PROC                ; log2_bsr_fun, COMDAT
; File d:\power2ms2.cpp
; Line 12
    push    ecx
; Line 14
    bsr    eax, DWORD PTR _x$[esp]
    mov    DWORD PTR _retval$[esp+4], eax
; Line 16
    pop    ecx
    ret    0
?log2_bsr_fun@@YAHH@Z ENDP                ; log2_bsr_fun
_TEXT    ENDS

顺便记录一下从using-gcc-to-produce-readable-assembly学到的gcc查看汇编代码的办法.

--加上-g选项,汇编代码和行号就能对应了
D:\>g++ -c -g power2gc2.cpp

D:\>objdump -d -M intel -S power2gc2.o >power2gc2.asm

方法2,用gcc一步生成,但是结果中没有函数行号

gcc -S -g asm.c -o asm.asm

g++ -S -g asm.cpp -o asm1.asm