1 /**
  2  参考的剑指offer
  3  */
  4 #include <stdio.h>
  5 
  6 int numberOf1(int n);
  7 int betterNumberOf1(int n);
  8 _Bool judgeIs2Cifang(int n);
  9 int numberOfTransform(int m, int n);
 10 
 11 int main(int argc, const char * argv[]) {
 12     
 13     int n;
 14     int countOf1;
 15     int betterCountOf1;
 16     _Bool is2Cifang;
 17     int transformCount;
 18     int transM,transN;
 19     
 20     while (1) {
 21         printf("请输入一个整数:\t");
 22         scanf("%d",&n);
 23         countOf1 = numberOf1(n);
 24         betterCountOf1 = betterNumberOf1(n);
 25         is2Cifang = judgeIs2Cifang(n) ? 1 : 0;
 26         
 27         
 28 
 29     
 30         printf("%d\t转换为二进制之后含有1的个数为\t%d\n\n",n,countOf1);
 31         printf("%d\t转换为二进制之后含有1的个数为\t%d\n\n",n,betterCountOf1);
 32         if(is2Cifang){
 33             printf("%d\t是2的整数次方\n\n",n);
 34         }else{
 35             printf("%d\t不是2的整数次方\t\n\n",n);
 36         }
 37         
 38         
 39         printf("输入待相互转化的两个数:\t");
 40         scanf("%d %d",&transM,&transN);
 41         transformCount = numberOfTransform(transM, transN);
 42         printf("%d和%d转化需要的次数是%d\n\n",transM,transN,transformCount);
 43         
 44         
 45         
 46     }
 47     
 48     return 0;
 49 }
 50 
 51 
 52 /**
 53  求1的个数
 54 
 55  @param n 所求的数
 56 
 57  @return 传进去的数的二进制形式中1的个数
 58  */
 59 int numberOf1(int n){
 60     int count = 0;
 61     while (n)
 62     {
 63         if ((n & 1)){
 64             count ++;
 65         }
 66         n = n >> 1;
 67         
 68     }
 69     return count;
 70     
 71 
 72 }
 73 
 74 
 75 /**
 76  求一个数二进制形式中1的个数的更优解
 77 
 78  @param n 传进去的待求的参数
 79 
 80  @return 返回的待求参数的二进制形式中1的个数
 81  */
 82 int betterNumberOf1(int n){
 83     
 84     int count = 0;
 85     while(n){
 86         count++;
 87         //每一次做下列操作都会使得这个待求的数的二进制的形式中少1个1 这样的好处是减少比较的次数
 88         n = n & (n-1);
 89     }
 90     return count;
 91 }
 92 
 93 
 94 /**
 95  相关的问题有：
 96     1.当判断一个数字a是否是2的整数次方的时候
 97     2.当判断给定的2个数m,n;
 98     每次改变二进制形式的1个1; 
 99  
100     m要经过几步转变为n的时候会用到异或;  
101     异或的结果 的二进制的形式含有几个1 就需要相应的几步转换为对方。
102  
103  */
104 
105 
106 /**
107  判断一个数是否是2的整数次方
108 
109  @param n 传进去的待求参数
110 
111  @return 返回的是布尔类型的是否是2的整数次方
112  */
113 _Bool judgeIs2Cifang(int n){
114     
115     return (n & (n-1))? 0 : 1;
116 }
117 
118 
119 
120 /**
121  两个数的二进制的形式相互转换的时候需要改动的次数
122 
123  @param p 参数p
124  @param q 参数q
125 
126  @return 返回p q相互转换所需的次数
127  */
128 int numberOfTransform(int p, int q){
129     
130     int count = betterNumberOf1(p ^ q);
131     return count;
132     
133 
134     
135 }