数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 算法交流 › 一个快速得到bit位索引的算法
1234567下一页
返回列表 发新帖
楼主: gxqcn

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

[复制链接]
mathe
发表于 2008-3-4 08:43:41 | 显示全部楼层
根据那个链接，数1的比特位数目应该用查询表还要快一些。（特别对于16比特整数）
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
 楼主| 发表于 2008-3-4 08:50:41 | 显示全部楼层
原帖由 mathe 于 2008-3-4 08:40 发表 我们知道,像下面的代码（来源自http://www.everything2.com/index.pl?node_id=1181258）可以 比较快速计算出一个int中比特1的数目，稍微修改一下，就可以变成计算short中比特1的数目的代码（可能需要4个时钟周期？？ 通过预先计算后半个short部分比特1的数目，我们应该可以将代码拆分成两个可以并行的部分。...
这个想法好是好，但最后如何并行并不容易啊。。。 不知道CPU是否支持函数级的并行：当两个紧邻的函数名一致、而输入输出没有依赖关系时？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-4 08:58:56 | 显示全部楼层
还有，gxqcn的代码可以改成C代码
  1. unsigned find(unsigned code, int index[])
  2. {
  3. int i;
  4. int *p=index;
  5. for(i=0;i<32;i++){
  6. *p=i;
  7. p+=(code&(1<<i))!=0;
  8. }
  9. *p=-1;
  10. }
复制代码
看看，当然编译器优化选项要打开（这样循环才会被展开）。 如果当心编译器优化选项打开会影响测试，可以创建保换两个文件的工程，将这部分代码单独放在一个文件中，然后单独对这个文件优化。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-4 09:00:45 | 显示全部楼层
函数级的不行，没法做到指令级并行，而线程级并行显然不能使用。 发现你那个代码如果拆分成并行的两部分或者四部分，主要问题在于最后对于那些多余的0有些问题
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-3-4 09:01:43 | 显示全部楼层
别想了 目前的X86没并行功能 考虑Cell级别的CPU可能还行 哈
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-4 09:10:01 | 显示全部楼层
将上面代码用gcc -O3 -funroll-all-loops -S编译出来代码为: 不过不知道为什么前面要做一次跳转指令，估计是为了让内存同Cacheline边界对齐。 如果我们能够保证输入数组空间已经内存对齐，那么这部分指令可以拿掉。（特别对于重复运行多次进行测试的代码，这部分应该拿掉）
  1. .file "tta1.c"
  2. .text
  3. .p2align 4,,15
  4. .globl find
  5. .type find, @function
  6. find:
  7. pushl %ebp
  8. movl %esp, %ebp
  9. pushl %edi
  10. pushl %esi
  11. movl \$1, %esi
  12. pushl %ebx
  13. xorl %ebx, %ebx
  14. subl \$4, %esp
  15. movl 12(%ebp), %eax
  16. movl 8(%ebp), %edi
  17. movl %eax, -16(%ebp)
  18. jmp .L2
  19. .p2align 4,,7
  20. .L20:
  21. movl -16(%ebp), %eax
  22. .L2:
  23. movb %bl, %cl
  24. movl %esi, %edx
  25. sall %cl, %edx
  26. andl %edi, %edx
  27. movl %ebx, (%eax)
  28. cmpl \$1, %edx
  29. movl -16(%ebp), %eax
  30. sbbl %edx, %edx
  31. notl %edx
  32. andl \$4, %edx
  33. addl %eax, %edx
  34. movl %esi, %eax
  35. leal 1(%ebx), %ecx
  36. sall %cl, %eax
  37. movl %ecx, (%edx)
  38. movl %eax, %ecx
  39. andl %edi, %ecx
  40. cmpl \$1, %ecx
  41. sbbl %eax, %eax
  42. notl %eax
  43. andl \$4, %eax
  44. addl %eax, %edx
  45. movl %esi, %eax
  46. leal 2(%ebx), %ecx
  47. sall %cl, %eax
  48. movl %ecx, (%edx)
  49. movl %eax, %ecx
  50. andl %edi, %ecx
  51. cmpl \$1, %ecx
  52. sbbl %eax, %eax
  53. notl %eax
  54. andl \$4, %eax
  55. addl %eax, %edx
  56. movl %esi, %eax
  57. leal 3(%ebx), %ecx
  58. sall %cl, %eax
  59. movl %ecx, (%edx)
  60. movl %eax, %ecx
  61. andl %edi, %ecx
  62. cmpl \$1, %ecx
  63. sbbl %eax, %eax
  64. notl %eax
  65. andl \$4, %eax
  66. addl %eax, %edx
  67. movl %esi, %eax
  68. leal 4(%ebx), %ecx
  69. sall %cl, %eax
  70. movl %ecx, (%edx)
  71. movl %eax, %ecx
  72. andl %edi, %ecx
  73. cmpl \$1, %ecx
  74. sbbl %eax, %eax
  75. notl %eax
  76. andl \$4, %eax
  77. addl %eax, %edx
  78. movl %esi, %eax
  79. leal 5(%ebx), %ecx
  80. sall %cl, %eax
  81. movl %ecx, (%edx)
  82. movl %eax, %ecx
  83. andl %edi, %ecx
  84. cmpl \$1, %ecx
  85. sbbl %eax, %eax
  86. notl %eax
  87. andl \$4, %eax
  88. addl %eax, %edx
  89. movl %esi, %eax
  90. leal 6(%ebx), %ecx
  91. sall %cl, %eax
  92. movl %ecx, (%edx)
  93. movl %eax, %ecx
  94. andl %edi, %ecx
  95. cmpl \$1, %ecx
  96. sbbl %eax, %eax
  97. notl %eax
  98. andl \$4, %eax
  99. addl %eax, %edx
  100. movl %esi, %eax
  101. leal 7(%ebx), %ecx
  102. sall %cl, %eax
  103. movl %ecx, (%edx)
  104. movl %eax, %ecx
  105. andl %edi, %ecx
  106. cmpl \$1, %ecx
  107. sbbl %ecx, %ecx
  108. addl \$8, %ebx
  109. notl %ecx
  110. andl \$4, %ecx
  111. cmpl \$32, %ebx
  112. leal (%edx,%ecx), %eax
  113. movl %eax, -16(%ebp)
  114. jne .L20
  115. movl 12(%ebp), %ecx
  116. subl %ecx, -16(%ebp)
  117. sarl \$2, -16(%ebp)
  118. movl -16(%ebp), %eax
  119. popl %edx
  120. popl %ebx
  121. popl %esi
  122. popl %edi
  123. popl %ebp
  124. ret
复制代码
gxqcn: 刚才对上述代码进行了重新排版， 1、将所有的美元符前添加“\”，以防止误解析为数学公式 2、将所有的Tab符替换成四个空格，并适当删减空格使之对齐
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-4 09:18:43 | 显示全部楼层
好像上面编译器展开的代码有点问题，看不大懂，还是直接用手工展开的代码吧:
  1. #define STORE(i) *p=i; \
  2. p+=(code&(1<<i))!=0;
  4. unsigned find(unsigned code, int index[33])
  5. {
  6. int i;
  7. int *p=index;
  9. STORE(0)
  10. STORE(1)
  11. STORE(2)
  12. STORE(3)
  13. STORE(4)
  14. STORE(5)
  15. STORE(6)
  16. STORE(7)
  17. STORE(8)
  18. STORE(9)
  19. STORE(10)
  20. STORE(11)
  21. STORE(12)
  22. STORE(13)
  23. STORE(14)
  24. STORE(15)
  25. STORE(16)
  26. STORE(17)
  27. STORE(18)
  28. STORE(19)
  29. STORE(20)
  30. STORE(21)
  31. STORE(22)
  32. STORE(23)
  33. STORE(24)
  34. STORE(25)
  35. STORE(26)
  36. STORE(27)
  37. STORE(28)
  38. STORE(29)
  39. STORE(30)
  40. STORE(31)
  41. *p=-1;
  42. return p-index;
  43. }
复制代码
对应gcc编译汇编代码为:
  1. find:
  2. pushl %ebp
  3. movl %esp, %ebp
  4. movl 8(%ebp), %eax
  5. pushl %ebx
  6. movl 12(%ebp), %ebx
  7. movl %eax, %edx
  8. movl %eax, %ecx
  9. andl \$2, %edx
  10. andl \$1, %ecx
  11. cmpl \$1, %edx
  12. sbbl %edx, %edx
  13. notl %edx
  14. leal (%ebx,%ecx,4), %ecx
  15. andl \$4, %edx
  16. movl \$0, (%ebx)
  17. addl %ecx, %edx
  18. movl \$1, (%ecx)
  19. movl %eax, %ecx
  20. andl \$4, %ecx
  21. movl \$2, (%edx)
  22. addl %ecx, %edx
  23. movl %eax, %ecx
  24. andl \$8, %ecx
  25. cmpl \$1, %ecx
  26. sbbl %ecx, %ecx
  27. notl %ecx
  28. andl \$4, %ecx
  29. movl \$3, (%edx)
  30. addl %edx, %ecx
  31. movl %eax, %edx
  32. andl \$16, %edx
  33. cmpl \$1, %edx
  34. sbbl %edx, %edx
  35. notl %edx
  36. andl \$4, %edx
  37. movl \$4, (%ecx)
  38. addl %ecx, %edx
  39. movl %eax, %ecx
  40. andl \$32, %ecx
  41. cmpl \$1, %ecx
  42. sbbl %ecx, %ecx
  43. notl %ecx
  44. andl \$4, %ecx
  45. movl \$5, (%edx)
  46. addl %edx, %ecx
  47. movl %eax, %edx
  48. andl \$64, %edx
  49. cmpl \$1, %edx
  50. sbbl %edx, %edx
  51. notl %edx
  52. andl \$4, %edx
  53. movl \$6, (%ecx)
  54. addl %ecx, %edx
  55. movb %al, %cl
  56. andb \$-128, %cl
  57. cmpb \$1, %cl
  58. sbbl %ecx, %ecx
  59. notl %ecx
  60. andl \$4, %ecx
  61. movl \$7, (%edx)
  62. addl %edx, %ecx
  63. movl %eax, %edx
  64. andl \$256, %edx
  65. cmpl \$1, %edx
  66. sbbl %edx, %edx
  67. notl %edx
  68. andl \$4, %edx
  69. movl \$8, (%ecx)
  70. addl %ecx, %edx
  71. movl %eax, %ecx
  72. andl \$512, %ecx
  73. cmpl \$1, %ecx
  74. sbbl %ecx, %ecx
  75. notl %ecx
  76. andl \$4, %ecx
  77. movl \$9, (%edx)
  78. addl %edx, %ecx
  79. movl %eax, %edx
  80. andl \$1024, %edx
  81. cmpl \$1, %edx
  82. sbbl %edx, %edx
  83. notl %edx
  84. andl \$4, %edx
  85. movl \$10, (%ecx)
  86. addl %ecx, %edx
  87. movl %eax, %ecx
  88. andl \$2048, %ecx
  89. cmpl \$1, %ecx
  90. sbbl %ecx, %ecx
  91. notl %ecx
  92. andl \$4, %ecx
  93. movl \$11, (%edx)
  94. addl %edx, %ecx
  95. movl %eax, %edx
  96. andl \$4096, %edx
  97. cmpl \$1, %edx
  98. sbbl %edx, %edx
  99. notl %edx
  100. andl \$4, %edx
  101. movl \$12, (%ecx)
  102. addl %ecx, %edx
  103. movl %eax, %ecx
  104. andl \$8192, %ecx
  105. cmpl \$1, %ecx
  106. sbbl %ecx, %ecx
  107. notl %ecx
  108. andl \$4, %ecx
  109. movl \$13, (%edx)
  110. addl %edx, %ecx
  111. movl %eax, %edx
  112. andl \$16384, %edx
  113. cmpl \$1, %edx
  114. sbbl %edx, %edx
  115. notl %edx
  116. andl \$4, %edx
  117. movl \$14, (%ecx)
  118. addl %ecx, %edx
  119. movl %eax, %ecx
  120. andl \$32768, %ecx
  121. cmpw \$1, %cx
  122. sbbl %ecx, %ecx
  123. notl %ecx
  124. andl \$4, %ecx
  125. movl \$15, (%edx)
  126. addl %edx, %ecx
  127. movl %eax, %edx
  128. andl \$65536, %edx
  129. cmpl \$1, %edx
  130. sbbl %edx, %edx
  131. notl %edx
  132. andl \$4, %edx
  133. movl \$16, (%ecx)
  134. addl %ecx, %edx
  135. movl %eax, %ecx
  136. andl \$131072, %ecx
  137. cmpl \$1, %ecx
  138. sbbl %ecx, %ecx
  139. notl %ecx
  140. andl \$4, %ecx
  141. movl \$17, (%edx)
  142. addl %edx, %ecx
  143. movl %eax, %edx
  144. andl \$262144, %edx
  145. cmpl \$1, %edx
  146. sbbl %edx, %edx
  147. notl %edx
  148. andl \$4, %edx
  149. movl \$18, (%ecx)
  150. addl %ecx, %edx
  151. movl %eax, %ecx
  152. andl \$524288, %ecx
  153. cmpl \$1, %ecx
  154. sbbl %ecx, %ecx
  155. notl %ecx
  156. andl \$4, %ecx
  157. movl \$19, (%edx)
  158. addl %edx, %ecx
  159. movl %eax, %edx
  160. andl \$1048576, %edx
  161. cmpl \$1, %edx
  162. sbbl %edx, %edx
  163. notl %edx
  164. andl \$4, %edx
  165. movl \$20, (%ecx)
  166. addl %ecx, %edx
  167. movl %eax, %ecx
  168. andl \$2097152, %ecx
  169. cmpl \$1, %ecx
  170. sbbl %ecx, %ecx
  171. notl %ecx
  172. andl \$4, %ecx
  173. movl \$21, (%edx)
  174. addl %edx, %ecx
  175. movl %eax, %edx
  176. andl \$4194304, %edx
  177. cmpl \$1, %edx
  178. sbbl %edx, %edx
  179. notl %edx
  180. andl \$4, %edx
  181. movl \$22, (%ecx)
  182. addl %ecx, %edx
  183. movl %eax, %ecx
  184. andl \$8388608, %ecx
  185. cmpl \$1, %ecx
  186. sbbl %ecx, %ecx
  187. notl %ecx
  188. andl \$4, %ecx
  189. movl \$23, (%edx)
  190. addl %edx, %ecx
  191. movl %eax, %edx
  192. andl \$16777216, %edx
  193. cmpl \$1, %edx
  194. sbbl %edx, %edx
  195. notl %edx
  196. andl \$4, %edx
  197. movl \$24, (%ecx)
  198. addl %ecx, %edx
  199. movl %eax, %ecx
  200. andl \$33554432, %ecx
  201. cmpl \$1, %ecx
  202. sbbl %ecx, %ecx
  203. notl %ecx
  204. andl \$4, %ecx
  205. movl \$25, (%edx)
  206. addl %edx, %ecx
  207. movl %eax, %edx
  208. andl \$67108864, %edx
  209. cmpl \$1, %edx
  210. sbbl %edx, %edx
  211. notl %edx
  212. andl \$4, %edx
  213. addl %ecx, %edx
  214. movl \$26, (%ecx)
  215. movl %eax, %ecx
  216. andl \$134217728, %ecx
  217. cmpl \$1, %ecx
  218. sbbl %ecx, %ecx
  219. notl %ecx
  220. andl \$4, %ecx
  221. addl %edx, %ecx
  222. movl \$27, (%edx)
  223. movl %eax, %edx
  224. andl \$268435456, %edx
  225. cmpl \$1, %edx
  226. sbbl %edx, %edx
  227. notl %edx
  228. andl \$4, %edx
  229. addl %ecx, %edx
  230. movl \$28, (%ecx)
  231. movl %eax, %ecx
  232. andl \$536870912, %ecx
  233. cmpl \$1, %ecx
  234. sbbl %ecx, %ecx
  235. notl %ecx
  236. andl \$4, %ecx
  237. movl \$29, (%edx)
  238. addl %edx, %ecx
  239. movl %eax, %edx
  240. andl \$1073741824, %edx
  241. cmpl \$1, %edx
  242. sbbl %edx, %edx
  243. notl %edx
  244. andl \$4, %edx
  245. sarl \$31, %eax
  246. addl %ecx, %edx
  247. andl \$4, %eax
  248. addl %edx, %eax
  249. movl \$30, (%ecx)
  250. movl \$31, (%edx)
  251. movl \$-1, (%eax)
  252. subl %ebx, %eax
  253. popl %ebx
  254. sarl \$2, %eax
  255. popl %ebp
  256. ret
复制代码
对应
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

gxqcn
 楼主| 发表于 2008-3-4 09:33:54 | 显示全部楼层
注意：我对16#、17#帖子进行过编辑排版。 似乎楼上的汇编指令数比我那版多了不少。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
发表于 2008-3-4 09:54:31 | 显示全部楼层
指令数目并不说明任何问题，我觉得编译器这么选择应该有其理由，毕竟这种细节问题人通常没有编译器考虑得好
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-3-10 10:06:37 | 显示全部楼层
总感觉不对劲 终于觉醒了 似乎我是测试的1000万, 你们测试的是100万 把GXQ代码和我代码聚集在一起 终于比较出来了 还是我的快 我冤啊 FindBits.rar (8.41 KB, 下载次数: 1)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1234567下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-24 10:07 , Processed in 0.027018 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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