Encoding signed integers as binary

• Signed integers are generally encoded in two’s complement.
  • The most significant bit (MSB) is interpreted as having a negative weight

Two’s complement encoding

Formula

For a vector $\vec{x}=\left[x_{w-1},x_{w-2},\dots ,x_0\right]$, the corresponding integer can be calculated using the following formula (where $B2T_w$ means binary to two’s complement, length $w$ bits)

$$B2T_w(\vec{x})\doteq -x_{w-1}{2}^{w-1}+\sum _{i=0}^{w-2}{x}_i{2}^i$$

About the most significant bit (MSB)

• The MSB $x_{w-1}$ is called the sign bit
• Its weight is $-2^{w-1}$ - the negation of its weight in unsigned representation
• When it is set to $1$, the represented integral value is negative. When it is set to $0$, the represented integral value is non-negative.

Examples

$$B2T_4([1011])=-1\cdot 2^3+0\cdot 2^2+1\cdot 2^1+1\cdot 2^0=-8+0+2+1=-5$$

Visual example

Range of values

• Consider a $w$-bit two’s complement number
• The least representable value is given be vector $[100\cdots 0]$, having integer value $TMi{n}_w\doteq -2^{w-1}$
• The largest value is given by the vector $[011\cdots 1]$, which has the integer value of: $TMa{x}_w\doteq {\sum }_{i=0}^{w-2}{2}^i=2^{w-1}-1$

Example

• When $w=4$

$$\begin{array}{rl}TMi{n}_4& =-2^{4-1}=-2^3=-8\\ TMa{x}_4& =2^{4-1}-1=8-1=7\end{array}$$

Sources

• Computer Systems - A Programmer’s Perspective

Related Notes