一个快速得到bit位索引的算法

gxqcn

已知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;
10. xor eax, eax;
12. shr ecx, 1;
13. mov dword ptr[edx + 4*eax], 0;
14. adc eax, 0;
16. shr ecx, 1;
17. mov dword ptr[edx + 4*eax], 1;
18. adc eax, 0;
20. shr ecx, 1;
21. mov dword ptr[edx + 4*eax], 2;
22. adc eax, 0;
24. shr ecx, 1;
25. mov dword ptr[edx + 4*eax], 3;
26. adc eax, 0;
28. shr ecx, 1;
29. mov dword ptr[edx + 4*eax], 4;
30. adc eax, 0;
32. shr ecx, 1;
33. mov dword ptr[edx + 4*eax], 5;
34. adc eax, 0;
36. shr ecx, 1;
37. mov dword ptr[edx + 4*eax], 6;
38. adc eax, 0;
40. shr ecx, 1;
41. mov dword ptr[edx + 4*eax], 7;
42. adc eax, 0;
44. shr ecx, 1;
45. mov dword ptr[edx + 4*eax], 8;
46. adc eax, 0;
48. shr ecx, 1;
49. mov dword ptr[edx + 4*eax], 9;
50. adc eax, 0;
52. shr ecx, 1;
53. mov dword ptr[edx + 4*eax], 10;
54. adc eax, 0;
56. shr ecx, 1;
57. mov dword ptr[edx + 4*eax], 11;
58. adc eax, 0;
60. shr ecx, 1;
61. mov dword ptr[edx + 4*eax], 12;
62. adc eax, 0;
64. shr ecx, 1;
65. mov dword ptr[edx + 4*eax], 13;
66. adc eax, 0;
68. shr ecx, 1;
69. mov dword ptr[edx + 4*eax], 14;
70. adc eax, 0;
72. shr ecx, 1;
73. mov dword ptr[edx + 4*eax], 15;
74. adc eax, 0;
76. shr ecx, 1;
77. mov dword ptr[edx + 4*eax], 16;
78. adc eax, 0;
80. shr ecx, 1;
81. mov dword ptr[edx + 4*eax], 17;
82. adc eax, 0;
84. shr ecx, 1;
85. mov dword ptr[edx + 4*eax], 18;
86. adc eax, 0;
88. shr ecx, 1;
89. mov dword ptr[edx + 4*eax], 19;
90. adc eax, 0;
92. shr ecx, 1;
93. mov dword ptr[edx + 4*eax], 20;
94. adc eax, 0;
96. shr ecx, 1;
97. mov dword ptr[edx + 4*eax], 21;
98. adc eax, 0;
100. shr ecx, 1;
101. mov dword ptr[edx + 4*eax], 22;
102. adc eax, 0;
104. shr ecx, 1;
105. mov dword ptr[edx + 4*eax], 23;
106. adc eax, 0;
108. shr ecx, 1;
109. mov dword ptr[edx + 4*eax], 24;
110. adc eax, 0;
112. shr ecx, 1;
113. mov dword ptr[edx + 4*eax], 25;
114. adc eax, 0;
116. shr ecx, 1;
117. mov dword ptr[edx + 4*eax], 26;
118. adc eax, 0;
120. shr ecx, 1;
121. mov dword ptr[edx + 4*eax], 27;
122. adc eax, 0;
124. shr ecx, 1;
125. mov dword ptr[edx + 4*eax], 28;
126. adc eax, 0;
128. shr ecx, 1;
129. mov dword ptr[edx + 4*eax], 29;
130. adc eax, 0;
132. shr ecx, 1;
133. mov dword ptr[edx + 4*eax], 30;
134. adc eax, 0;
136. shr ecx, 1;
137. mov dword ptr[edx + 4*eax], 31;
138. adc eax, 0;
140. // 休止符
141. mov dword ptr[edx + 4*eax], -1;
142. }
143. }

复制代码

以上代码涉及的汇编指令非常少，稍微有些ALU汇编指令基础的朋友很容易揣摩出其门道。 本文部分摘自：http://topic.csdn.net/u/20080217 ... c-9734e7a2b41b.html， 上述代码在其68楼，是本人原创的。 可否有更美妙的算法？

liangbch

楼主的算法确实巧妙。

mathe

用汇编的话，还可以用bsr指令。

liangbch

当 1 的个数较少时，bsr可能有优势。 当用bsr指令时，算法大概是这样的， 找到一位1,然后用当前索引对数组赋值，然后清掉当前位 重复上一步骤，知道所有的1全部找完。 因为bsr比平常的指令慢，当1的个数较多时，需要多次调用bsr指令，故速度可能不理想。

mathe

1的数目多时的确优势不明显。 上面代码有一个问题是所有指令之间有很强的数据依赖关系。现在CPU很强大，没有依赖关系的指令往往可以非常好的并行处理。 所以可以考虑这样一个算法。将32位数拆分成两个16位数据。首先通过一段代码快速计算出低16位中1的数目。 然后再分别对两部分找索引值，将它们的代码交叉起来，就可以并行处理了。 只是这样对寄存器压力会比较大，估计要动用esi,edi等

无心人

BSR慢在了可能是阻塞指令 猜想的 至于GXQ的 并不影响并行 因为存在寄存器重命名

mathe

数据依赖在eax上面，再寄存器重命名也没有用，这里有数据真依赖存在

gxqcn

bsr指令我早考虑过，但似乎并不适合解决该问题。 寄存器重命名是需要前后没有依赖关系的，而我的代码确实有很强的数据依赖关系。 这个题目由于“索引”需要判断累加，似乎很难做到并行且高效。

gxqcn

发完贴，才发现与 mathe 同时在回复一个问题。

mathe

我们知道,像下面的代码（来源自http://www.everything2.com/index.pl?node_id=1181258）可以 比较快速计算出一个int中比特1的数目，稍微修改一下，就可以变成计算short中比特1的数目的代码（可能需要4个时钟周期？？） 通过预先计算后半个short部分比特1的数目，我们应该可以将代码拆分成两个可以并行的部分。

1. unsigned numbits(unsigned int i)
2. {
4. unsigned int const MASK1 = 0x55555555;
5. unsigned int const MASK2 = 0x33333333;
6. unsigned int const MASK4 = 0x0f0f0f0f;
7. unsigned int const MASK8 = 0x00ff00ff;
8. unsigned int const MASK16 = 0x0000ffff;
10. i = (i&MASK1 ) + (i>>1 &MASK1 );
11. i = (i&MASK2 ) + (i>>2 &MASK2 );
12. i = (i&MASK4 ) + (i>>4 &MASK4 );
13. i = (i&MASK8 ) + (i>>8 &MASK8 );
14. i = (i&MASK16) + (i>>16&MASK16);
16. return i;
17. }

复制代码