这个题目是生算出来的吗

aore2010

1. #include <stdio.h>
   
2. 
   
3. int f(int x) {
   
4.         int c = 0;
   
5.         while(x!=0) {
   
6.                 x = x & (x-1);
   
7.                 c++;
   
8.         }
   
9.         return c;
   
10. }
    
11. 
    
12. int main () {
    
13.         int a = 65536 + 1024 + 8 + 1;
    
14.         int b = f(a);        //执行后b等于多少?
    
15.         printf("%d\n",a);
    
16.         printf("%d\n",b);
    
17.        
    
18.         return 0;
    
19. }

复制代码

这个是生算出来的么 我看不出其中有什么简便推导方法 请各位指教 多谢

hbmhalley

设 x % (2^k) == 0 且 x % (2^(k+1)) != 0 ，
那么 (x & (x-1)) == x - 2^k

比如 x==12时k==2,2^k==4
(x&(x-1)) == 12-4 == 8

为什么就不解释了 稍微想想就知道

那么
a == (2^16) + (2^10) + (2^3) + (2^0)
b ==     1      +     1      +     1    +    1     == 4

aore2010

回复 2# hbmhalley


    比如 x==12时k==2,2^k==4
(x&(x-1)) == 12-4 == 8
  
这句没看懂 为什么 x=12时 k=2呢

hbmhalley

回复 3# aore2010


    12%4 == 0
    12%8 == 4

aore2010

回复 4# hbmhalley


    没看太明白 那个k是通过12猜出来的么 如果不是12 是其他很大的数组 比如 134538 或者 12487 等等 该怎么计算呢

hbmhalley

回复 5# aore2010


    别纠结这个了 目的是让你拆成二进制看
    比如12 = (1100)2 ; 24 = (11000)2 ; 40 = (101000)2
    拿40说事：最右边的1及其后面的0构成 (1000)2 我说的2^k就是(1000)2，k就是0的个数：3。当然现在关于k的这些已经不重要了
    (101000)2 - 1 = (100111)2    只有原来 (1000)2 这部分变了。其实所有二进制数减一都是这个特点。不难理解吧
    如果拿原来的 (101000)2 和减一后的 (100111)2 做 '&' 运算，那么除了(1000)2这部分外，左边的都不动，右边的一定是0。结果是 (100000)2。也不难理解吧。
    所以每做一次 x=x&(x-1)，其二进制表示里的1就少一个。
    所以答案就是 x 二进制表示里 1 的个数

_Rayx

跟机器相关哈，不过f函数可以很容易看出是求x有多少个位是1.

aore2010

回复 6# hbmhalley
多谢多谢 呵呵