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
C
HAPTER 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
C
HAPTER 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
C
HAPTER 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
