tailieunhanh - Matters Computational Ideas, Algorithms, Source CodeJ¨rg Arndt

The first electronic digital computers were developed between 1940 and 1945 in the United Kingdom and United States. Originally they were the size of a large room, consuming as much power as several hundred modern personal computers (PCs).[1] In this era mechanical analog computers were used for military applications. | Matters Computational Ideas Algorithms Source Code Jorg Arndt ii CONTENTS Contents Preface iii xi I Low level algorithms 1 1 Bit wizardry 2 Trivia. 2 Operations on individual bits. 7 Operations on low bits or blocks of a word. 8 Extraction of ones zeros or blocks near transitions. 11 Computing the index of a single set bit. 13 Operations on high bits or blocks of a word. 14 Functions related to the base-2 logarithm. 17 Counting the bits and blocks of a word . 18 Words as bitsets. 23 Index of the i-th set bit. 25 Avoiding branches. 25 Bit-wise rotation of a word. 27 Binary necklaces z. 29 Reversing the bits of a word . 33 Bit-wise zip . 38 Gray code and parity. 41 Bit sequency z. 46 Powers of the Gray code z . 48 Invertible transforms on words z . 49 Scanning for zero bytes. 55 Inverse and square root modulo 2n. 56 Radix 2 minus two representation. 58 A sparse signed binary representation . 61 Generating bit combinations . 62 Generating bit subsets of a given word . 68 Binary words in lexicographic order for subsets . 70 Fibonacci words z . 74 Binary words and parentheses strings z . 78 Permutations via primitives z . 80 CPU instructions often missed. 82 Some space filling curves z . 83 2 Permutations and their operations 102 Basic definitions and Representation as disjoint Compositions of .