How get smallest n, that 2 ^ n >= x for given integer x in O(1)?

Question

How for given unsigned integer x find the smallest n, that 2 ^ n ≥ x in O(1)? in other words I want to find the index of higher set bit in binary format of x (plus 1 if x is not power of 2) in O(1) (not depended on size of integer and size of byte).

Answer 1

If you have no memory constraints, then you can use a lookup table (one entry for each possible value of x) to achieve O(1) time.

If you want a practical solution, most processors will have some kind of "find highest bit set" opcode. On x86, for instance, it's BSR. Most compilers will have a mechanism to write raw assembler.

Answer 2

Ok, since so far nobody has posted a compile-time solution, here's mine. The precondition is that your input value is a compile-time constant. If you have that, it's all done at compile-time.

#include <iostream>
#include <iomanip>

// This should really come from a template meta lib, no need to reinvent it here, 
// but I wanted this to compile as is. 
namespace templ_meta {
    // A run-of-the-mill compile-time if. 
    template<bool Cond, typename T, typename E> struct if_;
    template<           typename T, typename E> struct if_<true , T, E> {typedef T result_t;};
    template<           typename T, typename E> struct if_<false, T, E> {typedef E result_t;};

    // This so we can use a compile-time if tailored for types, rather than integers. 
    template<int I>
    struct int2type {
        static const int result = I;
    };
}

// This does the actual work.
template< int I, unsigned int Idx = 0>
struct index_of_high_bit {
    static const unsigned int result = 
        templ_meta::if_< I==0
           , templ_meta::int2type<Idx>
           , index_of_high_bit<(I>>1),Idx+1> 
        >::result_t::result;
};

// just some testing
namespace {
    template< int I >
    void test() 
    {
        const unsigned int result = index_of_high_bit<I>::result;
        std::cout << std::setfill('0') 
                  << std::hex << std::setw(2) << std::uppercase << I << ": " 
                  << std::dec << std::setw(2) << result  
                  << '\n';
    }
}

int main()
{
    test<0>();
    test<1>();
    test<2>();
    test<3>();
    test<4>();
    test<5>();
    test<7>();
    test<8>();
    test<9>();
    test<14>();
    test<15>();
    test<16>();
    test<42>();
    return 0;
}

'twas fun to do that.

Answer 3

In <cmath> there are logarithm functions that will perform this computation for you.

ceil(log(x) / log(2));

Answer 4

Some math to transform the expression:

 int n = ceil(log(x)/log(2));

This is obviously O(1).

Answer 5

It's a question about finding the highest bit set (as lshtar and Oli Charlesworth pointed out). Bit Twiddling Hacks gives a solution which takes about 7 operations for 32 Bit Integers and about 9 operations for 64 Bit Integers.

Answer 6

You can use precalculated tables.

If your number is in [0,255] interval, simple table look up will work.

If it's bigger, then you may split it by bytes and check them from high to low.

Answer 7

Perhaps this link will help.

Warning : the code is not exactly straightforward and seems rather unmaintainable.

  uint64_t v;          // Input value to find position with rank r.
  unsigned int r;      // Input: bit's desired rank [1-64].
  unsigned int s;      // Output: Resulting position of bit with rank r [1-64]
  uint64_t a, b, c, d; // Intermediate temporaries for bit count.
  unsigned int t;      // Bit count temporary.

  // Do a normal parallel bit count for a 64-bit integer,                     
  // but store all intermediate steps.                                        
  // a = (v & 0x5555...) + ((v >> 1) & 0x5555...);
  a =  v - ((v >> 1) & ~0UL/3);
  // b = (a & 0x3333...) + ((a >> 2) & 0x3333...);
  b = (a & ~0UL/5) + ((a >> 2) & ~0UL/5);
  // c = (b & 0x0f0f...) + ((b >> 4) & 0x0f0f...);
  c = (b + (b >> 4)) & ~0UL/0x11;
  // d = (c & 0x00ff...) + ((c >> 8) & 0x00ff...);
  d = (c + (c >> 8)) & ~0UL/0x101;
  t = (d >> 32) + (d >> 48);
  // Now do branchless select!                                                
  s  = 64;
  // if (r > t) {s -= 32; r -= t;}
  s -= ((t - r) & 256) >> 3; r -= (t & ((t - r) >> 8));
  t  = (d >> (s - 16)) & 0xff;
  // if (r > t) {s -= 16; r -= t;}
  s -= ((t - r) & 256) >> 4; r -= (t & ((t - r) >> 8));
  t  = (c >> (s - 8)) & 0xf;
  // if (r > t) {s -= 8; r -= t;}
  s -= ((t - r) & 256) >> 5; r -= (t & ((t - r) >> 8));
  t  = (b >> (s - 4)) & 0x7;
  // if (r > t) {s -= 4; r -= t;}
  s -= ((t - r) & 256) >> 6; r -= (t & ((t - r) >> 8));
  t  = (a >> (s - 2)) & 0x3;
  // if (r > t) {s -= 2; r -= t;}
  s -= ((t - r) & 256) >> 7; r -= (t & ((t - r) >> 8));
  t  = (v >> (s - 1)) & 0x1;
  // if (r > t) s--;
  s -= ((t - r) & 256) >> 8;
  s = 65 - s;

Answer 8

As has been mentioned, the length of the binary representation of x + 1 is the n you're looking for (unless x is in itself a power of two, meaning 10.....0 in a binary representation). I seriously doubt there exists a true solution in O(1), unless you consider translations to binary representation to be O(1).

Answer 9

For a 32 bit int, the following pseudocode will be O(1).

highestBit(x)
  bit = 1
  highest = 0
  for i 1 to 32
    if x & bit == 1
      highest = i
    bit = bit * 2
  return highest + 1

It doesn't matter how big x is, it always checks all 32 bits. Thus constant time.

If the input can be any integer size, say the input is n digits long. Then any solution reading the input, will read n digits and must be at least O(n). Unless someone comes up solution without reading the input, it is impossible to find a O(1) solution.

Answer 10

After some search in internet I found this 2 versions for 32 bit unsigned integer number. I have tested them and they work. It is clear for me why second one works, but still now I'm thinking about first one...

1.

unsigned int RoundUpToNextPowOf2(unsigned int v)
{
    unsigned int r = 1;
    if (v > 1) 
    {
      float f = (float)v;
      unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) - 0x7f);
      r = t << (t < v);
    }
    return r;
}

2.

unsigned int RoundUpToNextPowOf2(unsigned int v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;
}

edit: First one in clear as well.

Answer 11

An interesting question. What do you mean by not depending on the size of int or the number of bits in a byte? To encounter a different number of bits in a byte, you'll have to use a different machine, with a different set of machine instructions, which may or may not affect the answer.

Anyway, based sort of vaguely on the first solution proposed by Mihran, I get:

int
topBit( unsigned x )
{
    int r = 1;
    if ( x > 1 ) {
        if ( frexp( static_cast<double>( x ), &r ) != 0.5 ) {
            ++ r;
        }
    }
    return r - 1;
}

This works within the constraint that the input value must be exactly representable in a double; if the input is unsigned long long, this might not be the case, and on some of the more exotic platforms, it might not even be the case for unsigned.

The only other constant time (with respect to the number of bits) I can think of is:

int
topBit( unsigned x )
{
    return x == 0 ? 0.0 : ceil( log2( static_cast<double>( x ) ) );
}

, which has the same constraint with regards to x being exactly representable in a double, and may also suffer from rounding errors inherent in the floating point operations (although if log2 is implemented correctly, I don't think that this should be the case). If your compiler doesn't support log2 (a C++11 feature, but also present in C90, so I would expect most compilers to already have implemented it), then of course, log( x ) / log( 2 ) could be used, but I suspect that this will increase the risk of a rounding error resulting in a wrong result.

FWIW, I find the O(1) on the number of bits a bit illogical, for the reasons I specified above: the number of bits is just one of the many "constant factors" which depend on the machine on which you run. Anyway, I came up with the following purely integer solution, which is O(lg 1) for the number of bits, and O(1) for everything else:

template< int k >
struct TopBitImpl
{
    static int const k2 = k / 2;
    static unsigned const m = ~0U << k2;
    int operator()( unsigned x ) const
    {
        unsigned r = ((x & m) != 0) ? k2 : 0;
        return r + TopBitImpl<k2>()(r == 0 ? x : x >> k2);
    }
};

template<>
struct TopBitImpl<1>
{
    int operator()( unsigned x ) const
    {
        return 0;
    }
};

int
topBit( unsigned x )
{
    return TopBitImpl<std::numeric_limits<unsigned>::digits>()(x)
                + (((x & (x - 1)) != 0) ? 1 : 0);
}

A good compiler should be able to inline the recursive calls, resulting in close to optimal code.