Shifting and Masking

Several pro­gram­ming languages now provide a 0b prefix for binary literals to go along with the 0x prefix for hex literals and the 0o prefix for octal literals. (Older languages, such as C, use a 0 prefix for octal and have no 0b prefix.) See the discussion in Go number literals for more detail on 0b, including a list of languages that now support this notation.

2ⁿ, written in binary, looks like 1 followed by n 0s. For example, 2³ = 1000₂. In C-like languages, 2ⁿ can be written as 1 << n.

Similarly, 2ⁿ − 1, (1 << n) - 1, written in binary, looks like n 1s. For example, 2⁵ − 1 = 31₁₀ = 11111₂.

We can multiply an unsigned integer, u, by 2ⁿ by shifting u left by n bits, u << n, in­tro­duc­ing n zeroes as the low-order bits. For example, using 8-bit numbers without loss of generality, written as modern Go/Rust number literals:

0b_0001_0101 << 3 == 0b_1010_1000

Similarly, we can divide u by 2ⁿ by shifting u right by n bits, u >>> n, which drops the n low-order bits and introduces n zeroes as the high-order bits.

0b_0101_0110 >>> 3 == 0b_0000_1010

A sign-extending or arithmetic right shift introduces n copies of the sign bit as the high-order bits. In some languages, such as Java and JavaScript, >> means an arithmetic right shift and >>> means a zero-extending right shift. In other languages, including C, C++, and Go, there is only a >> operator and sign-extension generally depends upon the type of the left operand, signed or unsigned. However, sign extension is not guaranteed in C/C++.

0b_0101_0110 >> 2 == 0b_0001_0101
0b_1001_0110 >> 2 == 0b_1110_0101

Finally, we can find the remainder of dividing u by 2ⁿ by masking u with 2ⁿ − 1, that is, bitwise-and with (1 << n) - 1, to extract the n low-order bits:

0b_0101_0110 & 0b_0000_0111 = 0b_0000_0110

In other words, u % 8 == u & 7 and u / 8 == u >> 3.

Read bitwise operations for more background.

Casting Out Nines

There’s an old trick for checking the results of arithmetic operations, known as casting out nines or dropping nines.

Add up the decimal digits of each number. Apply the arithmetic operation to these digit sums. They should be congruent, modulo 9.

For example, 12, 345×8, 765 = 108, 203, 925.

To check the mul­ti­pli­ca­tion, compute the digit sum of each number, by adding up each decimal digit:

and

Take the first two digit sums, modulo 9, and multiply them:

Check against the sum of the digits of the product:

This works because 10ⁿ ≡ 1 ( mod 9).

Consider 758:

Dropping the nines from each term leaves the digit sum, which is congruent to the original number modulo nine:

Checking: 758  mod 9 = 2.

Con­gru­ences have a number of useful properties.

Casting Out Elevens

Let’s use 11, instead of 9. Since 10 = 11 − 1, then 10ⁿ ≡  − 1ⁿ (mod 11).

Consider 5234:

Dropping the elevens from each term leaves the al­ter­nat­ing digit sum:

It’s more convenient to proceed rightwards from the least sig­nif­i­cant digit, 4 − 3 + 2 − 5.

Checking: 5234  mod 11 = 9.

To cast out elevens, we calculate the al­ter­nat­ing sum from right to left.

Casting out elevens catches some trans­po­si­tion errors, unlike casting out nines. For more, see di­vis­i­bil­i­ty rule for 11 and proof for al­ter­nat­ing sum.

Modulo 9

At last, we turn to base 8, octal. Nine bears the same re­la­tion­ship to eight in octal, as eleven does to ten in decimal: 9₁₀ = 11₈, base plus one, and 8ⁿ ≡  − 1ⁿ (mod 9).

We can calculate k mod 9 in base 8 by al­ter­nate­ly adding and sub­tract­ing the octal digits, from right to left. For example, 1234₈  mod 9 = 4 − 3 + 2 − 1 = 2. This gives the right answer.

Here’s a simple, albeit incomplete, algorithm in Go. We’re masking and shifting three bits at a time, which is tantamount to working with the octal rep­re­sen­ta­tion of k.

func Mod9(k uint) uint {
    var m int = 0
    sign := +1

    for t := k; 0 != t; t >>= 3 {
        r := int(t & 7)
        m += sign * r
        sign = -sign
    }

    return uint(m)
}

What about 617₈?

And 6172₈?

Almost there!

Casting out “octal-elevens” (11₈ = 9₁₀) in octal, by an al­ter­nat­ing sum of the base-eight digits, computes a small number congruent to the original number number modulo nine.

The algorithm above is cal­cu­lat­ing numbers that are congruent to the correct answer modulo nine, but which may be outside the desired range. If the in­ter­me­di­ate sum dips below zero or rises above eight, we have to add nine or subtract nine re­spec­tive­ly to keep the running total in the range [0, 9).

Here’s a complete algorithm for Modulo 9 in Go, computing the al­ter­nat­ing sum of the octal digits:

func Mod9(k uint) uint {
    var m int = 0
    var negative bool = false

    for t := k; 0 != t; t >>= 3 {
        r := int(t & 7)
        if negative {
            m -= r
            if m < 0 {
                m += 9
            }
        } else {
            m += r
            if m >= 9 {
                m -= 9
            }
        }
        // assert(0 <= m && m < 9)
        negative = !negative
    }

    return uint(m)
}

Clearly, this algorithm can be im­ple­ment­ed in much simpler circuitry than that required to compute a remainder through full-blown division.

Modulo 36

We now have enough to calculate k mod 36 from Mod9 and the Chinese Remainder Theorem:

func Mod36(k uint) uint {
    Residues := [4][9]uint{
        { 0, 28, 20, 12,  4, 32, 24, 16,  8},
        { 9,  1, 29, 21, 13,  5, 33, 25, 17},
        {18, 10,  2, 30, 22, 14,  6, 34, 26},
        {27, 19, 11,  3, 31, 23, 15,  7, 35},
    }
    return Residues[k & 3][Mod9(k)]
}

My friend says that he later learned that similar tricks were used in classic 36-bit hardware.

I looked everywhere I could think of to see if I could find this algorithm to calculate modulo 9 described. I found something that hinted at it in Knuth’s Semi­nu­mer­i­cal Algorithms, §4.4.C, discussing converting octal integers to decimal by hand, where he mentions using casting out nines in octal and in decimal to check the result. There was no mention of it in Warren’s marvelous Hacker’s Delight or in HAKMEM.

I tried to come up with an analytic way to calculate the elements of the 9x4 table. The best that I found is (72 − 8×(k mod 9) + 9×(k mod 4))  mod 36! The inner expression yields a number in the range [0, 99], which can be reduced to [0, 36) by sub­tract­ing 36 at most twice. From Concrete Math­e­mat­ics, mod 36 can be derived from mod 4 and mod 9 by looking at the [0][1] and [1][0] elements of the table: (9×(k mod 4) + 28×(k mod 9))  mod 36. It works, but it’s even worse. A table lookup is clearly more efficient.

Most, if not all, of the computer ar­chi­tec­tures designed in the last forty years use a word size that is a power of two. Useful re­la­tion­ships like shifting and masking are one big reason why non-power-of-two word sizes have gone out of fashion.

Another big reason is the success of C and Unix, which have a bias towards 8-bit bytes. C doesn’t require 8-bit bytes, but there’s a lot of software which tacitly assumes that char has exactly 8 bits.

On systems with 9-bit bytes, like the 36-bit computers, octal is useful, since a 9-bit byte can hold all values up to 777₈ and the word size is a multiple of three.

And there you have it: an unexpected use for octal notation. It’s not exactly an important use, but then 36-bit computers aren’t exactly important any more either.