[vtk-developers] Power-of-two

[David Thompson]

Hi David,

I think it would be a good addition to vtkMath. You can sign me up to review a Gerrit topic.

	David

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