Binary Place Values — Bit Manipulation

Focus By the end of this chapter you should be able to look at an 8-bit pattern and mentally compute its value as a sum of powers of 2; and conversely, decompose a number like 42 into its binary representation. Everything else in bit manipulation builds on this one skill.

If we work with a high-level language like Python or JavaScript, or if we're generic computer users, we don't really think much about binary numbers or binary operations. But if we wish to understand how computers work at a lower level, getting a good intuition for binary representations is essential. The goal of this chapter is to build that mental model.

Let's start with something simple and familiar, the number 365. This number can be decomposed into three components. The hundreds, the tens, and the ones. So we have 300, 60, and 5, which all add up to 365! This is what makes this number a decimal number, or a Base 10 number. We have ten possible values (the numbers 0 to 9); and once we use all of them, we add a new column to the right. Each of these new columns represents a power of 10, which are things like 1, 10, 100, 1000... So the number 365 is actually described as a sum over powers of 10: 365 = 3·100 + 6·10 + 5·1 The total value is just the sum of each digit multiplied by its column's weight.

Binary numbers are exactly the same thing. The only differences are that a) columns multiply by 2 instead of 10; and b) each digit can only have two possible values: a 0 or 1. This is why we call these Base 2 numbers In base 2 numbers, each digit is called a bit. We can think of each bit as an independent on/off switch for its column's value. An 8-bit number has exactly eight of these switches, controlling columns that are powers of two: 128, 64, 32, 16, 8, 4, 2, and 1 from left to right.

In an 8-bit number representation, the value of the number is the sum of every column where the switch is on. Let's say we have 8 bits, where bit 0 is b₀:

value = b₇·128 + b₆·64 + b₅·32 + b₄·16 + b₃·8 + b₂·4 + b₁·2 + b₀·1

With n bits we can represent 2ⁿ unique values — from 0 (all switches off) to 2ⁿ−1 (all switches on). With 8 bits, we can cover numbers from 0 to 255.

Notice that each bit is completely independent. Flipping bit k changes the total by exactly 2^k and nothing else shifts. This independence is what makes a lot of the bit tricks work. These will be covered in later chapters. In the interactive demo below, toggle the switches and pay attention to each column's contribution.

Demo 1.1 — Binary Place Value Explorer

Presets:

0 decimal

Analogy: the only difference from decimal is that columns multiply by 2 instead of 10, and each digit is 0 or 1 instead of 0–9.

Decimal — 365

3 × 100
6 × 10
5 × 1
= 365

Binary — 101101101

1×256 + 0×128 + 1×64
+ 1×32 + 0×16 + 1×8
+ 1×4 + 0×2 + 1×1
= 365

Try 7 and 8 in the presets. Seven is 00000111, which has the lowest three bits turned on, which is 4+2+1. Eight is 00001000, which has a single bit turned on exactly one position to the left, giving precisely 8. In binary numbers, every power of 2 has a single active bit. And every number just below that power of 2 is a sequence of ones. This is one of the many patterns that come up constantly in bit manipulation.

The main take-away from this chapter is to acquire an intuition for binary numbers as a sum over powers of 2, and how these can describe any positive integers. But notice how we do not yet cover negative numbers. Let's extend this intuition to negative numbers in the next chapter.