题

编程计算给定的整数在用二进制来表示时含有多少个 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
}

欢迎关注我的微信公众号: coderbee笔记，可以更及时回复你的讨论。