Two's Complement Representation: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(59 intermediate revisions by the same user not shown)
Line 1: Line 1:
=External=
=External=


* https://en.wikipedia.org/wiki/Two%27s_complement
* https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html
* https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html


Line 6: Line 7:


* [[Numeric Values Representation in Java]]
* [[Numeric Values Representation in Java]]
* [[Go Integers#Overview|Go Integers]]


=Overview=
=Overview=


Two's complement is the most common signed integer representation scheme on computers. The scheme widely used because a computer can use the same circuitry to perform addition, subtraction and multiplication, whereas otherwise they would have to be treated as separate operations. Also, two's complement has no representation for negative zero, and thus does it not suffer from associated difficulties.
Two's complement is the most common signed integer representation scheme on computers.  It is used to represent both positive and negative numbers, though in the case of a positive number, two's complement representation is identical to the default binary implementation of that number. The scheme is widely used because a computer can use the same circuitry to perform addition, subtraction and multiplication, whereas otherwise they would have to be treated as separate operations. The most significant bit represents the sign - 0 for positive integers, 1 for negative integers - and the rest of the bits are used to represent the value according to the formula shown below. Two's complement has no representation for negative zero, and thus does it not suffer from associated difficulties.


=Mathematical Foundation=
=Mathematical Foundation=
A two's complement encodes both positive and negative numbers in a binary number representation. Assuming that n bits are available to represent an integral value, the weight of each bit, except the most significant one, is the power of two corresponding to bit's position. The weight of the most significant bit is the negative of the corresponding power of two.
If n bits are available to store the value:
a<sub>n-1</sub> a<sub>n-2</sub> ... a<sub>2</sub> a<sub>1</sub> a<sub>0</sub>
the value is given by the following formula:
                <sub>n-2</sub>
v = -a<sub>n-1</sub>*2<sup>n-1</sup> + ∑ a<sub>i</sub>2<sup>i</sup>
                <sup>i=0</sup>
Positive integers have the most significant bit 0, and use the rest n-1 bits to represent the value. Their representation is a normal binary representation, where each bit carries a weight that is the power of two of the bit's position.
Negative integer have the most significant bit 1, and use the rest n-1 bits to represent value.


=Practical Implications=
=Practical Implications=


To quickly find the two's complement representation of a negative number, start with the binary representation of the corresponding positive number, invert all bit values and add 1 to the result.
From a practical perspective, representing a negative number in two's complement simplifies a subtraction hardware operation, by making possible to use the same circuitry that is used for addition: assuming we want to subtract 53 from 71, which is 71 - 53, we express it as 71 + (-53), we represent -53 in two's complement by inverting the digits and adding 1, and then adding those two values.
=Examples=
==byte Representation==
25 represented in two's complement on 8 bits (1 byte):  0001 1001, the value: 1*2<sup>4</sup> + 1*2<sup>3</sup> + 1*2<sup>0</sup> = 25
-25 represented in two's complement: swap all bits and add 1:  1110 0111, the value: -1*2<sup>7</sup> + 1*2<sup>6</sup> + 1*2<sup>5</sup> + 1*2<sup>2</sup> + 1*2<sup>1</sup> + 1 = -25.
The smallest negative number represented on a byte: 1000 0000 (-1 * 2<sup>7</sup> = -128).
-1: 1111 1110
Zero: 0000 0000
The largest positive number represented on a byte: 0111 1111 (2<sup>7</sup> - 1 = 127).
Also see: {{Internal|Java_Language#byte|<code>byte</code> in Java}}
==short Representation==
25 represented in two's complement on 16 bits (2 bytes):  0000 0000 0001 1001, the value: 1*2<sup>4</sup> + 1*2<sup>3</sup> + 1*2<sup>0</sup> = 25
-25 represented in two's complement: swap all bits and add 1:  1111 1111 1110 0111, the value: -1*2<sup>15</sup> + 1*2<sup>14</sup> + 1*2<sup>13</sup> + 1*2<sup>12</sup> + 1*2<sup>11</sup> + 1*2<sup>10</sup> + 1*2<sup>9</sup> + 1*2<sup>8</sup> +  1*2<sup>7</sup> + 1*2<sup>6</sup> + 1*2<sup>5</sup> +  1*2<sup>2</sup> + 1*2<sup>1</sup> + 1 = -25.
The smallest negative number represented on a byte: 1000 0000 0000 0000 (-1 * 2<sup>15</sup> = -32,768).
-1: 1111 1111 1111 1110
Zero: 0000 0000 0000 0000
The largest positive number represented on a byte: 0111 1111 1111 1111 (2<sup>15</sup> - 1 = 32,767).
Also see: {{Internal|Java_Language#short|<code>short</code> in Java}}
==int Representation==
25 represented in two's complement on 32 bits (4 bytes):  0000 0000 0000 0000 0000 0000 0001 1001, the value: 1*2<sup>4</sup> + 1*2<sup>3</sup> + 1*2<sup>0</sup> = 25
-25 represented in two's complement: swap all bits and add 1:  1111 1111 1111 1111 1111 1111 1110 0111, the value: -1*2<sup>31</sup> + 1*2<sup>30</sup> + ... +  1*2<sup>7</sup> + 1*2<sup>6</sup> + 1*2<sup>5</sup> +  1*2<sup>2</sup> + 1*2<sup>1</sup> + 1 = -25.
The smallest negative number represented on a byte: 1000 0000 0000 0000 0000 0000 0000 0000 (-1 * 2<sup>31</sup> = -2,147,483,648).
-1: 1111 1111 1111 1111 1111 1111 1111 1110
Zero: 0000 0000 0000 0000 0000 0000 0000 0000
The largest positive number represented on a byte: 0111 1111 1111 1111 1111 1111 1111 1111 (2<sup>31</sup> - 1 = 2,147,483,647).
Also see: {{Internal|Java_Language#int|<code>int</code> in Java}}


==long Representation==


==Subtraction==
25 represented in two's complement on 64 bits (8 bytes):  0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1001, the value: 1*2<sup>4</sup> + 1*2<sup>3</sup> + 1*2<sup>0</sup> = 25


-25 represented in two's complement: swap all bits and add 1: 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1110 0111, the value: -1*2<sup>63</sup> + 1*2<sup>62</sup> + ... +  1*2<sup>7</sup> + 1*2<sup>6</sup> + 1*2<sup>5</sup> +  1*2<sup>2</sup> + 1*2<sup>1</sup> + 1 = -25.


The smallest negative number represented on a byte: 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 (-1 * 2<sup>63</sup> = -9,223,372,036,854,775,808).


used by most computers to represent signed integral values such as byte, int or long.
-1: 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1110


Positive numbers
Zero: 0000 0000 0000 0000 0000 0000 0000 0000  0000 0000 0000 0000 0000 0000 0000 0000


Negative numbers
The largest positive number represented on a byte: 0111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 (2<sup>63</sup> - 1 = 9,223,372,036,854,775,807).


The primary motivation between this scheme is that
Also see: {{Internal|Java_Language#long|<code>long</code> in Java}}

Latest revision as of 01:08, 19 August 2023

External

Internal

Overview

Two's complement is the most common signed integer representation scheme on computers. It is used to represent both positive and negative numbers, though in the case of a positive number, two's complement representation is identical to the default binary implementation of that number. The scheme is widely used because a computer can use the same circuitry to perform addition, subtraction and multiplication, whereas otherwise they would have to be treated as separate operations. The most significant bit represents the sign - 0 for positive integers, 1 for negative integers - and the rest of the bits are used to represent the value according to the formula shown below. Two's complement has no representation for negative zero, and thus does it not suffer from associated difficulties.

Mathematical Foundation

A two's complement encodes both positive and negative numbers in a binary number representation. Assuming that n bits are available to represent an integral value, the weight of each bit, except the most significant one, is the power of two corresponding to bit's position. The weight of the most significant bit is the negative of the corresponding power of two.

If n bits are available to store the value:

an-1 an-2 ... a2 a1 a0

the value is given by the following formula:

                n-2
v = -an-1*2n-1 + ∑ ai2i
                i=0

Positive integers have the most significant bit 0, and use the rest n-1 bits to represent the value. Their representation is a normal binary representation, where each bit carries a weight that is the power of two of the bit's position.

Negative integer have the most significant bit 1, and use the rest n-1 bits to represent value.

Practical Implications

To quickly find the two's complement representation of a negative number, start with the binary representation of the corresponding positive number, invert all bit values and add 1 to the result.

From a practical perspective, representing a negative number in two's complement simplifies a subtraction hardware operation, by making possible to use the same circuitry that is used for addition: assuming we want to subtract 53 from 71, which is 71 - 53, we express it as 71 + (-53), we represent -53 in two's complement by inverting the digits and adding 1, and then adding those two values.

Examples

byte Representation

25 represented in two's complement on 8 bits (1 byte): 0001 1001, the value: 1*24 + 1*23 + 1*20 = 25

-25 represented in two's complement: swap all bits and add 1: 1110 0111, the value: -1*27 + 1*26 + 1*25 + 1*22 + 1*21 + 1 = -25.

The smallest negative number represented on a byte: 1000 0000 (-1 * 27 = -128).

-1: 1111 1110

Zero: 0000 0000

The largest positive number represented on a byte: 0111 1111 (27 - 1 = 127).

Also see:

byte in Java

short Representation

25 represented in two's complement on 16 bits (2 bytes): 0000 0000 0001 1001, the value: 1*24 + 1*23 + 1*20 = 25

-25 represented in two's complement: swap all bits and add 1: 1111 1111 1110 0111, the value: -1*215 + 1*214 + 1*213 + 1*212 + 1*211 + 1*210 + 1*29 + 1*28 + 1*27 + 1*26 + 1*25 + 1*22 + 1*21 + 1 = -25.

The smallest negative number represented on a byte: 1000 0000 0000 0000 (-1 * 215 = -32,768).

-1: 1111 1111 1111 1110

Zero: 0000 0000 0000 0000

The largest positive number represented on a byte: 0111 1111 1111 1111 (215 - 1 = 32,767).

Also see:

short in Java

int Representation

25 represented in two's complement on 32 bits (4 bytes): 0000 0000 0000 0000 0000 0000 0001 1001, the value: 1*24 + 1*23 + 1*20 = 25

-25 represented in two's complement: swap all bits and add 1: 1111 1111 1111 1111 1111 1111 1110 0111, the value: -1*231 + 1*230 + ... + 1*27 + 1*26 + 1*25 + 1*22 + 1*21 + 1 = -25.

The smallest negative number represented on a byte: 1000 0000 0000 0000 0000 0000 0000 0000 (-1 * 231 = -2,147,483,648).

-1: 1111 1111 1111 1111 1111 1111 1111 1110

Zero: 0000 0000 0000 0000 0000 0000 0000 0000

The largest positive number represented on a byte: 0111 1111 1111 1111 1111 1111 1111 1111 (231 - 1 = 2,147,483,647).

Also see:

int in Java

long Representation

25 represented in two's complement on 64 bits (8 bytes): 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 1001, the value: 1*24 + 1*23 + 1*20 = 25

-25 represented in two's complement: swap all bits and add 1: 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1110 0111, the value: -1*263 + 1*262 + ... + 1*27 + 1*26 + 1*25 + 1*22 + 1*21 + 1 = -25.

The smallest negative number represented on a byte: 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 (-1 * 263 = -9,223,372,036,854,775,808).

-1: 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1110

Zero: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

The largest positive number represented on a byte: 0111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 (263 - 1 = 9,223,372,036,854,775,807).

Also see:

long in Java