Game Engine Gems 2

 385

24

BitHacksforGames

Eric Lengyel

Terathon Software

Game programmers have long been known for coming up with clever tricks that

allow various short calculations to be performed more efficiently. These tricks

are often applied inside tight loops of code, where even a tiny savings in CPU

clock cycles can add up to a significant boost in speed overall. The techniques

usually employ some kind of logical bit manipulation, or “bit twiddling,” to ob-

tain a result in a roundabout way with the goal of reducing the number of instruc-

tions, eliminating expensive instructions like divisions, or removing costly

branches. This chapter describes a variety of interesting bit hacks that are likely

to be applicable to game engine codebases.

Many of the techniques we describe require knowledge of the number of bits

used to represent an integer value. The most efficient implementations of these

techniques typically operate on integers whose size is equal to the native register

width of the CPU running the code. This chapter is written for integer registers

that are 32 bits wide, and that is the size assumed for the

int type in C/C++. All

of the techniques can be adapted to CPUs having different native register widths

(most commonly, 64 bits) by simply changing occurrences of the constants 31

and 32 in the code listings and using the appropriately sized data type.

24.1IntegerSignManipulation

We begin with a group of techniques that can be used to extract or modify infor-

mation about the sign of an integer value. These techniques, and many more

throughout this chapter, rely on the assumption that a signed right shift using the

>> operator preserves the sign of the input by smearing the original sign bit

across the high bits opened by the shift operation. Strictly speaking, shifting a

negative number to the right produces implementation-defined results according

386 24.BitHacksforGames

to the C++ standard

1

, but all compilers likely to be encountered in game devel-

opment give the expected outcome—if the bits are shifted to the right by n bit

positions, then the value of the highest bit of the input is replicated to the highest

n bits of the result.

AbsoluteValue

Most CPU instruction sets do not include an integer absolute value operation.

The most straightforward way of calculating an absolute value involves compar-

ing the input to zero and branching around a single instruction that negates the

input if it happens to be less than zero. These kinds of code sequences execute

with poor performance because the branch prevents good instruction scheduling

and pollutes the branch history table used by the hardware for dynamic branch

prediction.

A better solution makes clever use of the relationship

~1

x

x





, (24.1)

where the unary operator

~

represents the bitwise NOT operation that inverts

each bit in x. In addition to using the

~ operator in C/C++, the NOT operation can

be performed by taking the exclusive OR between an input value and a value

whose bits are all 1s, which is the representation of the integer value

1



. So we

can rewrite Equation (24.1) in the form









^1 1

x

x



, (24.2)

where the reason for subtracting

1



at the end will become clear in a moment.

If we shift a signed integer right by 31 bits, then the result is a value that is

all ones for any negative integer and all zeros for everything else. Let

m be the

value of x shifted right by 31 bits. Then a formula for the absolute value of x is

given by





^

x

xm m



 . (24.3)

If

0

x

 , then 1m  and this is equivalent to Equation (24.2). If

0

x

 , then 0m  ,

and the right-hand side of Equation (24.3) becomes a no-op because performing

an exclusive OR with zero does nothing and subtracting zero does nothing. So

now we have a simple formula that calculates the absolute value in three instruc-

tions, as shown in Listing 24.1. The negative absolute value operation is also

1

See Section 5.8, Paragraph 3 of the C++ standard.