count Number of 1 Bits in java

Question

I encountered a strange problem while doing an leetcode problem. This is about bits representation in Java.

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

My solution is

public class Solution {
// you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for(int i = 0; i < 32; ++i){
            if((n >>> i) % 2 == 1){
                ++count;
            }
        }
        return count;
    }
}

This code is not accepted because of the input case:

4294967295 (11111111111111111111111111111111)

I reviewed the bit representation of integer in java but still do not know the problem of the solution? Could anyone help me?

Answer 1

public int hammingWeight(int n) {
    return Integer.bitCount(n);
}

Integer.bitCount(int i)

Returns the number of one-bits in the two's complement binary representation of the specified int value.

Answer 2

The issue is performing modulo when you want a bitwise &. Something like,

public static int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; ++i) {
        if (((n >>> i) & 1) == 1) {
            ++count;
        }
    }
    return count;
}

public static void main(String[] args) {
    int c = -1;
    System.out.println(hammingWeight(c));
}

Outputs (as expected)

32

Answer 3

Java uses twos compliment. So the negative bit is the far left one. That means if you have a number greater than Integer.MAX_VALUE your input will be a negative number. When you do %2the sign remains unchanged. An alternative would be to use &1which will change the sign bit. After the first iteration, and you have done a bit shift, the sign bit will be zero.