CS Ramble — Set 2c - binary and bits

This is post is part of set 2 of A Ramble Around CS.

In this post, we’re going to become more familiar with thinking in binary.

Basics

Let’s use our example byte from last time to show the anatomy of a byte: 0b10111001 == 0xB9 == 185

1 0 1 1 1 0 0 1 128 64 32 16 8 4 2 1 “high bit” “low bit” B “high nibble”     9     “low nibble”

Note: the work “nibble” is less common these days than it used to be, when computers had much less memory, and making maximum use of every little bit was more important. Don’t be surprised if people haven’t heard of it: you can name-drop “high nibble” to increase your nerd cred!

Bit shifting

In base 10, if we shift digits to the left or right, we’re multiplying or dividing by 10:

1 8 5 1 8 5 0 shift ← shift ← 1 8 5 1 8 shift → shift →

In base 2, if we shift digits to the left or right, we’re multiplying or dividing by 2:

1 1 1 1 1 1 0 shift ← shift ← 1 1 1 1 1 shift → shift →

In code, we use << to shift left, and >> to shift right:

# python:
print(bin(0b111 << 1))  # 0b1110
print(bin(0b111 >> 1))  # 0b11

We can shift by a lot if we have the space for it. In python, there’s no real limit on how big numbers can be, so we can shift as far as we like:

print(bin(1 << 10))     # 0b10000000000
print(1 << 10)          # 1024
print(1<<130)           # 1361129467683753853853498429727072845824

In a language like Go, where the bit widths are fixed (because numbers occupy a specific number of bytes), we can shift right off the end!

var a uint8 = 1
fmt.Println(a<<7)  # 128
fmt.Println(a<<8)  # 0

(Longer example with several different widths you can play around with here.)

As you may have noticed, you can (within the bounds of the bit-width of your variable), replace 2ⁿ with 1 << n, and you can likewise replace x × 2ⁿ with x << n. You can also replace ⌊ˣ⁄₂⌋ with x >> 1 and ⌊x/2ⁿ⌋ with x >> n1. In fact, in compiled languages, your compiler will make these substitutions in the compiled code whenever it can, because bit-shifting is faster than multiplication.

Although that may take a few minutes to sink in, you’re already familiar with it in good old base 10: how do you multiply by 1000? Just shift left three places (add three zeros). Since you multiply by 10 each time you shift left once, you can multiply by 10³ by shifting left 3 places.

Fractions

We’re going to get into it deeply, but you can of course write fractions in other bases. In base 10, we divide by ten each time we move to the right, so the digit to the right of the “decimal” point is of course the ⅒ column. To represent ½, we use ⁵⁄₁₀, and write 0.5.

In octal, the column to the right of the point is the ⅛ column, so we’d use ⁴⁄₈, and write 0.4₈.

In binary, it’s the ½ column already, so we’d use ½, and write 0.1₂. ¼ would be 0.01₂, and ¾ would be 0.11₂. Weird, huh? But it all makes sense:

0 0 0 0 . 1 1 0 0 8 4 2 1 ½ ¼ ⅛ 1⁄16 ¾ ＝ ½ + ¼

We’ll explore how to work with the values of individual bits or true/false values in the next part.

  1. If you’re a bit rusty, ⌊a⌋ means the next integer (whole number) equal to or less than a. It’s called the “floor” of a: ⌊2⌋ ＝ 2, ⌊1.9⌋ ＝ 1, and ⌊−1.9⌋ ＝ −2. Similarly, ⌈a⌉ is the “ceiling” of a: ⌈2⌉ ＝ 2, ⌈1.9⌉ ＝ 2, and ⌈−1.9⌉ ＝ −1. ↩︎