algorithm


计算二进制整数中含有的1的个数的奇偶性

Table of Contents 问题描述 解决方案 问题描述 遇到过一个问题:判断一个数的二进制表示中含有的1的个数是偶数的还是奇数的。按照之前的做法,我会写一个循环,然后挨个判断这个数中每个位,记录下其中值为“1”的位的个数,最后给出结果。这种方法简单、直接,效率嘛,一般般,也没什么不好的。这两天在看《深入理解计算机系统》,其中有一道习题就是这个问题,而且还限制了不能用条件语句和循环语句来实现。这下,我就傻眼了。 解决方案 自己想了半天还是没有想到解决方案,不得以只能向Google求救,功夫不负有心人,总算让我找到解决方案了: /* Return 1 when x contains an odd number of 1s; 0 otherwise. Assume w=32. */ int odd_ones(unsigned x) { /* assume type unsigned take place 4 bytes */ x = (x >> 16) ^ x; x = (x >> 8) […]