[vtk-developers] Power-of-two

[David Gobbi]

Do you have ideas for what it should be called?  It isn't quite
log2(x), because, unlike most integer math operations, it rounds up
instead of truncating.

 - David


On Fri, Mar 8, 2013 at 11:44 AM, David Thompson
<david.thompson at kitware.com> wrote:
> 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;
>> }
>