Compute fast log base 2 ceiling

Question

What is a fast way to compute the (long int) ceiling(log_2(i)), where the input and output are 64-bit integers? Solutions for signed or unsigned integers are acceptable. I suspect the best way will be a bit-twiddling method similar to those found here, but rather than attempt my own I would like to use something that is already well tested. A general solution will work for all positive values.

For instance, the values for 2,3,4,5,6,7,8 are 1,2,2,3,3,3,3

Edit: So far the best route seems to be to compute the integer/floor log base 2 (the position of the MSB) using any number of fast existing bithacks, and then to add one if the input is not a power of two. The fast bitwise check for powers of two is (n&(n-1)).

Another method might be to try a binary search on exponents e until 1<<e is greater than or equal to the input.

Answer 1

Finding the log base 2 of an integer (64-bit or any other bit) with integer output is equivalent to finding the most significant bit that is set. Why? Because log base 2 is how many times you can divide the number by 2 to reach 1.

One way to find the MSB that's set is to simply bitshift to the right by 1 each time until you have 0. Another more efficient way is to do some kind of binary search via bitmasks.

The ceil part is easily worked out by checking if any other bits are set other than the MSB.

Answer 2

If you can limit yourself to gcc, there are a set of builtin functions which return the number of leading zero bits and can be used to do what you want with a little work:

int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)

Answer 3

OK, what I'm doing here is called "bit-fiddling." You need to understand how numbers are stored in the memory in order to get what's happening.

The number "300" is stored in the memory as: 100101100

And to get its value, the computer does: 2^0*0 + 2^1*0 + 2^2*1 + 2^3*1 .... + 2^8*1

The result is 8.something, the ceiling of which is 9.

We go backwards from (left to right) to determine the highest power, the value of which + 1 is the ceiling (assuming the rest are not zeros, of course).

The code:

int mathfunc(int64_t x)
{
    if(x < 1)
    {
        printf("Invalid input");
        return -1;
    }

    int64_t mask = 0x4000000000000000;
    for(int i = 63; i >= 0; --i)
    {
        if(mask & x)
            return i;
        mask = mask >> 1;
    }

    return -1;
}

Answer 4

If you have 80-bit or 128-bit floats available, cast to that type and then read off the exponent bits. This link has details (for integers up to 52 bits) and several other methods:

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float

Also, check the ffmpeg source. I know they have a very fast algorithm. Even if it's not directly extensible to larger sizes, you can easily do something like if (x>INT32_MAX) return fastlog2(x>>32)+32; else return fastlog2(x);

Answer 5

If you're compiling for 64-bit processors on Windows, I think this should work. _BitScanReverse64 is an intrinsic function.

#include <intrin.h>
__int64 log2ceil( __int64 x )
{
  unsigned long index;
  if ( !_BitScanReverse64( &index, x ) )
     return -1LL; //dummy return value for x==0

  // add 1 if x is NOT a power of 2 (to do the ceil)
  return index + (n&(n-1)?1:0);
}

For 32-bit, you can emulate _BitScanReverse64, with 1 or 2 calls to _BitScanReverse. Check the upper 32-bits of x, ((long*)&x)[1], then the lower 32-bits if needed, ((long*)&x)[0].

Answer 6

The true fastest solution:

A binary search tree of 63 entries. These are the powers of 2 from 0 to 63. One-time generation function to create the tree. The leafs represent the log base 2 of the powers (basically, the numbers 1-63).

To find the answer, you feed a number into the tree, and navigate to the leaf node greater than the item. If the leaf node is exactly equal, result is the leaf value. Otherwise, result is the leaf value + 1.

Complexity is fixed at O(6).

Answer 7

My apologies for posting this Java code, but I think it translates almost exactly to C. Java doesn't have unsigned types so I just considered positive longs. This is inspired by Computer Guru's answer and the binary search comment in Brian Bondy's answer

public static int log2(long x)
{
    int log2low = 0;
    int log2high = 62;

    if (x <= 0)
    {
        return -1;
    }

    while ((log2high-log2low) > 1)
    {
        /*
         * invariant: 2**log2low <= x <= 2**log2high
         */
        final int log2mid = (log2low + log2high) / 2;
        final long mid = 1L << log2mid;
        if (x > mid)
        {
            log2low = log2mid;
        }
        else if (x < mid)
        {
            log2high = log2mid;
        }
        else // x is a power of 2
        {
            return log2mid;
        }
    }
    return (x == (1<<log2low)) ? log2low : log2high;
}

Note: this can be accelerated by precomputing a table of size 2**k that maps the k high order bits of the argument z to the ceil(log2(z)). In other words, instead of the loop condition (log2high-log2low) > 1 it becomes (log2high-log2low) > k.

Answer 8

#include "stdafx.h"
#include "assert.h"

int getpos(unsigned __int64 value)
{
    if (!value)
    {
      return -1; // no bits set
    }
    int pos = 0;
    if (value & (value - 1ULL))
    {
      pos = 1;
    }
    if (value & 0xFFFFFFFF00000000ULL)
    {
      pos += 32;
      value = value >> 32;
    }
    if (value & 0x00000000FFFF0000ULL)
    {
      pos += 16;
      value = value >> 16;
    }
    if (value & 0x000000000000FF00ULL)
    {
      pos += 8;
      value = value >> 8;
    }
    if (value & 0x00000000000000F0ULL)
    {
      pos += 4;
      value = value >> 4;
    }
    if (value & 0x000000000000000CULL)
    {
      pos += 2;
      value = value >> 2;
    }
    if (value & 0x0000000000000002ULL)
    {
      pos += 1;
      value = value >> 1;
    }
    return pos;
}

int _tmain(int argc, _TCHAR* argv[])
{    
    assert(getpos(0ULL) == -1); // None bits set, return -1.
    assert(getpos(1ULL) == 0);
    assert(getpos(2ULL) == 1);
    assert(getpos(3ULL) == 2);
    assert(getpos(4ULL) == 2);
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos(1ULL << k);
        assert(pos == k);
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) - 1);
        assert(pos == (k < 2 ? k - 1 : k) );
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) | 1);
        assert(pos == (k < 1 ? k : k + 1) );
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) + 1);
        assert(pos == k + 1);
    }
    return 0;
}

Answer 9

You might be able to gain some inspiration from the venerable HAKMEM.

http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item160