Radices

The following are notes on radices.

Numerals

Recall that the division theorem provides the following:

division theorem. Let ${n,d \in \uint}$ with ${d \gt 0.}$ Then there exist unique integers ${q}$ and ${r}$ such that ${n = dq + r}$ with ${0 \le r \lt d.}$

theorem. Let ${b}$ be an integer greater than 1. Any ${n \in \pint}$ can be expressed uniquely in the form

n = a_kb^k + a_{k-1}b^{k-1} + \ldots + a_1b + a_\nil,

where ${k \in \nat}$ and ${a_0, a_1, \ldots, a_k}$ are natural numbers less than ${b}$ and ${a_k \neq 0.}$

example. ${(1101)_2 = 1(2^3) + 1(2^2) + 0(2^1) + 1(2^0) = 8 + 4 + 0 + 1 = 13.}$

In the example above, the base is 2. We say that 2 is the radix of the binary system.

Base Conversion Algorithm

Below is an algorithm for converting to different bases.

base-conversion

Input:
- ${n \in \uint}$ , the number to convert.
- ${b \gt 1}$ , the base.
Output: ${A,}$ an array of bases.

${\let{q}{n}}$
${\let{i}{0}}$
${\let{A}{\ix{~}}}$
while ${q \neq 0}$ do
1. ${\let{a_i}{q} \rem b}$
2. ${A \Lleftarrow a_i}$
3. ${\let{q}{q} \dv b}$
4. ${k \inc}$
return ${A}$

The algorithm above gives us a quick way to convert numbers to binary in our heads. For example, suppose we're given a decimal ${d.}$ To convert to binary ${d_2,}$ we start by writing ${1}$ if ${d}$ is odd, and ${0}$ if ${d}$ is even. Then, compute the integer division of ${d.}$ That is, ${\floor{d/2}.}$ If the result is even, write ${0.}$ If the result is odd, write ${1.}$ We continue this process until we get to ${1.}$ For example, consider converting the integer ${37:}$

${d}$	remainder
${37}$	${1}$
${\floor{37/2}=18}$	${0}$
${\floor{18/2}=9}$	${1}$
${\floor{9/2}=4}$	${0}$
${\floor{4/2}=2}$	${0}$
${\floor{2/2}=1}$	${1}$

Mentally, we might list: ${101001.}$ Simply reverse this sequence (binary digits are read from right to left): ${100101.}$ There's nothing magical here. All we're doing is computing the remainder, but in a cognitively easier way (for most people, determining if a number is odd or even is faster than thinking about remainders). The same goes for converting numbers in other bases. Simply determine if the integer quotient at each step is a multiple of the base.

Binary Arithmetic

It's helpful to know the basic powers of two for this section:

power	decimal
${2^0}$	1
${2^1}$	2
${2^2}$	4
${2^3}$	8
${2^4}$	16
${2^5}$	32
${2^6}$	64
${2^7}$	64
${2^8}$	128
${2^9}$	512
${2^{10}}$	1024
${2^{11}}$	2048
${2^{12}}$	4096

Below are the definitions of bitwise operations.

bitwise operations. Let ${(n)_2 = (a_{n-1},a_{n-1},\ldots,a_2,a_1,a_0)}$ and ${(m)_2 = (b_{n-1},b_{n-1},\ldots,b_2,b_1,b_0)}$ be binary integers, such that each ${a_i}$ and ${b_i}$ is a bit (1 or 0 but not both), for all ${0 \le i \le n,}$ where ${i,n \in \nat.}$ The following definitions apply for each bit ${a}$ and ${b.}$

\eqs{ \bnot a &= 1 - a \equiv \df{not}~ a \\ a \bor b &= \max{(a,b)} \equiv a ~\df{or} ~ a \\ a \band b &= \min{(a,b)} \equiv a ~\df{and} ~ b \\ a \bxor b &= \abs{a-b} \equiv a ~\df{xor} ~ b \\ }

Given ${A, B \in 2^{\nat},}$ the operations are defined as follows:

\eqs{ \bnot a &= 1 - a \equiv \df{not}~ a \\ a \bor b &= \max{(a,b)} \equiv a ~\df{or} ~ a \\ a \band b &= \min{(a,b)} \equiv a ~\df{and} ~ b \\ a \bxor b &= \abs{a-b} \equiv a ~\df{xor} ~ b \\ }

The bitwise operators apply to bits (base expansions) of integers, not the integers themselves.

Binary Set Union

The ${A \bor B}$ operation is equivalent to ${A \cup_{2} B}$ (the binary union of ${A}$ and ${B}$ ).

Binary Intersection

The ${A \band B}$ operation is equivalent to ${A \cap_{2} B}$ (the binary intersection of ${A}$ and ${B}$ ).

Binary Set Minus

Given two binary sets ${A}$ and ${B,}$ the binary set minus ( ${A \rid_{2} B}$ ) is expressed as ${A \band (\bnot B).}$

Binary Remainder

Given binary variables ${a}$ and ${n,}$ the binary remainder of ${a}$ and ${n}$ can be computed as follows:

a \rem n \equiv a \band (n-1).

example. ${6 \band (2-1)=6 \rem 2=0.}$

example. ${7 \band (2-1) = 7 \rem 2=1.}$

At Least One is False

The expression below returns true if at least one of ${a}$ and ${b}$ is 0. Note the different symbols, these are logical operators, not bitwise. The phrase "at least one of" can always be translated in terms of "nand."

\neg(a \land b).

Must Both Be False

Given two binary variables ${a}$ and ${b,}$ the expression below returns true if both ${a}$ and ${b}$ are false.

[(a \bor b)=0].

At Least One is False

Given two variables ${a}$ and ${b,}$ the expression below returns true if exactly one of the values is false.

[(\neg a) \bxor (\neg b)].