Algorithms For Programmers Ideas And Source Code.pdf

文档介绍：Algorithms for programmers
ideas and source code
This document is work in progress: read the ”important remarks” near the beginning
Arndt
******@
Draft version1 of 2006-September-11
1The latest version and the panying software is online at /.
ii
[fxtbook draft of 2006-September-11]
CONTENTS iii
Contents
Important remarks about this document xv
I Low level binatorial algorithms 1
1 Bit wizardry 3
Trivia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Copying and swapping bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Avoiding branches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Conditional swap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
piler may be smarter than you thought . . . . . . . . . . . . . . . . . . . 10
Operations on low bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
the index of a single set bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Operations on high bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Functions related to the base-2 logarithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Counting the bits of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Isolating blocks of bits and single bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Bit set lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Bitwise rotation of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Functions related to bitwise rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Swapping bits or blocks of a word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28