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