求无符号整数二进制中 1 的个数??
思路:看一个八位整数 10 100 001
,先判断最后一位是否为 1 ,而“与”操作可以达到目的。可以把这个八位的数字与 00000001
进行“与
”操作。如果结果为 1 ,则表示当前八位数的最后一位为 1 ,否则为 0 。怎么判断第二位呢?向右移位,再延续前面的判断即可。
func numsOfones(num: UInt) -> UInt {
var count : UInt = 0
var tempp = num
while tempp != 0 {
count += tempp & 1
tempp = tempp >> 1
}
return count
}
numsOfones(num: 7)
// 3
思考: 如果整数的二进制中有较多的 0 ,那么我们每一次右移一位做判断会很浪费,怎么改进前面的算法呢?有没有办法让算法的复杂度只与“1”的个数有关?
为了简化这个问题,我们考虑只有高位有 1 的情况。例如:11 000 000 ,如何跳过前面低位的 6 个 0 ,而直接判断第七位的 1 ?我们可以设计 11 000 000 和 10 111 111(也就是 11 000 000 - 1)做“与”操作,消去最低位的 1 。如果得到的结果为 0 ,说明我们已经找到/消去里面最后一个 1 。如果不为 0 ,那么说明我们消去了最低位的 1 ,但是二进制中还有其他的 1 , 我们的计数器需要加 1 ,然后继续上面的操作。
func numsOfones(num: UInt) -> UInt {
var count : UInt = 0
var tempp = num
while tempp != 0 {
count += 1
tempp = tempp & (tempp - 1)
}
return count
}
numsOfones(num: 0x101011)
网友评论