位运算解决二进制中1的个数

2017-03-30 16:24 阅读 259 次 评论 0 条

可能会引起死循环的解法

基本思路: 先判断整数二进制表示中最右边的一位是不是1,接着把输入的整数右移一位,此时,原来处于从右边数起的第二位被移到了最右边,再判断是否为1,直到整数变为0为止。当然这样的方法很简单,我们只需要将整数与1做位与运算看结果来判断是否为1。

上面的函数如果输入一个负数,比如0x8000000(32位系统下)。把舒服0x80000000右移一位的时候,并不是简单地把最高位的1移到第二位变成0x40000000,而是0xC0000000,这是因为移位前是个负数,仍然要保证移位后也是个负数,因此移位后的最高位会设为1,这样最终这个数字就会变成0xFFFFFFFF而变成死循环。

常规解法

为了便面死循环,我们将不再使用右移运算,而是将整数n与1做与运算,来判断最低位是否为1,然后将1左移一位,就可以判断次低位是否为1,依次类推。

这个解法避免了死循环的不安全性,但是却付出了时间上的浪费,所以这样的程序依旧是不完美的。为了减少循环的次数,我们引入了下面的算法。

高效率解法

我们将一个整数减去1,再和原整数相与,会把该整数最右边的一个1变成0,那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。

大家可以看出,这样的算法原理其实很简单,但是对于算法题来说,最重要的就是高效率,即最优解。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:位运算解决二进制中1的个数 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情