Apr 16

无聊的BSF/BSR 不指定

felix021 @ 2013-4-16 15:26 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(9681) | Via 本站原创 | |
今天看到80386+里 BSF/BSR 这对指令貌似挺有意思,Bit Scan Forward/Reverse,它们的作用是正向/逆向扫描一个WORD(16bit)/DWORD(32bit),找出第一个等于1的bit编号。比如对于BX=0x1010,执行 BSF CX, BX 得到的CX=4,而 BSR CX, BX 得到的CX=12。

咋一看是个神器啊。《编程之美》什么的,不是还有一道面试题说的就是怎样快速求出一个整数中bit=1的数量么。这货加上个while循环和移位,秒杀。最新版的Intel指令手册并没有明确说它需要多少个时钟周期,不过这里的数据指出,在80486+,BSF需要6~43个时钟周期才能完成(BSR则需要6~104个clocks),也就是说,它似乎并没有被特别优化,而是使用了CPU内的微码来完成循环,所以不要指望能带来性能上的BONUS,详情可参见这篇:求整数中比特为1的二进制位数

这篇文章里面给出的用上BSF/BSR的代码是:
int f4(unsigned int num) { 
    int count = 0; 
    while(num) { 
        int n; 
        __asm { 
            bsr eax, num 
            mov n, eax 
        } 
        ++count; 
        num ^= (1 << n); 
    } 
    return count; 

想试试这段代码,不过蛋疼的是这是VS的汇编语法,GCC不能识别,于是终于下了决心翻出GCC-Inline-Assembly-HOWTO,看了下,其实也不是很复杂,简单改了下,变成这样:
int f4(unsigned int num) { 
    int count = 0; 
    while(num) { 
        int n; 
        __asm__ (
            "bsr %1, %%eax\n\t"
            "movl %%eax, %0\n\t"
            : "=r" (n)
            : "r" (num)
            : "%eax"
        ); 
        ++count; 
        num ^= (1 << n); 
    } 
    return count; 
}

跑了一下,果然效率不行,跟最差的直接循环在同一个量级。

仔细看了下代码,发现这里用的是BSR,而且还用上了n和count两个变量,感觉不太爽,于是完全改成汇编,写成这样:
int f4(unsigned int num) {  //注:x86下一般都是用EAX来存函数的返回值
    asm (
            "movl $0, %%eax\n\t"  //这里是eax存的就是count
            "jmp  f4_cmp\n"
        "f4_loop:\n\t"
            "bsf  %0, %%ecx\n\t"  //ecx=bsf(num)
            "incb %%cl\n\t"        //cl += 1
            "shrl %%cl, %0\n\t"    //num >>= cl;  shr貌似只接受 cl 和立即数?
            "incl %%eax\n"        //count++
        "f4_cmp:\n\t"
            "cmp  $0, %0\n\t"
            "jnz  f4_loop\n\t"
            :
            : "r"(num)
            : "%eax", "%ecx"
    );
}

结果。。。基本没变。嗯,所以就这样吧。。。

转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: http://www.felix021.com/blog/feed.php
haha
2016-5-5 22:11
过时了,现在你可以用popcnt再试一次
在我这儿比查表快5倍,任何软件优化算法都比不上了
felix021 回复于 2016-5-7 13:42
好吧,这个指令太高大上了……
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]