Integer Encoding (数字编码)

Abstract

---

• Integer encoding is the process of representing decimal integers in the form of zeros and ones, supporting both positive and negative integer
• There are 3 integer encoding variants; Sign-and-Magnitude (原码), 1’s Complement (反码) and 2’s Complement (补码), computer uses the 2’s Complement to store integer, because it solves the flaws of Sign-and-Magnitude (原码) and 1’s Complement (反码)
• Below is a 4-bits integer encoding under the 3 variants

Decimal	Signed Magnitude	One’s Complement	Two’s Complement
$+7$	$0111$	$0111$	$0111$
$+6$	$0110$	$0110$	$0110$
$+5$	$0101$	$0101$	$0101$
$+4$	$0100$	$0100$	$0100$
$+3$	$0011$	$0011$	$0011$
$+2$	$0010$	$0010$	$0010$
$+1$	$0001$	$0001$	$0001$
$+0$	$0000$	$0000$	$0000$
$-0$	$1000$	$1111$	$0000$
$-1$	$1001$	$1110$	$1111$
$-2$	$1010$	$1101$	$1110$
$-3$	$1011$	$1100$	$1101$
$-4$	$1100$	$1011$	$1100$
$-5$	$1101$	$1010$	$1011$
$-6$	$1110$	$1001$	$1010$
$-7$	$1111$	$1000$	$1001$
$-8$	-	-	$1000$

Important

For the three integer encoding variants, the encodings for positive integer are exactly the same.

Sign Bit

• $0$ denotes positive
• $1$ denotes negative
• Usually the first bit from left, the most significant bit (MSB)

Magnitude Bit

• Represent the magnitude (absolute value) of the integer in standard binary representation

Sign-and-Magnitude (原码)

---

Positive Decimal	Signed Magnitude	Negative Decimal	Signed Magnitude
$+0$	$0000$	$-0$	$1000$
$+1$	$0001$	$-1$	$1001$
$+2$	$0010$	$-2$	$1010$
$+3$	$0011$	$-3$	$1011$
$+4$	$0100$	$-4$	$1100$
$+5$	$0101$	$-5$	$1101$
$+6$	$0110$	$-6$	$1110$
$+7$	$0111$	$-7$	$1111$

• Sign-and-magnitude is a method for representing both positive and negative integers using a Sign Bit and magnitude bits. The most significant bit (MSB) is reserved as the sign bit

Unable to performance subtraction with Adder

The Adder is unable to perform subtraction on sign-and-magnitude encoded integers, an explicit set of Logic Gates for substation is needed. This can be avoided using 1’s Complement (反码) or 2’s Complement (补码).

1’s Complement (反码)

---

Decimal	Signed Magnitude	One’s Complement
$+0$	$0000$	$0000$
$-0$	$1000$	$1111$
$-1$	$1001$	$1110$
$-2$	$1010$	$1101$
$-3$	$1011$	$1100$
$-4$	$1100$	$1011$
$-5$	$1101$	$1010$
$-6$	$1110$	$1001$
$-7$	$1111$	$1000$

• Basically same as the Sign-and-Magnitude (原码), but for negative decimal integers, all magnitude bits are inverted

Reuse adder for subtraction

We can reuse Adder Logic Gates to perform subtraction without the need for dedicated subtraction logic gates.

Mathematically wrong definition of 0

We have +0 (when all bits are 0) & -0(when all bits are 1) under this encoding, this can be solved with 2’s Complement (补码).

2’s Complement (补码)

---

Decimal	One’s Complement	Two’s Complement
$+0$	$0000$	$0000$
$-0$	$1111$	$0000$
$-1$	$1110$	$1111$
$-2$	$1101$	$1110$
$-3$	$1100$	$1101$
$-4$	$1011$	$1100$
$-5$	$1010$	$1011$
$-6$	$1001$	$1010$
$-7$	$1000$	$1001$
$-8$	-	$1000$

• This builds on top of 1’s Complement (反码), the only difference being to add $1$ to the 1’s complement (反码) integer encoding for negative numbers

Mathematically correct definition of Zero

The integer encoding for both $+0$ and $-0$ is $0000$, thus eliminating two different integer encodings for $0$.

Trick to convert from 2's complement to decimal value

The decimal value = the negative decimal value of Sign Bit + the positive sum of the magnitude bits.

Integer Overflow

---

• When a value is out of the range that the Datatype can hold

Check for Integer Overflow

If the Sign Bit of the two operand is the same, and the sign bit of the result is different. Then we have an Integer (整数) overflow.

How can the sum of two positive integer result in a negative number, and how the sum of two negative integer result in a positive number?

The sum of a negative and positive integer guaranteed no integer overflow.

Reference

---

• Sign-and-Magnitude Addition and Subtraction
• Hello-Algo