Bit Tricks, Part I: Exact Division

GCC has some clever tricks up its sleeve for compiling the humble division operator.

This is part 1 of a series of posts on bit-twiddling tricks and micro-optimizations. This one looks at ways to try to optimize the following function:

"Constant"
int exactDiv3(int x) {  // given that x is a multiple of 3
  return x/3;
}

Integer arithmetic (in binary) is usually done in two's complement^(W), meaning that negative numbers are stored as an infinite string of ones:

...00000000010 =  2
...00000000001 =  1
...00000000000 =  0
...11111111111 = -1
...11111111110 = -2
...11111111101 = -3

This works rather nicely; if you have -1 in a register and you add one, the carry goes all the way to the left and eventually "falls off the end", and you end up with zero (as you should).

To flip the sign of a number, you invert all the bits, and add one:

...00000001100 = 12
...11111110011 = ～12 = -11
...11111110100 = ～12 + 1 = -12

Now consider this infinitely long string of bits, where only half the bits are 1s:

...010101010101 = ?

   ...010101010101 * 11 =
   ...010101010101
 + ...10101010101
 = ...111111111111  = -1 ?

... so apparently the mystery number ...010101 behaves like -⅓. If it really is -⅓, we should be able to do this:

...010101010101 = -⅓
...101010101010 = ～(-⅓)
...101010101011 = ～(-⅓) + 1 = -(-⅓) = ⅓

Let's try multiplying 9 by our "⅓":

  ...101010101011 * 1001 =
  ...101010101011 
+ ...010101011000
= ...000000000011 = 3

It actually works!

int exactDiv3(int x) {
  return x * 0xaaaaaaab;
}

This works in decimal as well: The next time you need to divide a number by 13, just multiply by ...23076923076923076923077 instead. It's that simple!

91 * 23076923076923076923077 = 2100000000000000000000007

91 * ...076923076923077 = ...000000000000007 = 7

Wikipedia has a nice article about 2-adic numbers¹. If you don't like infinite bit strings, you can pretend we're just using inverses in the group formed by the odd integers under multiplication mod 2^W. In fact, Java even has a library method for finding such inverses:

BigInteger a = BigInteger.valueOf(3);
BigInteger m = BigInteger.ONE.shiftLeft(64);
out.println(a.modInverse(m).toString(16));
// prints "aaaaaaaaaaaaaaab"

Since this trick only works when there is no remainder, GCC will (as far as I know) only use it one situation.

When subtracting two pointers to the same array, it needs to divide the raw pointer difference by the element size. This difference will always be an exact multiple of the element size (this is guaranteed by one of the "nasal demon^(W) clauses" in the C standard).

You can force it to accept arbitrary integers by doing something like this (no, I'm not suggesting you use this anywhere):

"Exact"
template<int i> class dummy { char x[i]; };
template<int i> int divideby(int x) {
  return ((dummy<i>*)x) - (dummy<i>*)0;
}
int main() {
  printf("%d %d\n", divideby<5>(210), divideby<5>(7));
}
// output: 42 -1717986917

There's one additional snag, though: If the divisor is an even number, there is no direct multiplicative inverse. However, since we're still assuming there is no remainder, it is safe the use a bit shift to handle the 2ⁿ factor². The following function...

	int test(int n) {
	  return divide<20>(n);
	}

... can be compiled as (to see this, just run g++ -S foo.cpp and inspect the resulting .S file)

	;; essentially   return (x>>2) * -858993459;

        sarl    $2, %eax
        imull   $-858993459, %eax, %eax
        ret

This graph shows the runtime for each of the three division implementations: division by a variable using IDIV, division by a constant as optimized by GCC into a multiplication followed by fixups, and the exact division method.

Note how powers of 2 are most efficient (requiring a bitshift only), with odd numbers (multiplication but no shift) as a close second.

Another common operation is checking if the remainder is zero:

if (x % 7 == 0) { 
  ...

This can be simplified to...³

if (x * inverse(7) <= floor(2**32/7)) {
  ...

... that is, checking that the result of the inverse multiplication can be multiplied by 7 without overflowing again. As far as I can tell, no compilers actually use this trick.

Footnotes:

1. For all prime values of 2
2. It's unsafe in general, since negative numbers will round the wrong way. (-5/2) is -2, but (-5>>1) is -3.
3. Assuming x is unsigned; signed integers may require more instructions