Algorithms for programmers ideas and source code
This document is work in progress: read the “important remarks” near the beginning
J¨org Arndt
[email protected] Draft version1 of 2008-January-19
1
The latest version and the accompanying software is online at
http://www.jjj.de/fxt/.
ii
[fxtbook draft of 2008-January-19]
CONTENTS
iii
Contents Important remarks about this document
xi
I
1
Low level algorithms
1 Bit wizardry 1.1 Trivia . . . . . . . . . . . . . . . . . . . . . . . 1.2 Operations on individual bits . . . . . . . . . . 1.3 Operations on low bits or blocks of a word . . 1.4 Isolating blocks of bits and single bits . . . . . 1.5 Computing the index of a single set bit . . . . 1.6 Operations on high bits or blocks of a word . . 1.7 Functions related to the base-2 logarithm . . . 1.8 Counting bits and blocks of a word . . . . . . 1.9 Bit set lookup . . . . . . . . . . . . . . . . . . 1.10 Avoiding branches . . . . . . . . . . . . . . . . 1.11 Bit-wise rotation of a word . . . . . . . . . . . 1.12 Functions related to bit-wise rotation * . . . . 1.13 Reversing the bits of a word . . . . . . . . . . 1.14 Bit-wise zip . . . . . . . . . . . . . . . . . . . . 1.15 Gray code and parity . . . . . . . . . . . . . . 1.16 Bit sequency . . . . . . . . . . . . . . . . . . . 1.17 Powers of the Gray code . . . . . . . . . . . . 1.18 Invertible transforms on words . . . . . . . . . 1.19 Moves of the Hilbert curve