昨天去金山面试的一道题

tzm529

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

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. 结果他说这个程序其实可以再优化的.有些东西是可以不要的,当时我想了很久，各位能帮忙看看吗。

复制代码

biinn

假设整数不超过32位：

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

复制代码

kingway

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

1. 
   
2. int get_bit(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. }
   

复制代码

够简洁，效率够高的说。。。。

jigloo

这种老调的函数真是的，
自己去看kernel的__ffs函数实现，那才是真正写的好的。

jigloo

更多技巧请看hacker's delight, 学C语言的必看书

jigloo

这是这本书的来源，
http://graphics.stanford.edu/~seander/bithacks.html
多看看

biinn

Post by jigloo;2076631
这种老调的函数真是的，
自己去看kernel的__ffs函数实现，那才是真正写的好的。

看你求什么了；求速度，用kernel的；求空间，用我的 ;)
bty, 在我的函数中, 把 31 换成 sizeof(int) * 8 -1 就不用那个假设了。

jigloo

真是的，误人子弟。

tzm529

长见识了...
果然很牛!
惭愧啊。。

biinn

Post by jigloo;2076641
真是的，误人子弟。

甭担心, 我不是老师, 误也就误一个半个...