[LintCode] Count 1 in Binary [典型位运算题目]

java 21 2016-02-29 13:03

Problem

Count how many 1 in binary representation of a 32-bit integer.

Example

Given 32, return 1

Given 5, return 2

Given 1023, return 9

Challenge

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

Note

这道题,Olivia给我解决了两个疑问,还剩一个。首先是要用无符号右移运算符>>>,其次是可以用一个不断左移的二进制1作为参照。那么如何获得一个用1来进行补位的左移的1呢?
第一种解法,num右移,每次对末位进行比较,直到num为0;
第二种解法,1左移,每次和num的第i位比较,直到i = 32;
第三种解法,num和num-1逐位与,去1,直到num为0。

Solution

1.

public class Solution {
    public int countOnes(int num) {
        int count = 0;
        while (num != 0) {
            count += (num & 1);
            num >>>= 1;
        }
        return count;
    }
};

2.

public class Solution {
    public int countOnes(int num) {
        int count = 0;
        for(int i = 0 ; i < 32; i++) {
            if((num & (1<<i)) != 0)
                count++;
        }
        return count;
    }
}

3.

public class Solution {
    public int countOnes(int num) {
        int count = 0;
        while (num != 0) {
            num &= num - 1;
            count++;
        }
        return count;
    }
}

// 1111 1110 1110
// 1110 1101 1100
// 1100 1011 1000
// 1000 0111 0000

文章评论