求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周期