390 24.BitHacksforGames
On PowerPC processors, the cntlzw (count leading zeros word) instruction
can be used to evaluate the first expression in Table 24.1,
(a == 0), by calculat-
ing
cntlzw(a) >> 5. This works because the cntlzw instruction produces the
value 32 when its input is zero and a lower value for any other input. When shift-
ed right five bits, the value 32 becomes 1, and all other values are completely
shifted out to produce 0. A similar instruction called
BSR (bit scan reverse) exists
on x86 processors, but it produces undefined results when the input is zero, so it
cannot achieve the same result without a branch to handle the zero case.
Predicates can be used to perform a variety of conditional operations. The
expressions shown in Table 24.1 are typically used to change some other value
by one (or a power of two with the proper left shift), and the expressions shown
in Table 24.2 are typically used as masks that conditionally preserve or clear
some other value. We look at several examples in the remainder of this section.
ConditionalIncrementandDecrement
To perform conditional increment or decrement operations, the expressions
shown in Table 24.1 can simply be added to or subtracted from another value,
respectively. For example, the conditional statement
if (a >= 0) x++;
can be replaced by the following non-branching code:
x += (unsigned) ~a >> 31;
ConditionalAdditionandSubtraction
Conditional addition and subtraction can be performed by using the expressions
shown in Table 24.2 to mask the operations. For example, the conditional state-
ment
if (a >= 0) x += y;
can be replaced by the following non-branching code:
x += y & (~a >> 31);
IncrementorDecrementModuloN
The mask for the predicate (a < 0) can be used to implement increment and
decrement operations modulo a number n. Incrementing modulo 3 is particularly
common in game programming because it’s used to iterate over the vertices of a