ABSTRACT
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 obtain a result in a roundabout way with the goal of reducing the number of instructions, 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.
