Understanding java BigInteger.bitCount method on negative number

Question

This method BigInteger.bitCount() "Returns the number of bits in the two's complement representation of this BigInteger that differ from its sign bit."

If the number is positive, it is the count of 1 bits in the number.

I have difficulty to get the negative number right.

For example, number -1377605392 's binary representation is -1010010000111001001011100010000. It has 12 1s and 19 0s.

But java code BigInteger.valueOf((long)-1377605392) give result of 15!!

How does this 15 is calculated?

Answer 1

The two's complement representation of a binary number means:

• subtract 1
• switch all 1 to 0 and 0 to 1

Compare the two's complement of -1377605392 with the corresponding positive number:

1111111111111111111111111111111110101101111000110110100011110000
0000000000000000000000000000000001010010000111001001011100010000

As you can see, all bits are flipped, except the trailing zeroes.

However, in BigInteger, negative numbers are stored as the absolute (that is: positive) value with a separate sign-bit, so to count the number of 0 in a negative number, the pasted code counts the number of 1 in the absolute value, adds the number of trailing zeroes (which are still 0) and subtracts 1 (for the last 1 which is still there)

The reason for using two's complement is that it makes basic arithmetics really simple, and the logic can ignore the sign. For example (using 8-bit numbers for simplicity):

 6 = 00000110
-2 = 11111110
 4 = 00000100 (adding together with carry)

You should do som excercises on paper with smaller numbers to understand how this works.