论坛 › 编程擂台 › 求bit位为1数目不超出2的正整数

无心人 发表于 2009-2-3 12:18:50

:L

错了
jz

呵呵

liangbch 发表于 2009-2-3 12:33:13

我的 C + 汇编的版本int log2(int n)
{
_asm
{
mov ecx,n
bsr eax,ecx
}
}

int GreaterEqualBit2_c(int n)
{
int k1,k2;
int n2;
if (n<7)
return n;

if ( !(n & (n-1)) )
return n;

k1=log2(n);
n2=n- (1 << k1);

k2=log2(n2);
if ( n2== (1<<k2) )
return n;

return (1<<k1) + ( 1 << (k2+1) );
}

无心人 发表于 2009-2-3 13:27:47

:L

你这叫哪门子代码啊

liangbch 发表于 2009-2-3 13:29:38

下面是完全使用汇编的版本，共22条指令。
稍作修改，改为20条指令_declspec(naked)
int GreaterEqualBit2_asm(int n)
{
__asm
    {
push ebx
mov eax, dword ptr

cmp eax,7
jl tExit


bsr ecx,eax //ecx: k1
mov edx,1
shl edx,cl //edx: 1 << k1

mov ebx,eax
sub ebx,edx // ebx: n2 = n- (1<<k1);
jz    tExit

bsr ecx,ebx // ecx: k2

push ebx // save n2
mov ebx,1
shl ebx,cl // ebx: (1 << k2)
pop ecx // ecx: n2
cmp ecx,ebx
jztExit // n2 == 1<<k2

lea eax,   //eax: (1<<k1) +2* (1 << k2)

tExit:
pop    ebx
ret
}
}

无心人 发表于 2009-2-3 13:29:58

找到了另外的一个写法

    mov eax, n
    mov edx, eax
    bsr ecx, edx
    btr edx, ecx
    bsrecx, edx
    jz exit
    btr edx, ecx
    cmp edx, 0
    je exit
    mov edx, 1
    shledx, cl
    sub edx, 1
    or eax, edx
    add eax, 1
exit:

无心人 发表于 2009-2-3 13:31:46

这个代码
连ret一共15条
位指令只用四个
其他均为简单指令

无心人 发表于 2009-2-3 13:35:23

不知道17#和25#哪个快
似乎17#也能照25#的再优化下

gxqcn 发表于 2009-2-3 13:55:13

我自己写了个纯汇编版本，
仅15条指令的（包含最后的ret指令），
且不含任何jump指令。

暂不贴出来；待进一步优化后再公开。

大家继续。。。

无心人 发表于 2009-2-3 14:03:16

不含任何jump指令？？
=======================
:L

又是利用了CF？
哎
要费脑子猜测了

无心人 发表于 2009-2-3 14:05:14

可能还利用了cmovcc?

查看完整版本: 求bit位为1数目不超出2的正整数