[vtk-developers] Power-of-two

[David Gobbi]

Computing integer log base 2 is a fairly common operation in VTK,
should I add it to vtkMath?  I wrote a compact and fast algorithm
based on one of the answers to the following stack overflow question:
http://stackoverflow.com/questions/3272424/compute-fast-log-base-2-ceiling

It finds the answer in 6 iterations even for 64-bit inputs.

int vtkMath::HighestSetBit(vtkTypeUInt64 x)
{
  static const vtkTypeUInt64 t[6] = {
    0xffffffff00000000ull,
    0x00000000ffff0000ull,
    0x000000000000ff00ull,
    0x00000000000000f0ull,
    0x000000000000000cull,
    0x0000000000000002ull
  };

  // return -1 if x == 0
  int y = -1;

  if (x)
    {
    int j = 32;
    y = (((x & (x - 1)) == 0) ? 0 : 1);

    for (int i = 0; i < 6; i++)
      {
      int k = (((x & t[i]) == 0) ? 0 : j);
      y += k;
      x >>= k;
      j >>= 1;
      }
    }

  return y;
}