请教一个算法

cugb_cat

总共就那么几位，就算从最低位开始一位一位的扫描，用的时间也是很少的，如果这个是在别的系统中的话，我觉得提高效率应该考虑系统的其他部分。

MMMIX

原帖由 heavyrain44 于 2007-5-24 09:03 发表
我想请教一个算法，有一无符号32位整数，求其右边第一位数起到第一个位为‘1’的0的个数。
如0x21c534a8，则返回3；0x1b94a4c0，则返回6。
用循环好做，但时间复杂度不是常数。有时间复杂度为常数的算法吗，谢谢 ...

先考虑简单的实现，测试一下速度，如果不符合你的要求再考虑优化吧。要不也可以直接在网上搜索较快的算法。

yuxh

可以折半查找，但总共就32位，意义不大。
象这样：

1. 
   
2.     unsigned int mask = 0x0000ffff;
   
3.     for(i=16; i > 0; i >>= 1, mask >>= i)
   
4.     {
   
5.         if( (n&mask) == 0)
   
6.         {
   
7.             m += i;
   
8.             n >>= i;
   
9.         }
   
10.     }
    
11.     if(n == 0) m++;
    
12.     return m;
    

复制代码

只在理论上成立，实际的效果我很怀疑还不如循环32次

FreeGnu

1. 
   
2. unsigned int num = 0x12345678;
   
3. unsigned int table[32] = {0x00000001, 0x00000002, .....};
   
4. do{
   
5. if(num & table[0]){
   
6.    printf("0\n");
   
7.    break;
   
8. }
   
9. if(num & table[1]){
   
10.    printf("1\n");
    
11.    break;
    
12. }
    
13. .......
    
14. }while(0);
    

复制代码

[ 本帖最后由 FreeGnu 于 2007-5-24 12:41 编辑 ]

zenglj

unsigned int num = 0x12345678;
unsigned int count = 0;
while(1)
{
if(num & 0x00000001)
{
   printf("%d\n", count );
   break;
}
num = num>>1;
count++;
}

这样简洁些嘛

[ 本帖最后由 zenglj 于 2007-5-24 15:47 编辑 ]

emacsnw

二分：

1. 
   
2. int ntz(unsigned x) {
   
3.    int n;
   
4. 
   
5.    if (x == 0) return(32);
   
6.    n = 1;
   
7.    if ((x & 0x0000FFFF) == 0) {n = n +16; x = x >>16;}
   
8.    if ((x & 0x000000FF) == 0) {n = n + 8; x = x >> 8;}
   
9.    if ((x & 0x0000000F) == 0) {n = n + 4; x = x >> 4;}
   
10.    if ((x & 0x00000003) == 0) {n = n + 2; x = x >> 2;}
    
11.    return n - (x & 1);
    
12. }
    
13. 
    

复制代码

lz_fine

假设该数为x，那么x - (x & (x - 1))就是一个2的冥，然后就再进行处理，比如说取对数(但取对数时间复杂度是不是常数我就不知道了)或者查表(至于怎么设计表格你自己想想或者其他弟兄给个方法)。

SuperZ

这个就要看你在什么机器上跑了，有些机器比较怪异，直接就有这样的指令。

jigloo

考虑到《hackers delight》中的count_ones技巧， 有如下解决办法。

1. 
   
2. int count_ones(unsigned int x)
   
3. {
   
4.     x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
   
5.     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   
6.     x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
   
7.     x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
   
8.     x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
   
9. 
   
10.     return x;       
    
11. }
    
12. 
    
13. #define rfind_zeros(x) ((x)?count_ones((x)^((x)-1))-1:32)
    
14. 
    
15. int main(void)
    
16. {
    
17.         int n = 0x1;
    
18.         printf("%d\n", rfind_zeros(n));
    
19.         return 0;
    
20. }
    

复制代码

[ 本帖最后由 jigloo 于 2007-5-28 01:01 编辑 ]

MMMIX

原帖由 SuperZ 于 2007-5-27 23:48 发表
这个就要看你在什么机器上跑了，有些机器比较怪异，直接就有这样的指令。

对头，直接用汇编实现。