ARM汇编实现“1”位计数

白丁

ARM汇编实现“1”位计数 [复制链接]

           你是否有过对变量中“1”位的计数需求呢？有时候需要对若干变量中的“1”进行计数。如果单纯的进行移位与那效率就太低了。对一个word移位三十二次再进行与然后比较加计数，看过一回反汇编，对一个word进行“1”位计数要250+条指令周期。下面介绍一个用汇编实现的arm“1”位计数高效代码。
      3位分组计算：把32位字分成3位的组，每一组的和是两位大小的数，并行计算这些3位组，然后用对数方式加起来。
     这个操作一共占用10个周期，加两个常数建立周期。
   

白丁

1. UINT32 bit1count(UINT32 n)
   
2. 
   
3. {
   
4. 
   
5.          UINT32 t;
   
6. 
   
7.     UINT32 m = 0x49249249;
   
8. 
   
9. 
   
10. 
    
11.     t = n & (m << 1);
    
12. 
    
13.     n = n - (t >> 1);
    
14. 
    
15.     t = n & (m >> 1);
    
16. 
    
17.     n = n + t;
    
18. 
    
19. 
    
20. 
    
21.     m = 0xc71c71c7;
    
22. 
    
23.     n = n + (n >> 3);
    
24. 
    
25.     n = n & m;
    
26. 
    
27. 
    
28. 
    
29.     n = n + (n >> 6);
    
30. 
    
31.     n = n + (n >> 12);
    
32. 
    
33.     n = n + (n >> 24);
    
34. 
    
35.     n = (n & 0x3f);
    
36. 
    
37.         
    
38. 
    
39.          return n;
    
40. 
    
41. }

复制代码

C语言版来啦

zouguolvyi

如果按8bit分为一组然后去查表呢？是不是更快？我只要查4次。内存占用也还好，也就256字节。

白丁

zouguolvyi 发表于 2015-4-20 19:08
如果按8bit分为一组然后去查表呢？是不是更快？我只要查4次。内存占用也还好，也就256字节。

你算算呢，你需要移四次位，至少做三次与，关键是你的查表，你要遍历你的表，这个指令不少啊，遍历四次表，还要做加法，想想多得就不少，肯定不会更快

白丁

zouguolvyi 发表于 2015-4-20 19:08
如果按8bit分为一组然后去查表呢？是不是更快？我只要查4次。内存占用也还好，也就256字节。

可以写个c看一下反汇编有多少条指令能够做完这件事情

zouguolvyi

白丁 发表于 2015-4-20 22:33
你算算呢，你需要移四次位，至少做三次与，关键是你的查表，你要遍历你的表，这个指令不少啊，遍历四次表，还要做加法，想想多得就不少，肯定不会更快

char Table[256] =
        {0, 1, 1, 2, 1, 2, 2, 3,..........8};
//         0, 1, 2, 3, 4, 5, 6, 7,..........255

int Get1Bits(int nSmble)
{
        int nCounts = 0;

        for(int i=0; i < 32; i+=8)
        {
                  nCounts += Table[((unsigned char)(nSmble >> i))]
        }

   return nCounts;
}

zouguolvyi

白丁 发表于 2015-4-20 22:33
可以写个c看一下反汇编有多少条指令能够做完这件事情

其实你对汇编的了解还不够啊。

白丁

zouguolvyi 发表于 2015-4-21 11:03
char Table[256] =
        {0, 1, 1, 2, 1, 2, 2, 3,..........8};
//         0, 1, 2, 3, 4, 5, 6, 7,..........255

int Get1Bits(int nSmble)
{
        int nCounts = 0;

        for(int i=0; i < 32; i+=8)
        {
                  nCounts += Table[((unsigned char)(nSmble >> i))]
        }

   return nCounts;
}

zouguolvyi

多谢赐教，，，

白丁

zouguolvyi 发表于 2015-4-22 20:17
多谢赐教，，，

谈不上谈不上，我对汇编也不熟