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: C

## About this entry

You’re currently reading “

- Published:
- 9:13 PM
- by Anoob Backer

## 0 Comments (Post a Comment)