学步园

今天闲来无事，到定王台买了一本《编程之美》。这书上的题目确实不错，可要是看懂，也是有难度的。以后打算每天看一小节吧。

额，开始做那个题目吧。

       其实我以前刚开始搞ACM的时候就做过这个题目，真的。而且还是AC了的哦。那时候我的做法是：……偶都不好意思说了。不过反正这个blog没有人看的，也没有啥不好意思。那时候我的做法是把整数转换为二进制，再把二进制存到一个字符串里面……后面的我的就不多说了。

      废话不说，贴编程之美上面的代码。

int count1(int a)<br /> {<br /> int num = 0;<br /> while(a)<br /> {<br /> if(1 == a % 2)//如果是奇数，二进制的末尾一定是1<br /> {<br /> num++;<br /> }<br /> a /= 2;<br /> }<br /> return num;<br /> }</p> <p>int count2(int a)<br /> {<br /> int num = 0;<br /> while(a)<br /> {<br /> num += a & 0x01;//和1相与，这个可比取模之后和1相比快多了哦<br /> a >>= 1;//右移一位，相当于除以2<br /> }<br /> return num;<br /> }</p> <p>int count3(int a)<br /> {<br /> int num = 0;<br /> while(a)<br /> {<br /> a &= (a-1);//这个是复杂度最低的，为log2(x);x为a中1的个数。怎么解释呢……有点难度啊。自己模拟一下就明白了。<br /> num++;<br /> }<br /> return num;<br /> }</p> <p>int count4(int a)<br /> {<br /> /*额，因为题目限定的类型是BYTE，最大为255，书中还用了一种打表的方法，典型的用空间换时间。偶就不写了*/<br /> }

      最后书后面给了一个习题：给定两个正整数（二进制形式表示）A和B，问把A变为B需要改变多少位（bit）？也就是说，整数A 和B 的二进制表示中有多少位是不同的？偶写了一个代码。

int difCount(int a, int b)<br /> {<br /> int num = 0;<br /> while(a || b)<br /> {<br /> if((a & 0x01) != (b & 0x01))<br /> num++;<br /> a >>= 1;<br /> b >>= 1;<br /> }<br /> return num;<br /> }

显然，这个代码太傻B了。再给一个看上去优雅一点的代码。

int difCount(int a, int b)<br /> {<br /> int temp = a ^ b;<br /> int num = count2(temp);//调用求二进制中1的个数的函数<br /> return num;<br /> }

话说这本书最后还给出了一个网页，这里面还有更好的解法，各位有兴趣的话就去See One See吧。

http://blog.csdn.net/bvbook/archive/2008/04/15/2292823.aspx