Addison Wesley - Hackers Delight 2002.pdf

(6206 KB) Pobierz
This document was created by an unregistered ChmMagic, please go to http://www.bisenter.com to register it. Thanks
.
Copyright
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 Addison-Wesley 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 discounts on this book when ordered in quantity for special sales. For more
information, please contact:
U.S. Corporate and Government Sales
(800) 382-3149
corpsales@pearsontechgroup.com
For sales outside of the U.S., please contact:
International Sales
(317) 581-3793
international@pearsontechgroup.com
Visit Addison-Wesley on the Web:
www.awprofessional.com
Library of Congress Cataloging-in-Publication Data
Warren, Henry S.
Hacker's delight / Henry S. Warren, Jr.
p. cm.
Includes bibliographical references and index.
1. Computer programming. I. Title.
QA76.6 .W375 2002
005.1—dc21
This document was created by an unregistered ChmMagic, please go to http://www.bisenter.com to register it. Thanks
.
2002066501
Copyright © 2003 by Pearson Education, Inc.
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or
transmitted, in any form, or by any means, electronic, mechanical, photocopying, recording, or
otherwise, without the prior consent of the publisher. Printed in the United States of America.
Published simultaneously in Canada.
For information on obtaining permission for use of material from this work, please submit a written
request to:
Pearson Education, Inc.
Rights and Contracts Department
75 Arlington Street, Suite 300
Boston, MA 02116
Fax: (617) 848-7047
Text printed on recycled paper
1 2 3 4 5 6 7 8 9 10—MA—0605040302
First printing, July 2002
Dedication
To Joseph W. Gauld, my high school algebra teacher, for sparking in me a delight in the simple things
in mathematics.
This document was created by an unregistered ChmMagic, please go to http://www.bisenter.com to register it. Thanks
.
Foreword
When I first got a summer job at MIT's Project MAC almost 30 years ago, I was delighted to be able to
work with the DEC PDP-10 computer, which was more fun to program in assembly language than any
other computer, bar none, because of its rich yet tractable set of instructions for performing bit tests,
bit masking, field manipulation, and operations on integers. Though the PDP-10 has not been
manufactured for quite some years, there remains a thriving cult of enthusiasts who keep old PDP-10
hardware running and who run old PDP-10 software—entire operating systems and their
applications—by using personal computers to simulate the PDP-10 instruction set. They even write
new software; there is now at least one Web site whose pages are served up by a simulated PDP-10.
(Come on, stop laughing—it's no sillier than keeping antique cars running.)
I also enjoyed, in that summer of 1972, reading a brand-new MIT research memo called HAKMEM, a
bizarre and eclectic potpourri of technical trivia.
[1]
The subject matter ranged from electrical circuits to
number theory, but what intrigued me most was its small catalog of ingenious little programming tricks.
Each such gem would typically describe some plausible yet unusual operation on integers or bit
strings (such as counting the 1-bits in a word) that could easily be programmed using either a longish
fixed sequence of machine instructions or a loop, and then show how the same thing might be done
much more cleverly, using just four or three or two carefully chosen instructions whose interactions are
not at all obvious until explained or fathomed. For me, devouring these little programming nuggets was
like eating peanuts, or rather bonbons—I just couldn't stop—and there was a certain richness to them,
a certain intellectual depth, elegance, even poetry.
Why "HAKMEM"? Short for "hacks memo"; one 36-bit PDP-10 word could hold six 6-bit characters, so a
lot of the names PDP-10 hackers worked with were limited to six characters. We were used to glancing at a
six-character abbreviated name and instantly decoding the contractions. So naming the memo "HAKMEM"
made sense at the time—at least to the hackers.
[1]
"Surely," I thought, "there must be more of these," and indeed over the years I collected, and in some
cases discovered, a few more. "There ought to be a book of them."
I was genuinely thrilled when I saw Hank Warren's manuscript. He has systematically collected these
little programming tricks, organized them thematically, and explained them clearly. While some of
them may be described in terms of machine instructions, this is not a book only for assembly language
programmers. The subject matter is basic structural relationships among integers and bit strings in a
computer and efficient techniques for performing useful operations on them.
These techniques are just as useful in the C or Java programming languages as they are in assembly
language.
Many books on algorithms and data structures teach complicated techniques for sorting and
searching, for maintaining hash tables and binary trees, for dealing with records and pointers. They
This document was created by an unregistered ChmMagic, please go to http://www.bisenter.com to register it. Thanks
.
overlook what can be done with very tiny pieces of data—bits and arrays of bits. It is amazing what
can be done with just binary addition and subtraction and maybe some bitwise operations; the fact
that the carry chain allows a single bit to affect all the bits to its left makes addition a peculiarly
powerful data manipulation operation in ways that are not widely appreciated.
Yes, there ought to be a book about these techniques. Now it is in your hands, and it's terrific. If you
write optimizing compilers or high-performance code, you must read this book. You otherwise might
not use this bag of tricks every single day—but if you find yourself stuck in some situation where you
apparently need to loop over the bits in a word, or to perform some operation on integers and it just
seems harder to code than it ought, or you really need the inner loop of some integer or bit-fiddly
computation to run twice as fast, then this is the place to look. Or maybe you'll just find yourself
reading it straight through out of sheer pleasure.
Guy L. Steele, Jr.
Burlington, Massachusetts
April 2002
This document was created by an unregistered ChmMagic, please go to http://www.bisenter.com to register it. Thanks
.
Preface
Caveat Emptor: The cost of software maintenance increases with the square of the programmer's
creativity.
—First Law of Programmer Creativity, Robert D. Bliss, 1992
This is a collection of small programming tricks that I have come across over many years. Most of
them will work only on computers that represent integers in two's-complement form. Although a 32-bit
machine is assumed when the register length is relevant, most of the tricks are easily adapted to
machines with other register sizes.
This book does not deal with large tricks such as sophisticated sorting and compiler optimization
techniques. Rather, it deals with small tricks that usually involve individual computer words or
instructions, such as counting the number of 1-bits in a word. Such tricks often use a mixture of
arithmetic and logical instructions.
It is assumed throughout that integer overflow interrupts have been masked off, so they cannot occur.
C, Fortran, and even Java programs run in this environment, but Pascal and ADA users beware!
The presentation is informal. Proofs are given only when the algorithm is not obvious, and sometimes
not even then. The methods use computer arithmetic, "floor" functions, mixtures of arithmetic and
logical operations, and so on. Proofs in this domain are often difficult and awkward to express.
To reduce typographical errors and oversights, many of the algorithms have been executed. This is
why they are given in a real programming language, even though, like every computer language, it has
some ugly features. C is used for the high-level language because it is widely known, it allows the
straightforward mixture of integer and bit-string operations, and C compilers that produce high-quality
object code are available.
Occasionally, machine language is used. It employs a three-address format, mainly for ease of
readability. The assembly language used is that of a fictitious machine that is representative of today's
RISC computers.
Branch-free code is favored. This is because on many computers, branches slow down instruction
fetching and inhibit executing instructions in parallel. Another problem with branches is that they may
inhibit compiler optimizations such as instruction scheduling, commoning, and register allocation. That
is, the compiler may be more effective at these optimizations with a program that consists of a few
large basic blocks rather than many small ones.
The code sequences also tend to favor small immediate values, comparisons to zero (rather than to
some other number), and instruction-level parallelism. Although much of the code would become more
concise by using table lookups (from memory), this is not often mentioned. This is because loads are

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin