Shift-Right Versus Divide in the C Language

Yesterday I was extending some existing font processing
code for an embedded Linux device. The code uses FreeType and thus
makes extensive use of 26.6 fixed point numbers for "font units".
(The lower 6 bits of the 32-bit number are used to represent the
fractional part of the number.)
The existing code uses the shift-right operator `>>`
pretty much everywhere to convert these numbers to integers for display,
something like

glyph_advance = glyph.advance.x + kern_offset.x;
pixel_offset = pixel_offset + glyph.advance >> 6;

I took as a rule of thumb many years ago that almost all compilers
know how to convert division and multiplication by powers-of-two into
shifts. (Even K&R's original C compiler did that.) Since "divide by 64"
seems more semantically clear to me in this case, I've been changing every
"`>> 6`" and "`<< 6`" in the code to
"`/ 64`" and "`* 64`". Then it occured to me
maybe I should *check* my rule of thumb, since I have never
used it quite so extensively to change performance-critical code.

It turns out that left-shift and multiply-by-power-of-two both compile
to left-shift, at least using -O in gcc 4.1.2 and 3.4.4 on X86 and
ARM.

**But** divide compiles into right-shift plus *a few more
instructions!* A simple example illustrates why.

#include <stdio.h>
main()
{
printf("-32 / 64 = %d, -32 >> 6 = %d\n", -32 / 64, -32 >> 6);
}

The output is the following:
-32 / 64 = 0, -32 >> 6 = -1

So right-shift really is a sign-extending right arithmetic shift. -32
divided by 64 is 0, but shifting -32 right results in extending the sign bit
throughout the result. Right-shift is therefore not equivalent to divide for
signed integers. Normally in pixel math I wouldn't care, but "kerning"
incorporates a *negative* offset into a font offset, so all this math is signed.
I've continued changing "`>>`" to divide, since now I know that
divide is not only equivalent to right-shift for unsigned integers but is also *correct* for signed integers.

## The Lesson?

Every now and then, check your assumptions. Even if you were right, you might still be surprised.

Last modified:

Thu Jul 5 14:40:31 PDT 2007