求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>
   
2. 
   
3. typedef unsigned int UINT32;
   
4. 
   
5. typedef struct data {
   
6.         UINT32 retvalue;
   
7.         UINT32 halfdata;
   
8.         int type; //0 : directly return ; 1: need to go on  
   
9. } ITEM_DATA;
   
10. 
    
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. };
    
45. 
    
46. 
    
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. }
    
98. 
    
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));
     
103.        
     
104.     return 0;
     
105. }

复制代码

无心人

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