365. 二进制中有多少个1

2018-02-16  本文已影响15人  6默默Welsh

描述

计算在一个 32 位的整数的二进制表示中有多少个 1.

样例

给定 32 (100000),返回 1
给定 5 (101),返回 2
给定 1023 (1111111111),返回 10

挑战

If the integer is n bits with m 1 bits. Can you do it in O(m) time?

知识点

x & (x - 1) 可以消去二进制最右侧的 1

代码

public class Solution {
    /*
     * @param num: An integer
     * @return: An integer
     */
    public int countOnes(int num) {
        // 负数以补码形式存在,对于负数此算法也适用
        int count = 0;
        while (num != 0) {
            num = num & (num - 1);
            count++;
        }
        
        return count;
    }
}

错误代码

public class Solution {
    /*
     * @param num: An integer
     * @return: An integer
     */
    public int countOnes(int num) {        
        int count = 0;
        // 这么写 num 没更新
        while (num & (num - 1) != 0) {
            count++
        return count;
    }
};
上一篇下一篇

猜你喜欢

热点阅读