Hacker's Delight 2nd Edition.pdf-资料库

shenpanzhimao-10796991-Hacker-'s Delight 2nd Edition.pdf-第1页.png

第1页 / 共470页

shenpanzhimao-10796991-Hacker-'s Delight 2nd Edition.pdf-第2页.png

第2页 / 共470页

shenpanzhimao-10796991-Hacker-'s Delight 2nd Edition.pdf-第3页.png

第3页 / 共470页

shenpanzhimao-10796991-Hacker-'s Delight 2nd Edition.pdf-第4页.png

第4页 / 共470页

shenpanzhimao-10796991-Hacker-'s Delight 2nd Edition.pdf-第5页.png

第5页 / 共470页

shenpanzhimao-10796991-Hacker-'s Delight 2nd Edition.pdf-第6页.png

第6页 / 共470页

shenpanzhimao-10796991-Hacker-'s Delight 2nd Edition.pdf-第7页.png

第7页 / 共470页

shenpanzhimao-10796991-Hacker-'s Delight 2nd Edition.pdf-第8页.png

第8页 / 共470页

Hacker’s Delight Second Edition Henry S. Warren, Jr. Upper Saddle River, NJ • Boston • Indianapolis • San Francisco New York • Toronto • Montreal • London • Munich • Paris • Madrid CapeTown • Sydney • Tokyo • Singapore • Mexico City

To Joseph W. Gauld, my high school algebra teacher, for sparking in me a delight in the simple things in mathematics

Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals. The author and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein. The publisher offers excellent discounts on this book when ordered in quantity for bulk purchases or special sales, which may include electronic versions and/or custom covers and content particular to your business, training goals, marketing focus, and branding interests. For more information, please contact: U.S. Corporate and Government Sales (800) 382-3419 corpsales@pearsontechgroup.com For sales outside the United States, please contact: International Sales international@pearsoned.com Visit us on the Web: informit.com/aw Library of Congress Cataloging-in-Publication Data Warren, Henry S. Hacker’s delight / Henry S. Warren, Jr. -- 2nd ed. p. cm. Includes bibliographical references and index. ISBN 0-321-84268-5 (hardcover : alk. paper) 1. Computer programming. I. Title. QA76.6.W375 2013 005.1—dc23 2012026011 Copyright © 2013 Pearson Education, Inc. All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to (201) 236-3290. ISBN-13: 978-0-321-84268-8 ISBN-10: 0-321-84268-5 Text printed in the United States on recycled paper at Courier in Westford, Massachusetts. First printing, September 2012

Contents Foreword Preface CHAPTER 1. INTRODUCTION 1–1 Notation 1–2 Instruction Set and Execution Time Model CHAPTER 2. BASICS 2–1 Manipulating Rightmost Bits 2–2 Addition Combined with Logical Operations 2–3 Inequalities among Logical and Arithmetic Expressions 2–4 Absolute Value Function 2–5 Average of Two Integers 2–6 Sign Extension 2–7 Shift Right Signed from Unsigned 2–8 Sign Function 2–9 Three-Valued Compare Function 2–10 Transfer of Sign Function 2–11 Decoding a “Zero Means 2**n” Field 2–12 Comparison Predicates 2–13 Overflow Detection 2–14 Condition Code Result of Add, Subtract, and Multiply 2–15 Rotate Shifts 2–16 Double-Length Add/Subtract 2–17 Double-Length Shifts 2–18 Multibyte Add, Subtract, Absolute Value 2–19 Doz, Max, Min 2–20 Exchanging Registers 2–21 Alternating among Two or More Values 2–22 A Boolean Decomposition Formula 2–23 Implementing Instructions for all 16 Binary Boolean Operations CHAPTER 3. POWER-OF-2 BOUNDARIES 3–1 Rounding Up/Down to a Multiple of a Known Power of 2 3–2 Rounding Up/Down to the Next Power of 2 3–3 Detecting a Power-of-2 Boundary Crossing CHAPTER 4. ARITHMETIC BOUNDS 4–1 Checking Bounds of Integers 4–2 Propagating Bounds through Add’s and Subtract’s 4–3 Propagating Bounds through Logical Operations

CHAPTER 5. COUNTING BITS 5–1 Counting 1-Bits 5–2 Parity 5–3 Counting Leading 0’s 5–4 Counting Trailing 0’s CHAPTER 6. SEARCHING WORDS 6–1 Find First 0-Byte 6–2 Find First String of 1-Bits of a Given Length 6–3 Find Longest String of 1-Bits 6–4 Find Shortest String of 1-Bits CHAPTER 7. REARRANGING BITS AND BYTES 7–1 Reversing Bits and Bytes 7–2 Shuffling Bits 7–3 Transposing a Bit Matrix 7–4 Compress, or Generalized Extract 7–5 Expand, or Generalized Insert 7–6 Hardware Algorithms for Compress and Expand 7–7 General Permutations, Sheep and Goats Operation 7–8 Rearrangements and Index Transformations 7–9 An LRU Algorithm CHAPTER 8. MULTIPLICATION 8–1 Multiword Multiplication 8–2 High-Order Half of 64-Bit Product 8–3 High-Order Product Signed from/to Unsigned 8–4 Multiplication by Constants CHAPTER 9. INTEGER DIVISION 9–1 Preliminaries 9–2 Multiword Division 9–3 Unsigned Short Division from Signed Division 9–4 Unsigned Long Division 9–5 Doubleword Division from Long Division CHAPTER 10. INTEGER DIVISION BY CONSTANTS 10–1 Signed Division by a Known Power of 2 10–2 Signed Remainder from Division by a Known Power of 2 10–3 Signed Division and Remainder by Non-Powers of 2 10–4 Signed Division by Divisors ≥ 2 10–5 Signed Division by Divisors ≤ –2 10–6 Incorporation into a Compiler 10–7 Miscellaneous Topics 10–8 Unsigned Division

10–9 Unsigned Division by Divisors ≥ 1 10–10 Incorporation into a Compiler (Unsigned) 10–11 Miscellaneous Topics (Unsigned) 10–12 Applicability to Modulus and Floor Division 10–13 Similar Methods 10–14 Sample Magic Numbers 10–15 Simple Code in Python 10–16 Exact Division by Constants 10–17 Test for Zero Remainder after Division by a Constant 10–18 Methods Not Using Multiply High 10–19 Remainder by Summing Digits 10–20 Remainder by Multiplication and Shifting Right 10–21 Converting to Exact Division 10–22 A Timing Test 10–23 A Circuit for Dividing by 3 CHAPTER 11. SOME ELEMENTARY FUNCTIONS 11–1 Integer Square Root 11–2 Integer Cube Root 11–3 Integer Exponentiation 11–4 Integer Logarithm CHAPTER 12. UNUSUAL BASES FOR NUMBER SYSTEMS 12–1 Base –2 12–2 Base –1 + i 12–3 Other Bases 12–4 What Is the Most Efficient Base? CHAPTER 13. GRAY CODE 13–1 Gray Code 13–2 Incrementing a Gray-Coded Integer 13–3 Negabinary Gray Code 13–4 Brief History and Applications CHAPTER 14. CYCLIC REDUNDANCY CHECK 14–1 Introduction 14–2 Theory 14–3 Practice CHAPTER 15. ERROR-CORRECTING CODES 15–1 Introduction 15–2 The Hamming Code 15–3 Software for SEC-DED on 32 Information Bits 15–4 Error Correction Considered More Generally

CHAPTER 16. HILBERT’S CURVE 16–1 A Recursive Algorithm for Generating the Hilbert Curve 16–2 Coordinates from Distance along the Hilbert Curve 16–3 Distance from Coordinates on the Hilbert Curve 16–4 Incrementing the Coordinates on the Hilbert Curve 16–5 Non-Recursive Generating Algorithms 16–6 Other Space-Filling Curves 16–7 Applications CHAPTER 17. FLOATING-POINT 17–1 IEEE Format 17–2 Floating-Point To/From Integer Conversions 17–3 Comparing Floating-Point Numbers Using Integer Operations 17–4 An Approximate Reciprocal Square Root Routine 17–5 The Distribution of Leading Digits 17–6 Table of Miscellaneous Values CHAPTER 18. FORMULAS FOR PRIMES 18–1 Introduction 18–2 Willans’s Formulas 18–3 Wormell’s Formula 18–4 Formulas for Other Difficult Functions ANSWERS TO EXERCISES APPENDIX A. ARITHMETIC TABLES FOR A 4-BIT MACHINE APPENDIX B. NEWTON’S METHOD APPENDIX C. A GALLERY OF GRAPHS OF DISCRETE FUNCTIONS C–1 Plots of Logical Operations on Integers C–2 Plots of Addition, Subtraction, and Multiplication C–3 Plots of Functions Involving Division C–4 Plots of the Compress, SAG, and Rotate Left Functions C–5 2D Plots of Some Unary Functions Bibliography Index

资料库

Hacker's Delight 2nd Edition.pdf

相关推荐

安全技术

热门标签

最新资料