数学研发论坛

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

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

[复制链接]
发表于 2009-2-3 14:17:28 | 显示全部楼层
假设n的前2个bit = 1的索引是i, j
则结果是
  2^i + [(2^j) << (n - 2^i - 2^j * (n & (n-1) != 0) != 0) ] * (n&(n-1) !=0)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 14:25:59 | 显示全部楼层
不对

这个复杂式子, 不可能用15条指令能完成
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 14:38:05 | 显示全部楼层
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

==================
这么做么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-3 14:58:39 | 显示全部楼层
原帖由 无心人 于 2009-2-3 14:05 发表
可能还利用了cmovcc?


猜对了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-3 15:02:29 | 显示全部楼层
刚才查了下指令周期表,
发现AMD的BSR指令周期狂长:28,
Intel的就好很多(=2)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:03:37 | 显示全部楼层
优化下
   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
====================
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:04:26 | 显示全部楼层
没有bsr几乎不能做到很完美
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:06:33 | 显示全部楼层
36#应该类似GxQ的想法吧
而且加上ret还少一条
现在就看setne是否好了
==========================
似乎看P4/Core2的执行周期
这个版本并不存在长指令
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:14:55 | 显示全部楼层
那也不一定,如果只看速度不在乎内存的话,可以用hash
比如为8位做一个256项的表,检测前8位,只有33/256的数据不能立即返回,需要再检验后面。
不用汇编未必会比你们慢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-3 15:20:19 | 显示全部楼层


  汇编大概在20个时钟周期内就能完成
  hash光一个除法就至少20周期
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-8-17 20:35 , Processed in 0.048948 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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