[vtk-developers] Power-of-two

[David Thompson]

Hi David,

> 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.

These are the alternatives I can think of, in order of descending personal preference:

+ IntLog2
+ CeilLog2
+ BoundingLog2
+ NextPowerOfTwo

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

David Thompson
R&D Engineer – Kitware, Inc.
david.thompson at kitware.com
(919)869-8868
Suite G-4
101 E. Weaver St.
Carrboro, NC 27510