unsigned int v; // input to count trailing zero bits int c; // output: c will count v's trailing zero bits, // so if v is 1101000 (base 2), then c will be 3 if (v) { v = (v ^ (v - 1)) >> 1; // Set v's trailing 0s to 1s and zero rest for (c = 0; v; c++) { v >>= 1; } } else { c = CHAR_BIT * sizeof(v); }
Thursday, October 9, 2014
Count the consecutive trailing zero bits on the right linearly
Round up to the next highest power of 2
unsigned int x; // calculate the next highest power of 2 of 32-bit x x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x++;
Round up to the next highest power of 2 by float casting:
This operation is 3 times slower than above operation.
unsigned int const v; // Round this 32-bit value to the next highest power of 2 unsigned int r; // result here. (So v=3 -> r=4; v=8 -> r=8) if (v > 1) { float f = (float)v; unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) - 0x7f); r = t << (t < v); } else { r = 1; }
Wednesday, October 8, 2014
Compute the integer absolute value without branching operation
int input_value; // Find the absolute value of input_value
unsigned int abs_value; // the result value
#define CHAR_BIT 8
int const mask = input_value >> sizeof(int) * CHAR_BIT - 1;
abs_value = (input_value + mask) ^ mask;
unsigned int abs_value; // the result value
#define CHAR_BIT 8
int const mask = input_value >> sizeof(int) * CHAR_BIT - 1;
abs_value = (input_value + mask) ^ mask;
Subscribe to:
Posts (Atom)