4 * @brief Functions from hackers delight.
6 * Attention! These functions silently assume, that an int is 32 bit wide.
10 #ifndef __FIRM_HACKDEL_H
11 #define __FIRM_HACKDEL_H
15 #define HACKDEL_WORDSIZE 32
18 * Compute the count of set bits in a 32-bit word.
19 * @param x A 32-bit word.
20 * @return The number of bits set in x.
22 static INLINE unsigned popcnt(unsigned x) {
23 x = x - ((x >> 1) & 0x55555555);
24 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
25 x = (x + (x >> 4)) & 0x0f0f0f0f;
32 * Compute the number of leading zeroes in a word.
34 * @return The number of leading (from the most significant bit) zeroes.
36 static INLINE unsigned nlz(unsigned x) {
46 * Compute the number of trailing zeroes in a word.
48 * @return The number of trailing zeroes.
50 #define ntz(x) (HACKDEL_WORDSIZE - nlz(~(x) & ((x) - 1)))
53 * Compute the greatest power of 2 smaller or equal to a value.
54 * This is also known as the binary logarithm.
56 * @return The power of two.
58 #define log2_floor(x) (HACKDEL_WORDSIZE - 1 - nlz(x))
61 * Compute the smallest power of 2 greater or equal to a value.
62 * This is also known as the binary logarithm.
64 * @return The power of two.
66 #define log2_ceil(x) (HACKDEL_WORDSIZE - nlz((x) - 1))
69 * Round up to the next multiple of a power of two.
71 * @param pot A power of two.
72 * @return x rounded up to the next multiple of pot.
74 #define round_up2(x,pot) (((x) + ((pot) - 1)) & (~((pot) - 1)))