Format: PDF / Kindle (mobi) / ePub
A collection useful programming advice the author has collected over the years; small algorithms that make the programmer's task easier. * At long last, proven short-cuts to mastering difficult aspects of computer programming * Learn to program at a more advanced level than is generally taught in schools and training courses, and much more advanced than can be learned through individual study/experience. * An instant cult classic for programmers! Computer programmers are often referred to as hackers -- solitary problem solvers engrossed in a world of code as they seek elegant solutions to building better software. While many view these unique individuals as "madmen," the truth is that much of the computer programmer's job involves a healthy mix of arithmetic and logic. In Hacker's Delight, veteran programmer Hank Warren shares the collected wisdom -- namely tips and tricks -- from his considerable experience in the world of application development. The resulting work is an irresistible collection that will help even the most seasoned programmers better their craft. Henry S. Warren Jr. has had a 40-year career with IBM, spanning the computer field from the IBM 704 to PowerPC. He has worked on various military command and control systems, and on the SETL project under Jack Schwartz at NYU. Since 1973 he has been in IBM's Research Division at Yorktown Heights, New York. Here he has done compiler and computer architecture work on the 801 computer and its several variants through PowerPC. Presently he is working on the Blue Gene petaflop computer project. He received his Ph.D. in Computer Science from the Courant Institute at New York University in 1980.
this bit off, the remainder of the division will be an even number. Hence for an even divisor d, the remainder is at most d – 2. This slight change in the maximum possible remainder results in the maximum multiplier m being a W-bit number rather than a (W + 1)-bit number (and hence the shrxi instruction is not needed), as we will now see. In fact, we will investigate what simplifications occur if the divisor ends in z 0-bits, that is, if it is a multiple of 2z, for z ≥ 0. In this case, the z
integers, and let us take “overflow” to mean that the result does not fit in a word with the operands and result interpreted as signed two’s-complement integers. Then again, there are nine possible combinations of results, with the missing ones being “no carry, overflow, result > 0,” “no carry, overflow, result = 0,” and “carry, no overflow, result = 0.” Thus, considering addition, subtraction, and multiplication together, ten combinations can occur. 2–15 Rotate Shifts These are rather
1992 has a three-input adder and can execute two consecutive add-type instructions in parallel even when one feeds the other (e.g., an add feeding a compare, or the base register of a load). As a contrary example, consider a simple computer, possibly for low-cost embedded applications, that has only one read port on its register file. Normally, this machine would take an extra cycle to do a second read of the register file for an instruction that has two register input operands. However, suppose
members of a set are listed in a linear array, and a subset is represented by a word or sequence of words in which bit i is on if member i is in the subset. Set unions are computed by the logical or of the bit strings, intersections by and’s, and so on. You might want to iterate through all the subsets of a given size. This is easily done if you have a function that maps a given subset to the next higher number (interpreting the subset string as an integer) with the same number of 1-bits. A
instruction) after a fairly short calculation. We will make frequent use of the following elementary property of congruences: THEOREM C. If a ≡ b (mod m) and c ≡ d (mod m), then The unsigned case is simpler and is dealt with first. Unsigned Remainder For a divisor of 3, multiplying the trivial congruence 1 ≡ 1 (mod 3) repeatedly by the congruence 2 ≡ –1 (mod 3), we conclude by Theorem C that Therefore, a number n written in binary as ...b3 b2 b1 b0 satisfies n = ... + b3 · 23 + b2 · 22