Thursday, October 9, 2014

Count the consecutive trailing zero bits on the right linearly

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);
}

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;