191. 位1的个数

解法一：取余

对数取余，余数为1，则 count ++，然后每次取余后左移一位

时间复杂度：常数级 O(1)

代码一：取余会超时，改用位运算 X & -X 判断低位是否为1

class Solution {
    // you need treat n as an unsigned value
    fun hammingWeight(n: Int): Int {
        var x = n
        var count = 0
        for (i in 0 until 32) {
            if (x and -x == 1) {
                count++
            }
            x = x.shr(1)
        }
        return count
    }
}

代码二：改用位运算 X & 1 判断低位是否为1 也可

class Solution {
    // you need treat n as an unsigned value
    fun hammingWeight(n: Int): Int {
        var x = n
        var count = 0
        for (i in 0 until 32) {
            if (x and 1 == 1) {
                count++
            }
            x = x.shr(1)
        }
        return count
    }
}

解法二：利用位运算 每次消除一个1

上节课讲到：X = X & (X-1) => 清零最低位的1

于是可以写一个循环，每次消除一个1，直到等于0（变成全0）为止。

时间复杂度：O(二进制中1的个数) 常数级 O(1)

class Solution {
    // you need treat n as an unsigned value
    fun hammingWeight(n: Int): Int {
        var x = n
        var count = 0
        while (x != 0) {
            count++
            x = x and (x - 1)
        }
        return count
    }
}

最坏情况下（全1数字）两者解法效率一致，为：O(二进制位数)