Would someone mind elaborating the explanation in the manual?

[Brian Hurt]

On Mon, 27 Oct 2003, Kevin Ryde wrote:

> If you're only testing divisibility then for instance n%3==0 becomes
> 
> 	(n * 0xAAAAAAAB) <= 0x55555555
> 
> which is one multiply.

In 32-bit.  In 64-bit, if n = 3, then n * 0xAAAAAAAB becomes 0x200000001, 
and the test fails.  Although you can make you life somewhat simpler by 
only dealing with three cases: 1) 32-bit, where you test that (n * 
0xAAAAAAAB) <= 0x5555555, 2) 64-bit, where you test that (n * 
0xAAAAAAAAAAAAAAAB) <= 0x5555555555555555), and 3) everything else, where 
you test that (n % 3) == 0.

I'd keep case 3.

You snipped too much here:
> > Which isn't always faster than a divide instruction.
> 
> True, that should be checked, but almost everywhere one multiply is
> faster than a divide.
> 

In every architecture I know of, multiply is at least as fast as divide, 
and generally faster.  I'm not sure it's true that a divide is slower than 
2 multiplies, a shift, and a subtract (which is what I was comparing it 
to).

Brian