昨天去金山面试的一道题

tzm529

Post by biinn;2076626
假设整数不超过32位：

2. int get_bit(int val)
3. {
4.     int b, i;
6.     for (b = 31, i = 1<<31; i && !(val & i); b--, i>>1) ;
7.     return b;
8. }

复制代码

i>>1那里错了。

2. int get_bit(unsigned int val)
3. {
4.         unsigned int b, i, s = sizeof( int) * 8 - 1;
5.         for(b = s, i = 1<<s; i && !(val & i);b--,i>>=1);
6.         return b;
7. }

复制代码

biinn

Post by tzm529;2077142
i>>1那里错了。

非常感谢更正!

skor

Post by biinn;2076626
假设整数不超过32位：

1. 
   
2. int get_bit(unsigned int val)
   
3. {
   
4.     int b, i;
   
5. 
   
6.     for (b = 31, i = 1<<31; i && !(val & i); b--, i>>=1) ;
   
7.     return b;
   
8. }
   

复制代码

最后 return (int)b<0?0:b; 比较好, 不然如果 val 是 0 的话就不对了.

haohao_h

Post by tzm529;2076619
给定一个无符号整型数，试完成一个程序， 它求出这个数的二进制最高位是第几位（最低位为0）。例如，十六进制数0xFF，其最高位为第7位
我的程序如下:

1. 
   
2. int get_bit(int val)
   
3. {
   
4.         //mod为模值,sub_val为除2后的值, bit为最高位值,作为返加值, zero_count为当前0的个数
   
5.         int  mod,sub_val, bit, zero_count;   
   
6.         if(val <= 0)
   
7.                 return 0;
   
8.         sub_val = val;
   
9.         mod = bit = zero_count = 0;
   
10.         while(sub_val > 0)
    
11.         {                 
    
12.                 mod = sub_val % 2;
    
13.                 sub_val = sub_val / 2;
    
14.                 if(mod != 0)
    
15.                 {
    
16.                         bit += zero_count + 1;
    
17.                         zero_count = 0;
    
18.                 }
    
19.                 else
    
20.                 {
    
21.                         zero_count++;
    
22.                 }
    
23.         }
    
24.         return bit - 1;
    
25. }
    
26. 结果他说这个程序其实可以再优化的.有些东西是可以不要的,当时我想了很久，各位能帮忙看看吗。
    

复制代码

1. 
   
2. int get_bit(unsigned int val)
   
3. {
   
4.     int i=0, ret=val;
   
5.     for(;ret!=0;ret &=ret-1)
   
6.         {
   
7.                 i++;
   
8.         }
   
9.     return i-1;
   
10. }
    

复制代码

haohao_h

1. 
   
2. int get_bit(unsigned int val)
   
3. {
   
4.     int i=0;
   
5.     for(i=0;i<32;i++)
   
6.         {
   
7.                 if(val&(1<<(31-i)))
   
8.                 {
   
9.                         break;
   
10.                 }
    
11.         }
    
12.     return 31-i;
    
13. }
    

复制代码

jruv

val == 0 返回-1, 其他返回最高位

2. int get_bit(unsigned int val)
3. {
4.     int n = sizeof(int) * 8;
5.     while(--n >= 0 && !(val >> n));
6.     return n;
7. }

复制代码