4
$\begingroup$

Can someone explain in plain English what "two's complement integer" means? I read this:

in Java long is a 64-bit signed two's complement integer

$\endgroup$

migrated from cstheory.stackexchange.com Apr 1 '13 at 16:44

This question came from our site for theoretical computer scientists and researchers in related fields.

5
$\begingroup$

Two's complement is the most commonly used way to represent signed integers in bits. First, consider unsigned numbers in 8 bits. Notice that $2^8 = 256 = 100000000_2$ does not fit into 8 bits and will thus be represented as 0000 0000. Therefore $255 + 1 =$ 1111 1111 + 0000 0001 = 0000 0000 and in that sense 1111 1111 acts as if it was $-1$. Two's complement is based on this observation.

For a deeper understanding of it, I suggest reading the wikipedia page on it. Note that as long as you you don't need to directly manipulate bits of your integers and your numbers don't go out of range, it makes no difference what signed integer representation is used.

$\endgroup$
0
$\begingroup$

Karolis Juodele's answer is good. Here's another take.

To represent a negative number over $k$ bits in two's complement:

  1. Take the complement of the absolute value of the number over $k$ bits, by changing $0$ to $1$ and vice-versa.
  2. Add 1 to the number obtained previously, using regular unsigned integer arithmetic.

Example: find the two's complement representation of $-55$ assuming an 8-bit representation. The binary representation of $|-55| = 55$ is $00110111$. The complement of this is $11001000$. Adding $1$ using unsigned integer arithmetic yields $1101001$. This is the two's complement representation of $-55$ over 8-bit integers. Note that, as Karolis points out, performing binary addition using unsigned integer arithmetic of these two representations (the representations for $55$ and $-55$) yields $00000000$, or $0$.

$\endgroup$
0
$\begingroup$

The two's complement of a number $N$ is the amount that you need to add to $N$ to get $2^k$ where $k$ is the number of binary digits needed to represent $N$; analogously three's complement would be the amount to add to get $3^k$ ($k$ is the number of ternary digits now) and you get the pattern. So this complement idea can be generalized to any base not only $2$. In other words, the complement is the amount that you need to add to get the WHOLE where the WHOLE is some predetermined quantity (thinking of complements of sets might help).

Let's say numbers are stored in $8$ bits so the maximum number in this representation is $2^8 - 1$ and $2^8$ is equivalent to $0$ because it can't fit in the $8$ bits representation (it overflows). The complement of the maximum is $1$ since $1 + (2^8 - 1) = 2^8$. This suggests that a legitimate representation of a negative number $-M$ is $(2^8-M)$ because adding $M$ results in $2^8$ which is the same as $0$ and this is what we expect it to be.

The way computers do it is a bit different. Let's take the number $X=1$; in our representation this is written as: $X=00000001$. Now the amount that we need to add to $X$ to get the WHOLE is $11111110$ which turns all bits on and then add $1$ to cause an overflow so that the result is $100000000$ which is the same as $2^8$, so computers first flip all the bits ($0$ becomes $1$ and vice-versa) and then add $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy