看到这个问题我们的第一反应就是根据二进制的位直接统计,这也是我已开始想到的,于是有了如下代码
这份代码的逻辑很清晰,就是将这个数慢慢的移,每一位都进行判断最终得出结果,乍一看没什么错误。并且进行测试会发现对于正整数它运行的非常好,没有什么错误,但是我们尝试一下负整数就会发现他有巨大的问题。
这里首先要提一下,计算机对负数的存储是按照其正数的补码表示的,所以进行这种简单的移位判断就不可避免的会出现错误。
这里我们就要提到第二中解法,这种方法不金额以解决负数的问题,而且可以提高算法的效率。先看代码:
这种解法的精髓就在这个操作上面,我们首先要考虑x和x-1的二进制的差别在哪,我们列出几个
从这些例子我们不难发现,这两个数存在着这么一个关系:x的最后一个一变成了零,其后(可能没有)的零变成了一。于是我们可以发现只要将两个数进行与操作,那么最后一个一以及它后面的就都置零了,通过判断可以进行多少次这样的操作就可以知道有多少个一。
判断有多少零只需要将判断改一下就好。