求bit位为1数目不超出2的正整数

gxqcn

看起来不错， 若能将部分访问内存的语句改成访问寄存器的就更好了。

无心人

当然， 这么小的范围 Cache整个表才是王道

无心人

我想 xor edx, edx setne dl 应该不阻塞 不是说了么 全0的寄存器不存在部分寄存器阻塞

shshsh_0510

原帖由 无心人 于 2009-2-3 15:20 发表 汇编大概在20个时钟周期内就能完成 hash光一个除法就至少20周期

谁让你用除法了，说是Cache表可能比较合适

无心人

你来实现下 看最后翻译成汇编 20条内能实现么？

shshsh_0510

好吧，好久不编程了，试试看

无心人

http://www.codingnow.com/mmx/mmx2.htm#4 这里有部分寄存器阻塞的详细说明 我们这里的代码应该属于这种例外 即首先xor大寄存器，再setne，则应该不影响稍后的指令

无心人

记得原先写的代码求大于等于n的2的方幂， 当时写的不好 如果现在写，应该这么做 mov eax, 1 bsr ecx, n bsf edx, n sub edx, ecx adc eax, 0 mov edx, 0 cmp n, 0 cmove eax, edx shl eax, cl

shshsh_0510

大概写了一下，就算示意吧，那个表的数据我就不算了，太麻烦了

1. #include <stdio.h>
3. typedef unsigned int UINT32;
5. typedef struct data {
6. UINT32 retvalue;
7. UINT32 halfdata;
8. int type; //0 : directly return ; 1: need to go on
9. } ITEM_DATA;
11. ITEM_DATA hash [256] = {
12. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
13. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
14. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
15. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
16. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
17. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
18. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
19. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
20. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
21. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
22. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
23. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
24. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
25. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
26. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
27. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
28. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
29. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
30. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
31. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
32. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
33. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
34. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
35. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
36. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
37. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
38. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
39. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
40. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
41. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
42. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},
43. {1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0},{1,1,0}
44. };
47. UINT32 GreaterEqualBit2(UINT32 n)
48. {
49. int t1=0,t2=0;
50. unsigned char *v= (unsigned char *)&n;
51. //find first 2 v that large than zero
52. if (v[3]>0) {
53. if( hash[v[3]].type == 0 ) {
54. //3
55. return ( hash[v[3]].retvalue )<<24;
56. } else {
57. if (v[2]>0) {
58. //3,2
59. return ((hash[v[3]].halfdata)<<24)+((hash[v[2]].halfdata)<<16);
60. }
61. else {
62. if(v[1]>0) {
63. //3,1
64. return ((hash[v[3]].halfdata)<<24)+((hash[v[1]].halfdata)<<8);
65. }
66. }
67. //3,0
68. return ((hash[v[3]].halfdata)<<24)+((hash[v[0]].halfdata));
69. }
70. }
71. else {
72. if(v[2]>0) {
73. if( hash[v[2]].type == 0 ) {
74. //2
75. return ( hash[v[2]].retvalue )<<16;
76. } else {
77. if (v[1]>0)
78. //2,1
79. return ((hash[v[2]].halfdata)<<16)+((hash[v[1]].halfdata)<<8);
80. else
81. //2,0
82. return ((hash[v[2]].halfdata)<<16)+((hash[v[1]].halfdata) );
83. }
84. }
85. else
86. if(v[1]>0) {
87. if( hash[v[1]].type == 0 )
88. //1
89. return ( hash[v[1]].retvalue )<<8;
90. else
91. //1,0
92. return ((hash[v[1]].halfdata)<<8)+((hash[v[1]].halfdata) );
93. }
94. }
95. //0
96. return hash[v[0]].retvalue ;
97. }
99. int main(int argc, char * argv[]){
100. int i;
101. for (i=0x11 ; i<0x111121 ; i++)
102. printf(" input %d , output %X \n",i,GreaterEqualBit2(i));
104. return 0;
105. }

复制代码

无心人

你认为这么复杂的代码比我的汇编要高效么？ 况且，最终的代码的适用范围要比GxQ题目要求的大 只要是1-(2^31+2^30）就可以