C Programming - Bit Twiddling Hack

Some Bit Twiddling code snippets!!


Bit Twiddling Hacks

Contents:

# 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
* 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 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 Kernighan's way
* Counting bits set in 12, 24, or 32-bit words using 64-bit instructions
* Counting bits set, in parallel

# Computing parity (1 if an odd number of bits set, 0 otherwise)
* Compute parity of a word the naive way
* Compute parity by lookup table
* Compute parity of a byte using 64-bit multiply and modulus division
* Compute parity in parallel

# Swapping Values
* Swapping values with XOR
* Swapping individual bits with XOR

# 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)

* 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 division 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 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)

* Interleave bits the obvious way
* Interleave bits by table lookup
* Interleave bits with 64-bit multiply
* Interleave bits by Binary Magic Numbers

# Testing for ranges of bytes in a word (and counting occurances found)

* Determine if a word has a zero byte
* 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


Bit Twiddling Hacks

Labels:

About this entry

You’re currently reading “C Programming - Bit Twiddling Hack,” an entry on ANOOB BACKER Technical Blog

Published:
9:13 pm
by -