求bit位为1数目不超出2的正整数

无心人

假设n的前2个bit = 1的索引是i, j
则结果是
  2^i + [(2^j) << (n - 2^i - 2^j * (n & (n-1) != 0) != 0) ] * (n&(n-1) !=0)

无心人

不对

这个复杂式子， 不可能用15条指令能完成

无心人

mov ebx, n
   mov eax, 1
   bsr ecx, ebx
   shl eax, cl
   sub ebx, eax
   mov edx, 1
   mov esi, 0
   bsr ecx, ebx
   shl edx, cl
   cmovne esi, edx
   add eax, esi
   mov edi, 0
   sub ebx, edx
   cmovne edi, esi
   add eax, edi

==================
这么做么？

gxqcn

原帖由 无心人 于 2009-2-3 14:05 发表 可能还利用了cmovcc?

猜对了！

gxqcn

刚才查了下指令周期表，
发现AMD的BSR指令周期狂长：28，
Intel的就好很多（=2）。

无心人

优化下
   mov eax, 1
   bsr ecx, n
   shl eax, cl
   sub n, eax
   xor edx, edx
   bsr ecx, n
   setne dl
   shl edx, cl
   add eax, edx
   xor ecx, ecx
   sub n, edx
   cmovne ecx, edx
   add eax, ecx
====================

无心人

没有bsr几乎不能做到很完美

无心人

36#应该类似GxQ的想法吧
而且加上ret还少一条
现在就看setne是否好了
==========================
似乎看P4/Core2的执行周期
这个版本并不存在长指令

shshsh_0510

那也不一定，如果只看速度不在乎内存的话，可以用hash
比如为8位做一个256项的表，检测前8位，只有33/256的数据不能立即返回，需要再检验后面。
不用汇编未必会比你们慢

无心人

  汇编大概在20个时钟周期内就能完成
  hash光一个除法就至少20周期