Binary Representation

Why Bits?

Bits are used because they're the easiest way to deal with the noise and uncertainty of electrical pulses running through wires. If we examined the pulses with an oscilloscope, we'd see graphs that aren't true step functions like we'd see in a mathematics textbook. Instead, they're graphs that appear to resemble step functions.

Word Size

Every computer has a word size. In terms of hardware, the word size is the width of a single register on the machine. The width of a register is the number of binary cells the register contains. For example, a machine with a word size of 8 bits consists of registers with 8 binary cells. On a machine with a word size of 64 bits, a single register ctonains 64 binary cells.

In terms of software, the word size is the nominal size of pointer data (a memory address). Put differently, the word size is the maximum number of bits the computer's CPU can process at a single point in time. This is in line with the hardware perspective — if the most a register can take is ${w}$ bits, then the CPU can only work with ${w}$ at a time.

Thus, If we have a 4-bit machine, each register has 4 binary cells, each of which can be either 1 or 0. As such, the number of possible bit sequences for 4 binary cells ranges from 0 to ${2^4 - 1 = 15,}$ or 16 possible sequences. This leaves 16 possible memory addresses.

Word-oriented Memory Organization

If we have ${n}$ possible numbers for addresses, the next question is how we want to use those numbers to address memory locations — the process of byte ordering. There are predominant two approaches too byte ordering:

1. Big Endian (used by SPARC, PPC Mac, and the Internet), and
2. Little Endian (used by the x86, ARM processesors for Android, iOS, Linux, as well as most modern operating systems like Windows and OSX)

With the Big Endian approach, the least significant byte has the highest address. With the Little Endian approach, the least signfiicant byte has the lowest address. Simply put, with Big Endian, the bits are ordered from left to right:

And with Little Endian, the bits are ordered from right to left:

Most of devices we use daily employ Little Endian ordering. The one exception is the Internet. This is because the Network Working Group (the organization responsible for implementing the Internet in its early years) decided to use Big Endian.^[note_big_endian] It's not entirely clear why they made that decision, but it's what we have today.

Warning on Twos Complement

As a warning, we should never assume that a machine uses twos-complement representation. While there aren't very many ones-complement machines today, when working with low-level systems, we should check to know for certain that the relevant platform uses twos-complement. There are several ways to do so.

The simplest way is to check if:

If -1 and ${\bnot 0}$ are equal, then the machine uses twos-complement representation. Why? Because -1 on a twos-complement machine is always a bit vector of entirely ones. If they aren't equal, then we're using either ones-complement hardware or, albeit very rare, a sign-magnitude machine.

Numeric Ranges

From the discussion of twos-complement, we can see that on a machine with a word size ${w}$ we have the following conclusions (where ${U}$ is an unsigned number and ${T}$ is a signed number in twos-complement):

For example, for a machine with a word size of 16, we have:

Notice that with twos-complement, we can represent more negative numbers than we can positive numbers. Why? Because we have to set aside space for 0.

In C, a short is 2 bytes long.

Relationship Between Signed and Unsigned Values

Following twos complement, we see that following relationship between unsigned and signed numeric values. Suppose the table below is drawn from a machine with a word size of 4.

Notice that for nonnegative numbers, both signed and unsigned numbers have the same encodings. However, once we hit the most significant bit, the encodings change: For the signed numbers, we add ${-2^{w},}$

This means that we can jump to and from unsigned to signed numbers with the following:

lemma. Given a machine with a word size ${w,}$ and a negative number ${n}$ on the machine,

$$|n| = n + 2^w$$

This lemma leads to some strange real-world behaviors. Negative numbers can become extremely large positive numbers, and large positive numbers can become negative. Because of this, languages like Java do not provide an unsigned data type — if a programmer uses a number that's too large, Java throws a compile-time error Integer number too large.

Overflow Bits in Addition

When an overflow results from twos-complement addition, we have two possibilities:

1. The result is within the twos-complement representable range,
2. The result is too big (a positive overflow) — resulting in a negative number.
3. The result is too small (a negative overflow) — resulting in a positive number.

Mathematically:

In languages like C, no overflow occurs for unsigned addition. The catch, of course, is that we get unsigned integer wrapping.

Overflow Bits in Multiplication

For multiplication, we have a messier situation. When we multiply an ${n}$ bit number by an ${m}$ bit number, we need ${n + m}$ bits for the product. If we have two ${w}$ bit numbers ${x}$ and ${y}$, the product ${x \cdot y}$ requires twice as many bits. Thus, the product of two unsigned ${w}$ bit numbers can require either ${0}$ or ${2w}$ bits.

For 2s-complement multiplication (signed multiplication), we have two cases. If one of the operands is ${\text{MIN}}$, then we may need up to ${2w-1}$ bits. If one of the operands is ${\text{MAX},}$ we may need up to ${2w}$ bits.

Again, we can't keep adding bits. As such, like addition, there are two approaches for handling overflows in multiplication:

1. For unsigned multiplication:
   1. Ignore the overflow bits (truncation), or
   2. Implement modular arithmetic (${u \cdot v = u \cdot v \bmod 2^w}$).
2. For signed multiplication:
   1. Ignore the overflow bits, or
   2. Compute the product (resulting in a bit sequence of length ${n+m}$), and then truncate the result.

Loops & Overflow Bits

One area where overflow bits are potentially dangerous is the use of iteration. A common iterative construct in many languages is the for-loop, and in many situations, we often want to count down:

int i;
for (i = start; i >= 0; i--) {
	// code
}

The problem with this approach is that int can be signed or unsigned. Considering how common fenceposts are, unless the programmer truly knows the data they're working with the loop above is risky. Because of this, some programmers employ the following:

unsigned i;
for (i = start; i >= 0; i--) {
	// code
}

While this declares that i is a positive value, it does not guarantee it. Because unsigned arithmetic on any machine employs unsigned wrapping, we can imagine a scenario where the loop counter i wraps.

We can prevent this is by using the following:

size_t start;
for (i = start-2; i < start; i--) {
	// code
}

This ensures that we don't wrap. Of course, it also assumes that start is not less than 0.

Floating Point Numbers

For the rational number 3.145, we know that the 1's place is the 1/10ths place, the 4 the 1/100ths, the 5 the 1/100ths, and so on. The same idea applies to binary numbers. For the rational binary number 1011.101, the first 1 to the right of the point corresponds 1/2, the 0 to 1/4, and the next 1 1/8. Thus, the number 1011.101 corresponds to:

There are several limitations with this encoding scheme. First, we can only represent numbers of the form ${\dfrac{n}{2^k}.}$ This means that we get binary representations like:

Second, the binary point is fixed — the point doesn't actually move; the bits go around it. This means that there are only so many values we can represent.

Because of these limitations, hardware designers came up with all sorts of ways to mitigate. In response to the increasingly chaotic market, the Institute of Electrical and Electronics Engineers (IEEE), a professional association of electrical and computer engineers, established a uniform standard for floating point arithmetic. In particular, the standard clarified how rounding, overflows, and underflows of floating points should be handled — the three most idiosyncratic areas at the time.

Today, the standard is supported by all major CPUs, and those that do not are generally regarded as black market CPUs. That said, the IEEE standard is a remarkably difficult standard to comply with at the hardware level. Much of the standard was defined by numerical analysts — mathematicians — rather than hardware engineers. The IEEE standard, however, is precisely what makes working with floating point numbers today user-friendly (at least compared to what it was like before the standard).

For computers, the numerical form of a floating point number is the following:

where ${s}$ is the sign bit. ${M}$ is the significand or mantissa. This is the number of significant digits, usually some fractional value in the range ${[1.0, 2.0).}$ The bits that encode ${M}$ are called f-bits (fractional bits). And ${E}$ is the exponent, which weights the value by a power of two. The bits that encode ${E}$ are called the e-bits (exponent bits).

For example, the number ${15213,}$ as a float, can be represented as:

Here, ${s = 0}$ because ${15213}$ is positive. ${M}$ is the bit sequence of ${13}$ bits following the decimal point. Then we have ${E = 2^{13}.}$

Visualizing with bits, this looks like:

Above, we've appended asterisks to each of the locations to indicate that these are encodings of the numbers comprising the numerical form. In other words, they're not exactly the numbers we'd see in the numerical form.

Bitwise AND

The bitwise AND operation is defined as follows:

definition. Let ${a, b \in \mathbb{B}.}$ If both ${a = 1}$ and ${b = 1}$, then ${a \band b = 1.}$ Else, ${a \band b = 0.}$

The possible results with two bits:

Bitwise OR

The Bitwise OR operation is defined as follows:

definition. Let ${a, b \in \mathbb{B}}$ be binary numbers. If ${a = 0}$ and ${b = 0,}$ then ${a \bor b = 0.}$ Else, ${a \bor b = 1.}$

Here's another example. What is the result of ${5 | 8}$? Well, first convert 5 to binary, which is 0101. Then we convert 8 to binary, which is 1000. The result then is:

The number 1101, in decimal form, is 13.

Bitwise XOR

Bitwise XOR (the exclusive or) is defined as follows:

definition. Let ${a,b \in \mathbb{B}}$. If ${a}$ and ${b}$ have the same value, then ${a \bxor b = 0.}$ Else, ${a \bxor b = 1.}$

Laying out the possibilities with two bits:

Illustrating with decimals, suppose we wanted to compute ${5 \bxor 7.}$ The decimal 5 in binary is ${101,}$ and the decimal 7 in binary is ${111.}$ Thus, we get:

Bitwise NOT

The bitwise NOT operation is a unary operation — it only takes one argument. The operation is defined as follows:

definition. Let ${n \in \mathbb{B}.}$ If ${n = 0,}$ then ${\bnot n = 1.}$ If ${n = 1,}$ then ${\bnot n = 0.}$

For example:

We can think of the bitwise NOT operation as the "bit-flipper." For example, ${\bnot 5}$ results in:

Importantly, the bitwise NOT operation will also flip the number's MSB (most significant bit). This means that the result of the number could very well be negative. Above, the number ${111010}$ is 58 in decimal.

An interesting implication of this fact is the result of coding something along these lines in some language:

int a = 0;
int b = ~a;
print(b);

This will result in ${-1.}$ Why? Because the number ${0,}$ on say, a 4-bit platform, is:

Flipping all of these bits, we get:

Because the MSB is 1, we have a negative number. The rest of the bits are the magnitude of the number. And because modern computers use 2s-complement to represent decimals, the decimal 1 is apparent when we go through the 2s compliment process.

Here, we have ${1111.}$ 2s-complement says we invert all the bits:

Then add 1:

The number ${0001}$ in binary is the number ${1.}$ Hence the result -1.

Bitwise Left-shift

The bitwise left-shift operation is defined as follows:

Defition. Let ${b \in \mathbb{B}}$ and ${n \in \nat.}$ Then ${b \bls n}$ shifts all the digits of ${b}$ to the left ${n}$ positions.

Let's look at an example. The number 5 in binary is ${0000101.}$ When we write:

we get the binary number:

Just to make the comparison clearer:

Notice how the digits have shifted by ${n}$ places. This is interesting. The number ${0101}$ in decimal is ${5,}$ and the number ${010100}$ in binary is ${20.}$ This observation leads to an alternative definition of the binary left-shift operator:

Defition. Let ${b \in \mathbb{B}}$ and ${n \in \nat.}$ Then:

$$b \bls n = c \cdot 2^n$$

where ${c}$ is the decimal form of ${b.}$

Thus, we have the following:

Bitwise Right-shift

Bitwise right shift.

Defition. Let ${b \in \mathbb{B}}$ and ${n \in \nat.}$ Then ${b \brs n}$ shifts all the digits of ${b}$ to the right ${n}$ positions.

For example, the number 10 in binary is ${001010.}$ The computation:

results in:

A before and after shot:

Notice how we lose the last two binary digits. The number ${000010}$ in decimal is ${2.}$ Like the left-shift operation, the right-shift operation also yields a more interesting definition:

Defition. Let ${b \in \mathbb{B}}$ and ${n \in \nat.}$ Then:

$$b \brs n = \floor{\dfrac{c}{2^n}} \\$$

where ${c}$ is the decimal form of ${b.}$

Thus, we have:

Note that this trick will "round the wrong way" when we shift negative numbers. That is, performing ${-5 \brs 1 = \floor{-2.5} = -3.}$ If we want the result to be closer to zero, we have to add some bias to the number:

Applications

Now that we have an understanding of the bitwise operations, let's see some useful applications. Given that we can perform some fairly interesting arithmetic with these operations, there are numerous possible applications. The curation below is just a small sampling.

#include <iostream>
#include <bitset>

std::bitset<8> printBinaryInt(int n) {
	return std::bitset<8>(n);
}

#include <iostream>

void parityCheck(int n) {
	if (n & 1) {
		std::cout << n << " is odd" << std::endl;
	} else {
		std::cout << n << " is even" << std::endl;
	}
}

#include <iostream>

int getIthBit(int n, int i) {
	int mask = 1 << i;
	return (n & mask) > 0 ? 1 : 0;
}

int main() {
	const int n = 5;
	int i;
	std::cin>>i;
	std::cout << "bit @ position " << i << " is " << getIthBit(n,i) << std::endl;
	return 0;
}