数学研发论坛

 找回密码
 欢迎注册
查看: 15022|回复: 65

[讨论] 一个快速得到bit位索引的算法

[复制链接]
发表于 2008-3-3 16:26:00 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
已知32位中有n(0 <= n <= 32)个1。
要求:快速找处所有的1位索引数值。


一般的算法,都需要大量的跳转指令才能完成,
而CPU一旦分支预测失败,将会有很大的惩罚,应尽可能避免。

下面是我想到的一种完全无跳转指令的算法,抛出来与大家共享:
  1. // 作者:GxQ,2008-03-03
  2. // 返回返回当前bit=1的数目
  3. DWORD find_by_GxQ(DWORD code, int index[33])
  4. {
  5.     __asm
  6.     {
  7.         mov     ecx, code;
  8.         mov     edx, dword ptr index;

  9.         xor     eax, eax;

  10.         shr     ecx, 1;
  11.         mov     dword ptr[edx + 4*eax], 0;
  12.         adc     eax, 0;

  13.         shr     ecx, 1;
  14.         mov     dword ptr[edx + 4*eax], 1;
  15.         adc     eax, 0;

  16.         shr     ecx, 1;
  17.         mov     dword ptr[edx + 4*eax], 2;
  18.         adc     eax, 0;

  19.         shr     ecx, 1;
  20.         mov     dword ptr[edx + 4*eax], 3;
  21.         adc     eax, 0;

  22.         shr     ecx, 1;
  23.         mov     dword ptr[edx + 4*eax], 4;
  24.         adc     eax, 0;

  25.         shr     ecx, 1;
  26.         mov     dword ptr[edx + 4*eax], 5;
  27.         adc     eax, 0;

  28.         shr     ecx, 1;
  29.         mov     dword ptr[edx + 4*eax], 6;
  30.         adc     eax, 0;

  31.         shr     ecx, 1;
  32.         mov     dword ptr[edx + 4*eax], 7;
  33.         adc     eax, 0;

  34.         shr     ecx, 1;
  35.         mov     dword ptr[edx + 4*eax], 8;
  36.         adc     eax, 0;

  37.         shr     ecx, 1;
  38.         mov     dword ptr[edx + 4*eax], 9;
  39.         adc     eax, 0;

  40.         shr     ecx, 1;
  41.         mov     dword ptr[edx + 4*eax], 10;
  42.         adc     eax, 0;

  43.         shr     ecx, 1;
  44.         mov     dword ptr[edx + 4*eax], 11;
  45.         adc     eax, 0;

  46.         shr     ecx, 1;
  47.         mov     dword ptr[edx + 4*eax], 12;
  48.         adc     eax, 0;

  49.         shr     ecx, 1;
  50.         mov     dword ptr[edx + 4*eax], 13;
  51.         adc     eax, 0;

  52.         shr     ecx, 1;
  53.         mov     dword ptr[edx + 4*eax], 14;
  54.         adc     eax, 0;

  55.         shr     ecx, 1;
  56.         mov     dword ptr[edx + 4*eax], 15;
  57.         adc     eax, 0;

  58.         shr     ecx, 1;
  59.         mov     dword ptr[edx + 4*eax], 16;
  60.         adc     eax, 0;

  61.         shr     ecx, 1;
  62.         mov     dword ptr[edx + 4*eax], 17;
  63.         adc     eax, 0;

  64.         shr     ecx, 1;
  65.         mov     dword ptr[edx + 4*eax], 18;
  66.         adc     eax, 0;

  67.         shr     ecx, 1;
  68.         mov     dword ptr[edx + 4*eax], 19;
  69.         adc     eax, 0;

  70.         shr     ecx, 1;
  71.         mov     dword ptr[edx + 4*eax], 20;
  72.         adc     eax, 0;

  73.         shr     ecx, 1;
  74.         mov     dword ptr[edx + 4*eax], 21;
  75.         adc     eax, 0;

  76.         shr     ecx, 1;
  77.         mov     dword ptr[edx + 4*eax], 22;
  78.         adc     eax, 0;

  79.         shr     ecx, 1;
  80.         mov     dword ptr[edx + 4*eax], 23;
  81.         adc     eax, 0;

  82.         shr     ecx, 1;
  83.         mov     dword ptr[edx + 4*eax], 24;
  84.         adc     eax, 0;

  85.         shr     ecx, 1;
  86.         mov     dword ptr[edx + 4*eax], 25;
  87.         adc     eax, 0;

  88.         shr     ecx, 1;
  89.         mov     dword ptr[edx + 4*eax], 26;
  90.         adc     eax, 0;

  91.         shr     ecx, 1;
  92.         mov     dword ptr[edx + 4*eax], 27;
  93.         adc     eax, 0;

  94.         shr     ecx, 1;
  95.         mov     dword ptr[edx + 4*eax], 28;
  96.         adc     eax, 0;

  97.         shr     ecx, 1;
  98.         mov     dword ptr[edx + 4*eax], 29;
  99.         adc     eax, 0;

  100.         shr     ecx, 1;
  101.         mov     dword ptr[edx + 4*eax], 30;
  102.         adc     eax, 0;

  103.         shr     ecx, 1;
  104.         mov     dword ptr[edx + 4*eax], 31;
  105.         adc     eax, 0;

  106.         // 休止符
  107.         mov     dword ptr[edx + 4*eax], -1;
  108.     }
  109. }
复制代码
以上代码涉及的汇编指令非常少,稍微有些ALU汇编指令基础的朋友很容易揣摩出其门道。

本文部分摘自:http://topic.csdn.net/u/20080217 ... c-9734e7a2b41b.html
上述代码在其68楼,是本人原创的。

可否有更美妙的算法?

评分

参与人数 1威望 +2 鲜花 +2 收起 理由
liangbch + 2 + 2 有创造性

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-3 16:49:06 | 显示全部楼层
楼主的算法确实巧妙。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-3 18:29:59 | 显示全部楼层
用汇编的话,还可以用bsr指令。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-3 18:43:57 | 显示全部楼层
当 1 的个数较少时,bsr可能有优势。
当用bsr指令时,算法大概是这样的,
    找到一位1,然后用当前索引对数组赋值,然后清掉当前位
    重复上一步骤,知道所有的1全部找完。

因为bsr比平常的指令慢,当1的个数较多时,需要多次调用bsr指令,故速度可能不理想。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-3 18:53:04 | 显示全部楼层
1的数目多时的确优势不明显。
上面代码有一个问题是所有指令之间有很强的数据依赖关系。现在CPU很强大,没有依赖关系的指令往往可以非常好的并行处理。
所以可以考虑这样一个算法。将32位数拆分成两个16位数据。首先通过一段代码快速计算出低16位中1的数目。
然后再分别对两部分找索引值,将它们的代码交叉起来,就可以并行处理了。
只是这样对寄存器压力会比较大,估计要动用esi,edi等
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-3 20:46:40 | 显示全部楼层
BSR慢在了可能是阻塞指令
猜想的

至于GXQ的
并不影响并行
因为存在寄存器重命名
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-4 07:54:24 | 显示全部楼层
数据依赖在eax上面,再寄存器重命名也没有用,这里有数据真依赖存在
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-4 07:54:47 | 显示全部楼层
bsr指令我早考虑过,但似乎并不适合解决该问题。

寄存器重命名是需要前后没有依赖关系的,而我的代码确实有很强的数据依赖关系。

这个题目由于“索引”需要判断累加,似乎很难做到并行且高效。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-4 07:57:26 | 显示全部楼层

撞车了:)

发完贴,才发现与 mathe 同时在回复一个问题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-4 08:40:57 | 显示全部楼层
我们知道,像下面的代码(来源自http://www.everything2.com/index.pl?node_id=1181258)可以
比较快速计算出一个int中比特1的数目,稍微修改一下,就可以变成计算short中比特1的数目的代码(可能需要4个时钟周期??)
通过预先计算后半个short部分比特1的数目,我们应该可以将代码拆分成两个可以并行的部分。
  1. unsigned numbits(unsigned int i)
  2. {

  3.     unsigned int const MASK1  = 0x55555555;
  4.     unsigned int const MASK2  = 0x33333333;
  5.     unsigned int const MASK4  = 0x0f0f0f0f;
  6.     unsigned int const MASK8  = 0x00ff00ff;
  7.     unsigned int const MASK16 = 0x0000ffff;
  8.    
  9.     i = (i&MASK1 ) + (i>>1 &MASK1 );
  10.     i = (i&MASK2 ) + (i>>2 &MASK2 );
  11.     i = (i&MASK4 ) + (i>>4 &MASK4 );
  12.     i = (i&MASK8 ) + (i>>8 &MASK8 );
  13.     i = (i&MASK16) + (i>>16&MASK16);
  14.    
  15.     return i;
  16. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-1-20 08:18 , Processed in 0.057595 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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