Number systems formulas

Here $n$ is the number of integer digits $d_{n-1}\dots d_0$ and $m$ the number of fraction digits $d_{-1}\dots d_{-m}$. Every digit must be smaller than the base.

An $n$-digit base-$r$ integer takes $r^n$ distinct values. In bits, $n_{\min }=\lceil {\log }_2(N+1)\rceil$. For example, 256 needs 9 bits because $2^8-1=255$. The formula needs $N\ge 1$; the value 0 still takes one digit.

$N$ is an $n$-digit base-$r$ integer (leading 0s count towards $n$). The $(r-1)$'s complement replaces every digit $d$ by $(r-1)-d$; adding 1 to it gives the $r$'s complement. For $N=0$ the $r$'s complement $r^n$ has $n+1$ digits; dropping the extra digit leaves 0. If $N$ also has $m$ fraction digits, its $(r-1)$'s complement is $r^n-r^{-m}-N$. Examples: the 9's and 10's complements of $3250$ are $6749$ and $6750$; the 7's and 8's complements of $(325{)}_8$ are $(452{)}_8$ and $(453{)}_8$. With $r=2$ these are the 1's and 2's complements.

The MSB has weight $-2^{n-1}$. Equivalently, when the MSB is 1, value $=$ (unsigned value) $-2^n$. For example, $10110011_2=179-256=-77$.

For $n=8$: unsigned is 0 to 255, 2's complement is $-128$ to $+127$, and the other two are $-127$ to $+127$ (each has two codes for zero).

$N$ and the results are read as $n$-bit unsigned values, and the carry out of bit $n-1$ is dropped (the arithmetic is modulo $2^n$). So in 2's complement, negating $0$ gives $0$ back; in 1's complement it gives $11\dots 1$, the second code for zero. In 2's complement, negating $-2^{n-1}$ gives $-2^{n-1}$ back (an overflow), because $+2^{n-1}$ has no $n$-bit code.

Overflow occurs exactly when the carry into the MSB differs from the carry out of it. This holds for addition and for $A+\overline{B}+1$ alike.

$a_{n-1}$ and $b_{n-1}$ are the sign bits of the two words entering the adder, and $s_{n-1}$ is the sign bit of the sum. In words: two operands of the same sign produced a sum of the other sign. Adding operands of opposite signs can never overflow. For $A-B$, use the sign bit of $\overline{B}$, the word the adder actually receives.

When $A-B$ is computed as $A+\overline{B}+1$, $C_n=1$ means $A\ge B$ (no borrow) and $C_n=0$ means $A<B$.

Equivalently, $G=B\oplus (B\gg 1)$, where $B\gg 1$ is $B$ shifted right by one bit with a 0 entering at the MSB. It takes $n-1$ XOR gates and involves no carries. Example: $B=10110110$ gives $G=10110110\oplus 01011011=11101101$.

Work from the MSB down. Each binary bit is the XOR of the Gray bit at that position with the binary bit just found on its left. Equivalently, $b_i$ is the parity of all Gray bits from the MSB down to position $i$.

$(1.F{)}_2=1+{\sum }_{i=1}^{23}{f}_i{2}^{-i}$, where $f_1$ is the fraction MSB. The true exponent runs from $-126$ to $+127$.

There is no hidden 1, and the exponent is fixed at $-126$, not $0-127=-127$. Denormals fill the gap between 0 and the smallest normalized number in equal steps of $2^{-149}$.

$x_{\max }$ has $E=254$ and $F$ all 1s (hex 7F7FFFFF). $x_{\min ,\text{norm}}$ has $E=1$, $F=0$ (hex 00800000). $x_{\min ,\text{denorm}}$ has $E=0$ and $F=0\dots 01$ (hex 00000001). The negative values mirror these with $S=1$.

The gap doubles with each power of 2. Absolute resolution therefore worsens as magnitude grows, while the relative gap between neighbours stays between $2^{-24}$ and $2^{-23}\approx 1.19\times 10^{-7}$. Below $2^{-126}$ the denormals take over, with the fixed gap $2^{-149}$.

$k$ is the number of exponent bits: $k=8$ gives 127 and $k=11$ gives 1023. Double precision has 1 sign bit, 11 exponent bits and 52 fraction bits, and its denormals use $2^{-1022}$. A question that defines its own format, with a stated bias or a different significand convention (for example $0.1F$ with no hidden bit), overrides these values.

To check, XOR all $m+1$ received bits; with even parity, a result of 1 flags an error. An XOR tree with $m$ inputs needs $m-1$ two-input XOR gates.

$d_{\min }$ is the smallest number of bit positions in which any two valid code words differ. To correct up to $t$ errors and also detect up to $s$ errors ($s\ge t$), $d_{\min }\ge t+s+1$. Single parity has $d_{\min }=2$, so it detects 1 error and corrects none.

$m$ is the number of data bits and $p$ the number of check bits, and you take the smallest $p$ that satisfies the inequality. $m=4$ needs $p=3$ (the (7,4) code) and $m=8$ needs $p=4$. $m=16$ needs $p=5$, not 4, because $2^4=16<21$. In the usual layout the check bits sit at positions 1, 2, 4, 8, … (numbered from 1), and the recomputed checks (the syndrome), read as a binary number, give the position of a single flipped bit, with 0 meaning no error. The Hamming code has $d_{\min }=3$; adding one overall parity bit raises it to 4, so the extended code corrects 1 error and detects 2.