22
Dec
Bit Twiddling/Manipulation Hacks
Related Blog Items
- C++ Basics Tutorial - Lesson 2
- Reference Counting
- C++ Basics Tutorial - Lesson 11
- C++ Basics Tutorial - Lesson 4
- C++ Basics Tutorial - Lesson 6
Contents
- About the operation counting methodology
- Compute the sign of an integer
- Compute the integer absolute value (abs) without branching
- Compute the minimum (min) or maximum (max) of two integers without branching
- Determining if an integer is a power of 2
- Sign extending
- Conditionally set or clear bits without branching
- Merge bits from two values according to a mask
- Counting bits set
- Computing parity (1 if an odd number of bits set, 0 otherwise)
- Swapping Values
- Reversing bit sequences
- Reverse bits the obvious way
- Reverse bits in word by lookup table
- Reverse the bits in a byte with 3 operations (64-bit muliply 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 quantity in parallel with 5 * lg(N) operations
- Modulus division (aka computing remainders)
- 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 lookup 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 2 of a 32-bit IEEE float
- Find 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 in parallel
- Count the 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 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)
- Testing for ranges of bytes in a word (and counting occurances found)
[tags]bit manipulation,byte manipulation, bit manipulation source code, bit manipulation programs[/tags]
Popularity: 11%
You need to log on to convert this article into PDF
Related Blog Items - C++ Basics Tutorial - Lesson 2
- Reference Counting
- C++ Basics Tutorial - Lesson 11
- C++ Basics Tutorial - Lesson 4
- C++ Basics Tutorial - Lesson 6
Related Blog Items
- C++ Basics Tutorial - Lesson 2
- Reference Counting
- C++ Basics Tutorial - Lesson 11
- C++ Basics Tutorial - Lesson 4
- C++ Basics Tutorial - Lesson 6
No Comments
No comments yet.