数学研发论坛

 找回密码
 欢迎注册
楼主: gxqcn

[擂台] 求bit位为1数目不超出2的正整数

[复制链接]
发表于 2009-2-3 12:18:50 | 显示全部楼层


错了
jz

呵呵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 12:33:13 | 显示全部楼层
我的 C + 汇编的版本
  1. int log2(int n)
  2. {
  3. _asm
  4. {
  5. mov ecx,n
  6. bsr eax,ecx
  7. }
  8. }

  9. int GreaterEqualBit2_c(int n)
  10. {
  11. int k1,k2;
  12. int n2;
  13. if (n<7)
  14. return n;

  15. if ( !(n & (n-1)) )
  16. return n;

  17. k1=log2(n);
  18. n2=n- (1 << k1);

  19. k2=log2(n2);
  20. if ( n2== (1<<k2) )
  21. return n;

  22. return (1<<k1) + ( 1 << (k2+1) );
  23. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 13:27:47 | 显示全部楼层


你这叫哪门子代码啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 13:29:38 | 显示全部楼层
下面是完全使用汇编的版本,共22条指令。
稍作修改,改为20条指令
  1. _declspec(naked)
  2. int GreaterEqualBit2_asm(int n)
  3. {
  4. __asm
  5.     {
  6. push ebx
  7. mov eax, dword ptr[esp + 4+ 4]

  8. cmp eax,7
  9. jl tExit

  10.   
  11. bsr ecx,eax //ecx: k1
  12. mov edx,1
  13. shl edx,cl //edx: 1 << k1

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

  17. bsr ecx,ebx // ecx: k2

  18. push ebx // save n2
  19. mov ebx,1
  20. shl ebx,cl // ebx: (1 << k2)
  21. pop ecx // ecx: n2
  22. cmp ecx,ebx
  23. jz  tExit // n2 == 1<<k2

  24. lea eax,  [edx + ebx*2]   //eax: (1<<k1) +  2* (1 << k2)

  25. tExit:
  26. pop    ebx
  27. ret
  28. }
  29. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 13:29:58 | 显示全部楼层
找到了另外的一个写法

    mov eax, n
    mov edx, eax
    bsr ecx, edx
    btr edx, ecx
    bsr  ecx, edx
    jz exit
    btr edx, ecx
    cmp edx, 0
    je exit
    mov edx, 1
    shl  edx, 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#的再优化下
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-3 13:55:13 | 显示全部楼层
我自己写了个纯汇编版本,
仅15条指令的(包含最后的ret指令),
且不含任何jump指令。

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

大家继续。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 14:03:16 | 显示全部楼层
不含任何jump指令??
=======================


又是利用了CF?

要费脑子猜测了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 14:05:14 | 显示全部楼层
可能还利用了cmovcc?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-18 08:29 , Processed in 0.050871 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表