一、题目

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制1001，有2位1。因此如果输入9，该函数输出2。

二、解题思路

Notzuonotdied

第一种思路

1. 假如是9【两个1】：
   • 9 & 8 = 1001 & 1000 = 1000 = 8 不为0；
   • 8 & 7 = 1000 & 0111 = 0
2. 假如是8【一个1】：
   • 8 & 7 = 1000 & 0111 = 0
3. 假如是7【三个1】：
   • 7 & 6 = 0111 & 0110 = 0110 = 6 不为0；
   • 6 & 5 = 0110 & 0101 = 0100 = 4 不为0；
   • 4 & 3 = 0100 & 0011 = 0 = 4
4. 假如是6【两个1】：
   • 6 & 5 = 0110 & 0101 = 0100 = 4 不为0；
   • 4 & 3 = 0100 & 0011 = 0 = 4
5. 假如是5【两个1】：
   • 5 & 4 = 0101 & 0100 = 0100 = 4 不为0；
   • 4 & 3 = 0100 & 0011 = 0
6. 总结上述思路：
   • 使用循环的形式$n & (n - 1)$来统计有几个二进制的1。

第二种思路

1. 9的二进制为：1001
2. 采用无符号右移的方式，循环移位。
   • 简述过程：
   • 1001 & 0001 = 1
   • 0100 & 0001 = 0
   • 0010 & 0001 = 0
   • 0001 & 0001 = 1
   • 总计两个二进制的1。

Kotlin实现

fun main(args: Array<String>) {
    println(countOne(9))
    println(countOne2(9))
}

fun countOne(what: Int): Int {
    var count = 0
    var temp = what

    while (temp != 0) {
        ++count
        // 9 & 8 = 1001 & 1000 = 1000 = 8 不为0，
        // 8 & 7 = 1000 & 0111 = 0
        // 刚好两个
        temp = (temp - 1) and temp
    }

    return count
}

fun countOne2(what: Int): Int {
    var count = 0
    var temp = what

    // 因为Kotlin的Int类型的长度为4字节，总共32位
    for (i in 0..32) {
        // 与1相与，统计为1的个数
        count += temp and 1
        // 无符号右移
        temp = temp ushr 1
    }

    return count
}

输出结果

2
2