Casting Out

Most school children are taught about ‘Casting Out The Nines’ — specifically that a number is divisible by 9 if the sum of its digits is divisible by 9. This page explains the more general principle of casting out, and ends with an example of how it can be used in bit bashing.

Modular Arithmetic

This page includes modular arithmetic — if you are not familiar with modular arithmetic, it is sufficient to say that two numbers a and b are equal ‘mod n’ if the have the same remainder after division by n. This is written a=b (mod n), so for example 2 = 11 (mod 3) and 8 = −2 (mod 5).

If a=b (mod n) and c=d (mod n) then a+c=b+d (mod n) and a×c=b×d (mod n). Using these equations we can show how ‘casting out the nines’ works.

Casting Out The Nines

If a number in base ten (decimal/denary) is written d_nd_n-1…d₁ (that is, its ith digit is d_i), its remainder r after division by 9 satisfies the following equation:

r=d_n×10^n-1+d_n-1×10^n-2+…+d₁×10⁰ (mod 9)

But as 10=1 (mod 9) then 10ⁱ=1 (mod 9) by the rule for multiplication given above, so the equations simplifies to:

r=d_n+d_n-1+…+d₁ (mod 9)

So if the sum of the digits of a number is divisible by 9, so is the original number.

Casting Out In General

The principle of casting out can be extended to other bases. If a number gives remainder r when divided by n, the sum if its digits in base n+1 also give remainder r when divided by n.

This is usually used to find the remainder by summing the digits, but in bit bashing it is used to find the sum of digits by finding the remainder — they are equal if the sum of digits is guaranteed to be less than the divisor.

Bit bashing example

The following program counts number of ones in a four-bit variable a and stores the result in the variable b, so long as the computer supports 12-bit numbers:

b = a * 000100010001
b = b & 001001001001
b = b % 111

If the variable a contains the digits abcd, the first line creates the number abcdabcdabcd. The second line creates the number 00c00b00a00d. The third line finds the remainder after division by 7, which by casting out is equal to 00c+00b+00a+00d. This is guaranteed to be less than 7, so the value is equal to the sum a+b+c+d — the number of ones in a.