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?

Try Long.bitCount(4294967295L).

user4910279
– user4910279

2016-02-22 07:33:43 +00:00
Commented Feb 22, 2016 at 7:33 — user4910279
– user4910279, Commented Feb 22, 2016 at 7:33

Gayan Weerakutti · Accepted Answer · 2018-09-02 14:40:12Z

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.

Elliott Frisch · Accepted Answer · 2016-02-22 06:51:00Z

7

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)

edited Feb 22, 2016 at 6:51

answered Feb 22, 2016 at 6:33

Elliott Frisch

202k20 gold badges166 silver badges265 bronze badges

4 Comments

Yun Li Over a year ago

Thanks so much for your prompt reply. Could you please tell me why I got the result 31 from my code? If I right shift the original value (11111111111111111111111111111111) 31 times, shouldn't I get 1 and finally get the result 32?

matt Over a year ago

@YunLi because the input value is -1. -1%2 = -1, you could change the condition to !=0 and it will work for your example.

weston Over a year ago

The OP has correctly used >>> so it really shouldn't need long. The fix is purely the use of & 1 over % 2

Elliott Frisch Over a year ago

@weston Edited and tested.

matt · Accepted Answer · 2016-02-22 07:00:04Z

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.

Collectives™ on Stack Overflow

count Number of 1 Bits in java

3 Answers 3

Comments

4 Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

4 Comments

1 Comment

Related