How are integers internally represented at a bit level in Java?

Question

I am trying to understand how Java stores integer internally. I know all java primitive integers are signed, (except short?). That means one less bit available in a byte for the number.

My question is, are all integers (positive and negative) stored as two's complement or are only negative numbers in two's complement?

I see that the specs says x bit two's complement number. But I often get confused.

For instance:

  int x = 15; // Stored as binary as is?  00000000 00000000 00000000 00001111?
  int y = -22; // Stored as two complemented value? 11111111 11111111 11111111 11101010

Edit

To be clear, x = 15

   In binary as is: `00000000 00000000 00000000 00001111'
  Two's complement: `11111111 11111111 11111111 11110001`

So if your answer is all numbers are stored as two's complement then:

  int x = 15; // 11111111 11111111 11111111 11110001
  int y = -22 // 11111111 11111111 11111111 11101010

The confusion here again is the sign says, both are negative numbers. May be I am misreading / misunderstanding it?

Edit Not sure my question is confusing. Forced to isolate the question:

My question precisely: Are positive numbers stored in binary as is while negative numbers are stored as two's complement?

Some said all are stored in two's complement and one answer says only negative numbers are stored as two's complement.

Solution 1

Let's start by summarizing Java primitive data types:

byte: Byte data type is an 8-bit signed two's complement integer.

Short: Short data type is a 16-bit signed two's complement integer.

int: Int data type is a 32-bit signed two's complement integer.

long: Long data type is a 64-bit signed two's complement integer.

float: Float data type is a single-precision 32-bit IEEE 754 floating point.

double: double data type is a double-precision 64-bit IEEE 754 floating point.

boolean: boolean data type represents one bit of information.

char: char data type is a single 16-bit Unicode character.

Source

Two's complement

"The good example is from wiki that the relationship to two's complement is realized by noting that 256 = 255 + 1, and (255 − x) is the ones' complement of x

0000 0111=7 two's complement is 1111 1001= -7

the way it works is the MSB(the most significant bit) receives a negative value so in the case above

-7 = 1001= -8 + 0+ 0+ 1

Positive integers are generally stored as simple binary numbers (1 is 1, 10 is 2, 11 is 3, and so on).

Negative integers are stored as the two's complement of their absolute value. The two's complement of a positive number is when using this notation a negative number.

Source

Since I received a few points for this answer, I decided to add more information to it.

A more detailed answer:

Among others there are four main approaches to represent positive and negative numbers in binary, namely:

1. Signed Magnitude
2. One's Complement
3. Two's Complement
4. Bias

1. Signed Magnitude

Uses the most significant bit to represent the sign, the remaining bits are used to represent the absolute value. Where 0 represents a positive number and 1 represents a negative number, example:

1011 = -3
0011 = +3

This representation is simpler. However, you cannot add binary numbers in the same way that you add decimal numbers, making it harder to be implemented at the hardware level. Moreover, this approach uses two binary patterns to represent the 0, -0 (1000) and +0 (0000).

2. One's Complement

In this representation, we invert all the bits of a given number to find out its complementary. For example:

010 = 2, so -2 = 101 (inverting all bits).

The problem with this representation is that there still exist two bits patterns to represent the 0, negative 0 (1111) and positive 0 (0000)

3. Two's Complement

To find the negative of a number, in this representation, we invert all the bits and then add one bit. Adding one bit solves the problem of having two bits patterns representing 0. In this representation, we only have one pattern for 0 (0000).

For example, we want to find the binary negative representation of 4 (decimal) using 4 bits. First, we convert 4 to binary:

4 = 0100

then we invert all the bits

0100 -> 1011

finally, we add one bit

1011 + 1 = 1100.

So 1100 is equivalent to -4 in decimal if we are using a Two's Complement binary representation with 4 bits.

A faster way to find the complementary is by fixing the first bit that as value 1 and inverting the remaining bits. In the above example it would be something like:

0100 -> 1100
^^ 
||-(fixing this value)
|--(inverting this one)

Two's Complement representation, besides having only one representation for 0, it also adds two binary values in the same way that in decimal, even numbers with different signs. Nevertheless, it is necessary to check for overflow cases.

4. Bias

This representation is used to represent the exponent in the IEEE 754 norm for floating points. It has the advantage that the binary value with all bits to zero represents the smallest value. And the binary value with all bits to 1 represents the biggest value. As the name indicates, the value is encoded (positive or negative) in binary with n bits with a bias (normally 2^(n-1) or 2^(n-1)-1).

So if we are using 8 bits, the value 1 in decimal is represented in binary using a bias of 2^(n-1), by the value:

+1 + bias = +1 + 2^(8-1) = 1 + 128 = 129
converting to binary
1000 0001

Solution 2

Java integers are of 32 bits, and always signed. This means, the most significant bit (MSB) works as the sign bit. The integer represented by an int is nothing but the weighted sum of the bits. The weights are assigned as follows:

Bit#    Weight
31      -2^31
30       2^30
29       2^29
...      ...
2        2^2
1        2^1
0        2^0

Note that the weight of the MSB is negative (the largest possible negative actually), so when this bit is on, the whole number (the weighted sum) becomes negative.

Let's simulate it with 4-bit numbers:

Binary    Weighted sum            Integer value
0000       0 + 0 + 0 + 0           0
0001       0 + 0 + 0 + 2^0         1
0010       0 + 0 + 2^1 + 0         2
0011       0 + 0 + 2^1 + 2^0       3
0100       0 + 2^2 + 0 + 0         4
0101       0 + 2^2 + 0 + 2^0       5
0110       0 + 2^2 + 2^1 + 0       6
0111       0 + 2^2 + 2^1 + 2^0     7 -> the most positive value
1000      -2^3 + 0 + 0 + 0        -8 -> the most negative value
1001      -2^3 + 0 + 0 + 2^0      -7
1010      -2^3 + 0 + 2^1 + 0      -6
1011      -2^3 + 0 + 2^1 + 2^0    -5
1100      -2^3 + 2^2 + 0 + 0      -4
1101      -2^3 + 2^2 + 0 + 2^0    -3
1110      -2^3 + 2^2 + 2^1 + 0    -2
1111      -2^3 + 2^2 + 2^1 + 2^0  -1

So, the two's complement thing is not an exclusive scheme for representing negative integers, rather we can say that the binary representation of integers are always the same, we just negate the weight of the most significant bit. And that bit determines the sign of the integer.

In C, there is a keyword unsigned (not available in java), which can be used for declaring unsigned int x;. In the unsigned integers, the weight of the MSB is positive (2^31) rather than being negative. In that case the range of an unsigned int is 0 to 2^32 - 1, while an int has range -2^31 to 2^31 - 1.

From another point of view, if you consider the two's complement of x as ~x + 1 (NOT x plus one), here's the explanation:

For any x, ~x is just the bitwise inverse of x, so wherever x has a 1-bit, ~x will have a 0-bit there (and vice versa). So, if you add these up, there will be no carry in the addition and the sum will be just an integer every bit of which is 1.

For 32-bit integers:

x + ~x = 1111 1111 1111 1111 1111 1111 1111 1111
x + ~x + 1 =   1111 1111 1111 1111 1111 1111 1111 1111 + 1
           = 1 0000 0000 0000 0000 0000 0000 0000 0000

The leftmost 1-bit will simply be discarded, because it doesn't fit in 32-bits (integer overflow). So,

x + ~x + 1 = 0
-x = ~x + 1

So you can see that the negative x can be represented by ~x + 1, which we call the two's complement of x.

Solution 3

I have ran the following program to know it

public class Negative {
    public static void main(String[] args) {
        int i =10;
        int j = -10;

        System.out.println(Integer.toBinaryString(i));
        System.out.println(Integer.toBinaryString(j));
    }
}

Output is

1010
11111111111111111111111111110110

From the output it seems that it has been using two's complement.

Solution 4

Oracle provides some documentation regarding Java Datatypes that you may find interesting. Specifically:

int: The int data type is a 32-bit signed two's complement integer. It has a minimum value of -2,147,483,648 and a maximum value of 2,147,483,647 (inclusive).

Btw, short is also stored as two's complement.

Solution 5

Positive numbers are stored/retrived as it is.

e.g) For +ve number 10; byte representation will be like 0-000 0010 
                                               (0 - MSB will represent that it is +ve).
So while retrieving based on MSB; it says it is +ve, 
so the value will be taken as it is. 

But negative numbers will be stored after 2's complement (other than MSB bit), and MSB bit will be set to 1.

e.g) when storing -10 then

  0-000 0010  -> (1's complement) -> 0-111 1101 
              -> (2's complement) 0-111 1101 + 1 -> 0-111 1110
  Now MSB will be set to one, since it is negative no -> 1-111 1110

when retrieving, it found that MSB is set to 1. So it is negative no. And 2's complement will be performed other than MSB.

  1-111 1110  --> 1-000 0001 + 1 --> 1-000 0010
  Since MSB representing this is negative 10 --> hence  -10 will be retrived.

Casting

Also note that when you are casting int/short to byte, only last byte will be considered along with last byte MSB,

Take example "-130" short, it might be stored like below

(MSB)1-(2's complement of)130(1000 0010) --> 1-111 1111 0111 1110

Now byte casting took last byte which is 0111 1110. (0-MSB) Since MSB says it is +ve value, so it will be taken as it is. Which is 126. (+ve).

Take another example "130" short, it might be stored like below

  0-000 000 1000 0010     (MSB = 0)

Now byte casting took last byte which is 1000 0010 . (1=MSB) Since MSB says it is -ve value, 2's complement will be performed and negative number will be returned. So in this case -126 will be returned.

 1-000 0010  -> (1's complement) -> 1-111 1101 
             -> (2's complement) 1-111 1101 + 1 -> 1-111 1110 -> (-)111 1110
               = -126

Diff between (int)(char)(byte) -1 AND (int)(short)(byte) -1

(byte)-1       -> 0-000 0001 (2's Comp) -> 0-111 1111 (add sign) -> 1-111 1111
(char)(byte)-1 -> 1-111 1111 1111 1111  (sign bit is carry forwarded on left) 

similarly

(short)(byte)-1-> 1-111 1111 1111 1111  (sign bit is carry forwarded on left) 

But

(int)(char)(byte)-1 -> 0-0000000 00000000 11111111 11111111  = 65535
since char is unsigned; MSB won't be carry forwarded. 

AND

(int)(Short)(byte)-1 -> 1-1111111 11111111 11111111 11111111 = -1
since short is signed; MSB is be carry forwarded. 

References

Why is two's complement used to represent negative numbers?

What is “2's Complement”?

View more solutions

Comments

[Kevin Rave]

My question precisely: Are +ve numbers stored in binary as is while -ve numbers are stored in two's complement?

[Kevin Rave]

Twos complement of 10 is 11111111 11111111 11111111 11110110. Yours prints while Binary as is for 10 is 1010. So only -ve numbers are stored as two's complement?

[Dungeon Hunter]

check the wiki article en.wikipedia.org/wiki/… the 2's complement number you have given for 15 is wrong

[Dungeon Hunter]

if the msb bit starts with 1 it will be negative number

[Sufian Latif]

Well, yes. a negative number is represented to a computer as the two's complement of its positive value.

[Dungeon Hunter]

yes two's complement of 10 is 11111111 11111111 11111111 11110110 which is -10

[Dungeon Hunter]

+ve numbers will be stored as binary leaving the sign bit in 2's complement

[Shashi]

"In two’s complement format, a positive value is represented as a straightforward binary number." written in the same document .. so technically it's correct then. :)

[Kanagavelu Sugumar]

stackoverflow.com/questions/11380062/…

[Abhishek Singh]

@0605002: Could you please give the reference to this answer, if any? Though I knew the concepts but never really thought them in that way. Simplest, still accurate Answer.

[Prashant Pandey]

Four years of university, and I never understood 2s complement. This answer has taught me more. It is so sad that such simple things are taught in such arcane ways throughout the world.

[KevinZhou]

The scheme you are using here is already 2's complement. Isn't is?