Bit Twiddling Hacks.docx

1、Bit Twiddling HacksBit Twiddling HacksBy Sean Eron Andersonseandercs.stanford.edu Individually, the code snippets here are in the public domain (unless otherwise noted) feel free to use them however you please. The aggregate collection and descriptions are 1997-2005 Sean Eron Anderson. The code and

2、descriptions are distributed in the hope that they will be useful, but WITHOUT ANY WARRANTY and without even the implied warranty of merchantability or fitness for a particular purpose. As of May 5, 2005, all the code has been tested thoroughly. Thousands of people have read it. Moreover, Professor

3、Randal Bryant, the Dean of Computer Science at Carnegie Mellon University, has personally tested almost everything with his Uclid code verification system. What he hasnt tested, I have checked against all possible inputs on a 32-bit machine. To the first person to inform me of a legitimate bug in th

4、e code, Ill pay a bounty of US$10 (by check or Paypal). If directed to a charity, Ill pay US$20. Contents About the operation counting methodology Compute the sign of an integer Detect if two integers have opposite signs Compute the integer absolute value (abs) without branching Compute the minimum

5、(min) or maximum (max) of two integers without branching Determining if an integer is a power of 2 Sign extending Sign extending from a constant bit-width Sign extending from a variable bit-width Sign extending from a variable bit-width in 3 operations Conditionally set or clear bits without branchi

6、ng Conditionally negate a value without branching Merge bits from two values according to a mask Counting bits set Counting bits set, naive way Counting bits set by lookup table Counting bits set, Brian Kernighans way Counting bits set in 12, 24, or 32-bit words using 64-bit instructions Counting bi

7、ts set, in parallel Count bits set (rank) from the most-significant bit upto a given position Select the bit position (from the most-significant bit) with the given count (rank) Computing parity (1 if an odd number of bits set, 0 otherwise) Compute parity of a word the naive way Compute parity by lo

8、okup table Compute parity of a byte using 64-bit multiply and modulus division Compute parity of word with a multiply Compute parity in parallel Swapping Values Swapping values with subtraction and addition Swapping values with XOR Swapping individual bits with XOR Reversing bit sequences Reverse bi

9、ts the obvious way Reverse bits in word by lookup table Reverse the bits in a byte with 3 operations (64-bit multiply and modulus division) Reverse the bits in a byte with 4 operations (64-bit multiply, no division) Reverse the bits in a byte with 7 operations (no 64-bit, only 32) Reverse an N-bit q

10、uantity in parallel with 5 * lg(N) operations Modulus division (aka computing remainders) Computing modulus division by 1 s without a division operation (obvious) Computing modulus division by (1 s) - 1 without a division operation Computing modulus division by (1 s) - 1 in parallel without a divisi

11、on operation Finding integer log base 2 of an integer (aka the position of the highest bit set) Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way) Find the integer log base 2 of an integer with an 64-bit IEEE float Find the log base 2 of an integer with a looku

12、p table Find the log base 2 of an N-bit integer in O(lg(N) operations Find the log base 2 of an N-bit integer in O(lg(N) operations with multiply and lookup Find integer log base 10 of an integer Find integer log base 10 of an integer the obvious way Find integer log base 2 of a 32-bit IEEE float Fi

13、nd integer log base 2 of the pow(2, r)-root of a 32-bit IEEE float (for unsigned integer r) Counting consecutive trailing zero bits (or finding bit indices) Count the consecutive zero bits (trailing) on the right linearly Count the consecutive zero bits (trailing) on the right in parallel Count the

14、consecutive zero bits (trailing) on the right by binary search Count the consecutive zero bits (trailing) on the right by casting to a float Count the consecutive zero bits (trailing) on the right with modulus division and lookup Count the consecutive zero bits (trailing) on the right with multiply

15、and lookup Round up to the next highest power of 2 by float casting Round up to the next highest power of 2 Interleaving bits (aka computing Morton Numbers) Interleave bits the obvious way Interleave bits by table lookup Interleave bits with 64-bit multiply Interleave bits by Binary Magic Numbers Te

16、sting for ranges of bytes in a word (and counting occurances found) Determine if a word has a zero byte Determine if a word has a byte equal to n Determine if a word has byte less than n Determine if a word has a byte greater than n Determine if a word has a byte between m and n Compute the lexicogr

17、aphically next bit permutation -About the operation counting methodology When totaling the number of operations for algorithms here, any C operator is counted as one operation. Intermediate assignments, which need not be written to RAM, are not counted. Of course, this operation counting approach on

18、ly serves as an approximation of the actual number of machine instructions and CPU time. All operations are assumed to take the same amount of time, which is not true in reality, but CPUs have been heading increasingly in this direction over time. There are many nuances that determine how fast a sys

19、tem will run a given sample of code, such as cache sizes, memory bandwidths, instruction sets, etc. In the end, benchmarking is the best way to determine whether one method is really faster than another, so consider the techniques below as possibilities to test on your target architecture. -Compute

20、the sign of an integer int v; / we want to find the sign of vint sign; / the result goes here / CHAR_BIT is the number of bits per byte (normally 8).sign = -(v 0); / if v (sizeof(int) * CHAR_BIT - 1);/ or, for one less instruction (but not portable):sign = v (sizeof(int) * CHAR_BIT - 1); The last ex

21、pression above evaluates to sign = v 31 for 32-bit integers. This is one operation faster than the obvious way, sign = -(v (sizeof(int) * CHAR_BIT - 1); / if v (sizeof(int) * CHAR_BIT - 1);/ Or, for more speed but less portability:sign = (v != 0) | (v (sizeof(int) * CHAR_BIT - 1); / -1, 0, or +1/ Or

22、, for portability, brevity, and (perhaps) speed:sign = (v 0) - (v (sizeof(int) * CHAR_BIT - 1); / if v 0 then 0, else 1Caveat: On March 7, 2003, Angus Duggan pointed out that the 1989 ANSI C specification leaves the result of signed right-shift implementation-defined, so on some systems this hack mi

23、ght not work. For greater portability, Toby Speight suggested on September 28, 2005 that CHAR_BIT be used here and throughout rather than assuming bytes were 8 bits long. Angus recommended the more portable versions above, involving casting on March 4, 2006. Rohit Garg suggested the version for non-

24、negative integers on September 12, 2009. -Detect if two integers have opposite signs int x, y; / input values to compare signsbool f = (x y) sizeof(int) * CHAR_BIT - 1;r = (v + mask) mask;Patented variation: r = (v mask) - mask;Some CPUs dont have an integer absolute value instruction (or the compil

25、er fails to use them). On machines where branching is expensive, the above expression can be faster than the obvious approach, r = (v (sizeof(int)*CHAR_BIT-1)*v, because a multiply is not used. Unfortunately, this method has been patented in the USA on June 6, 2000 by Vladimir Yu Volkonsky and assigned to Sun Microsystems. On August 13, 2006, Yuriy Kaminskiy told me that the patent is likely invalid because the method was pub