Binary Number

Complement

In computers, the representation and manipulation of negative numbers is often performed using complements.

Why is two's complement used on hardware?

Because we can eliminate the need to have separate circuitry (ALUs) for both signed and unsigned numbers.

• Good motivation from this article

Resources

• https://en.wikipedia.org/wiki/Signed_number_representations

Two’s Complement form

-a == ~a + 1

This is the unanimous choice to represent numbers in Binary.

The 2’s complement form is a very popular convention that maps sequences of $n$ bits to integers in the range from $-2^{n-1}$ to $2^{n-1}-1$.

Ex: In two’s complement, the bit sequence $1000011$ represents the number $1(-2^6)+0(2^5)+0(2^4)+0(2^3)+0(2^2)+1(2^1)+1(2^0)=-61$

Abstract

The property that makes two’s complement convenient is that if any sequence S of $n$ bits is interpreted both as a binary number $b$ and as a two’s complement number $t$, then $b\equiv t(\mathrm{mod}{2}^n)$.

From CS241E, to find the 2’s complement encoding of a small negative number, take the positive unsigned number, invert its bits, and add 1 to the result binary number. Ex:

• $00000000000000000000000000000001\to 1$ (unsigned)
• Flipping all the bits: $11111111111111111111111111111110$
• Add 1: $11111111111111111111111111111111\to -1$

We can also do the same in to go from signed negative to unsigned positive numbers. Ex: what does: $1001111111111111111111111111111$ represent?

• You flip the bits, add 1, so you get $0110000000000000000001$, and that is the positive version of the number.

Why are you just able to flip the bits and add 1 to get an equivalent number?

Like that feels like black magic to me. Damn I spent an hour trying to prove this to myself. See below. All because this article claimed that signed magnitude would not work, but two’s complement would.

• OMG SERENDIPITY, because Floating Point actually uses sign-magnitude!!

It’s actually really simple. You simply need to realize that we have the following property (for 32-bit representation):

$\overline{x}=(2^{32}-1)-x$

• $2^{32}-1$ is just a mask of all 1s, i.e. 0b11111111…111

Therefore, we can extract $-x$ $-x=\overline{x}-2^{32}+1$

• We are already implicitly doing -2^32, because that exponent representation has gone from 2^31 to -2^31, so it’s a subtraction by $2^{3}2$.

Why is signed and unsigned addition equivalent?

Because you are just adding bits and carrying over. In both cases, overflow results undefined values.

Given the bits $b_{n-1}{b}_{n-2}...b_1{b}_0$ the same, this is how you read it:

(and essentially that’s converting from negative to positive)

Other thought experiment

Consider 61 in unsigned form, i.e. $61=0b111101=1(2^5)+1(2^4)+1(2^3)+1(2^2)+0(2^1)+1(2^0)$ Let’s try represented -61, the most intuitive way is to use the signed magnitude represented: $-61=-0b111101=-1(2^5)-1(2^4)-1(2^3)-1(2^2)-0(2^1)-1(2^0)$ Would that work?

Another way we can try representing -61, is by doing $2^{32}-61=0b11111111111111111111111111000011=0b111101+1$

• And then read the MSB as $-2^{31}$

Used to get the negative of a signed binary number. → This is what is widely used nowadays To negate a value:

1. Take the complement of all bits
2. Add 1

Other way to think about it from CS241E:

• Take the biggest bit, and make that negative. The idea is to represent $-x$ the same as $2^n-x$

Another way is Subtraction by Addition, see Binary Number.

Also see the Sign Extension shortcut, which is super important for Sign Extension shortcut, which is super important for ECE222.

Sign Magnitude

This is essentially putting an indicator on the MSB, i.e. 0011 means +3, and 1011 is -3.

• https://semianalysis.com/2024/01/11/neural-network-quantization-and-number/

This is actually how we represent Floating Point!!

You can’t just add the bits. For example, consider 3 - 2, where:

  0011   (+3)
+ 1010   (-2)
------------
  1101   (Incorrect!)

You have to first compare the signs, handle different cases.

One’s Complement

-a == ~a

Used for unsigned numbers.

8’s Complement, 9’s Complement

Calculated by subtracting the number from 888888 / 999999

R’s Complement (Radix Complement)

9’s complement 1’s complement

The complement of a complement returns the original number

Signed magnitude → Left-most bit indicates sign

Conversion between number systems

Convert 53 to binary

Decimal to binary is very straightforward.