c语言，检测一个无符号整数中是否有偶数位个1

最近在学习大牛Bryant O'Hallaron 的深入理解计算机系统，发现学了这么久的程序设计，其实有些基本的东西还不太了解，这不，这两天在恶补整数，浮点数在计算机中的表示，并且开始做上面的习题，

因为刚开始，主要是做位运算方面的练习，这个以前没怎么重视，但是实在太重要了，搞不清楚位运算的别说自己编程很NB！

书里正好有这么一道习题2.65，就是检测一个无符号数的数位是否有偶数个1，而且要求不能超过12次基本运算！！那么，我就根据位运算中异或的想法来实现，这个想法就是，偶数位的个数实际上就是这个无符号整数中

所有1的和，那么对于32位的无符号整数，比如x1x2x3x4(xi=1字节），那么 x1x2^x3x4其实就是他们高2字节和低2字节的1的和(mod2),这样如果相同位上都有1的话，那么异或得0，其实就是模去了一个偶数，而奇数是

不会被模去的，结果是y1=x1x2^x3x4=y2,接下来再 y1^y2=z1,以此类推，直到最后剩下一位，如果这一位是0，则说明有偶数个2，否则就是奇数个2了，具体实现如下：

1 #include<stdio.h>
2 #include<stdlib.h>
3 #define UINT_LEN 4
4
5 //因为使用了循环，实际计算次数略多，但是并不影响题目的本质，如果不用循环则满足要求，而且本代码可以适用到64位整数上，只要定义UNIT_LEN 5
6 int even_ones(unsigned x){
7     int u = 1<<UINT_LEN;
8     int p=UINT_LEN-1;
9     unsigned tx=x;
10     unsigned ty=x>>u;
11     printf("0: u=%d, tx=%x, ty=%x\n",u,tx,ty);
12     while(p>=-1){
13         tx = tx^ty;
14         u = u>>1;
15         ty = tx>>u;
16         printf("%d, u=%d, tx=%x, ty=%x\n",UINT_LEN-p,u,tx,ty);
17         p--;
18     }
19     int odd = tx&1;
20     return !odd;
21 }
22
23 int main(int argc,char** argv){
24     if(argc!=2){
25         perror("incorrect number of arguments!\n");
26         exit(1);
27     }
28
29     unsigned u=(unsigned) atoi(argv[1]);
30
31     even_ones(u)? printf("%d has even 1s!\n",u):printf("%d has odd 1s!\n",u);
32     return 0;
33 }

巴特西

c语言，检测一个无符号整数中是否有偶数位个1

最新文章

热门文章