剑指offer—面试题15:二进制中1的个数

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

根据位运算的方式， 0 或者 1 & 1得到的结果和原来的数一致，我们可以通过不断的左移数字n，根据最右位上 & 1，判断是否是1。

右移n算法：

    func hammingWeight(_ n: Int) -> Int {
        var n = n
        var res = 0
        while n != 0 {
            if n & 1 == 1 {
                res += 1
            }
            n = n >> 1
        }
        return res
    }

算法二： n&(n-1)

• (n−1) ： 二进制数字 n 最右边的数如果是 1 则变成 0，其它不变 。如果是0，则 n 最右边的1的变成0，1 右边的 0 都变成 1 。1001 - 1 = 1000， 1100 - 1 = 1011。
• n&(n−1) ： 二进制数字 n 最右边的 1 变成 0 ，其余不变。1001 & 1000 = 1000，1100 & 1011 = 1000。

    func hammingWeight(_ n: Int) -> Int{
        var n = n
        var res = 0
        while n != 0{
                res += 1
                n &= n - 1
        }
            return res
    }

算法的时间复杂度： O(M)，其中M表示二进制数字 n 中 1 的个数，则需循环 M 次（每轮消去一个 1 ）。