文档介绍：Algorithms for programmers
ideas and source code
This document is work in progress: read the ”important remarks” near the beginning
Arndt
******@
Draft version1 of 2005-January-17
1The latest version and the panying software is online at /.
ii
[fxtbook draft of 2005-January-17]
CONTENTS iii
Contents
Important remarks about this document xv
I Low level binatorial algorithms 1
1 Bit wizardry 3
Trivia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Avoiding branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Operations on low bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
the index of a single set bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Operations on high bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Functions related to the base-2 logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Counting the bits of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Swapping bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Isolating blocks of bits and single bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Bit set lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Bitwise rotation of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Functions related to bitwise rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Reversing the bits of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Bitwise zip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Gray code and parity . . . . . . . . . . . . . . . . . . . . . . . . . .