[vtk-developers] [EXTERNAL] Re: Power-of-two

[Scott, W Alan]

Fptw?  Fastest Power of Two in the West?  (Remembering the FFTW code (Fastest Fourier Transform in the West))

Alan

-----Original Message-----
From: vtk-developers-bounces at vtk.org [mailto:vtk-developers-bounces at vtk.org] On Behalf Of David Gobbi
Sent: Friday, March 08, 2013 11:55 AM
To: David Thompson
Cc: VTK Developers
Subject: [EXTERNAL] Re: [vtk-developers] Power-of-two

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-ce
>> iling
>>
>> 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;
>> }
>
_______________________________________________
Powered by www.kitware.com

Visit other Kitware open-source projects at http://www.kitware.com/opensource/opensource.html

Follow this link to subscribe/unsubscribe:
http://www.vtk.org/mailman/listinfo/vtk-developers