计算整数的二进制表示里1的位数

编程计算给定的整数在用二进制来表示时含有多少个 1。

分析

假定以高位在前、低位在后的形式,一个整数的二进制表示为:000110100;当该整数减1时,由于低位是0,所以会一直往高位借位,直至碰到最低位的1(竖线后面的那个1):000110|100;减1之后整数那个最低位1变为0,之后的位都变为1:000110|011;此时进行 i & (i-1) 就会让竖线后面的都变为0:


000110|100  i
000110|011  i-1
000110|000  i&(i-1)

1110  -2
1101  -2 - 1
1100  -2 & (-2 - 1)

所以 i = i & (i-1) 都会让 i 里的位为 1 的个数减一。对于负数,同样具有这样的性质。

实现


func CountBitsInInteger(integer int) int {
     count := 0
    for integer != 0 {
        count++
        integer = integer & (integer - 1)
    }

    return count
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据