CODEWITHSUNDEEP
c++int
johndoe
johndoe

Reputation: 303

Determining Exponent of Power of Two Integer?

Is there any way other than log_2(x) for determining which power an integer is ? Knowing of course that it is a power of two, (binary base 0001, 0010, 0100, 1000, etc...).
Mostly I don't want it to convert to a floating point number and I don't want it to simple use an array search.

Upvotes: 0

Views: 335

Answers (3)

πάντα ῥεῖ
πάντα ῥεῖ

Reputation: 1

You can use a bit comparison test based on iterating with a bit shift operation:

unsigned int power_of_2(unsigned int x) {
    // Note that *8 hardcoded isn't ideal here. There's a constant available that
    // specifies the 'byte' size (bitwise) for the actual architecture. 
    // But this is really depending on your C or C++ compiler.
    for(size_t p2 = 0; p2 < sizeof(x)*8; ++p2) { 
        if(x & (1 << p2)) {
            return p2;
        }
    }
    return 0;
}

The following calls give you the output shown below:

int main() {
    std::cout << power_of_2(0x0080) << " "
              << power_of_2(0x0040) << " "
              << power_of_2(0x0020) << " "
              << power_of_2(0x0010) << " "
              << std::endl;
    return 0;
}

Output:

7 6 5 4

Check a live sample here please.

Upvotes: 0

BonzaiThePenguin
BonzaiThePenguin

Reputation: 1433

What you want to do is count the trailing zeroes of a number, although counting the leading zeroes and subtracting from 32 or 64 can work just as well when the number is a power of two. Bit Twiddling Hacks provides many ways to do this.

Count the consecutive zero bits (trailing) on the right linearly

unsigned int v;  // input to count trailing zero bits
int c;  // output: c will count v's trailing zero bits,
        // so if v is 1101000 (base 2), then c will be 3
if (v)
{
  v = (v ^ (v - 1)) >> 1;  // Set v's trailing 0s to 1s and zero rest
  for (c = 0; v; c++)
  {
    v >>= 1;
  }
}
else
{
  c = CHAR_BIT * sizeof(v);
}

Count the consecutive zero bits (trailing) on the right in parallel

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

Count the consecutive zero bits (trailing) on the right by binary search

unsigned int v;     // 32-bit word input to count zero bits on right
unsigned int c;     // c will be the number of zero bits on the right,
                    // so if v is 1101000 (base 2), then c will be 3
// NOTE: if 0 == v, then c = 31.
if (v & 0x1) 
{
  // special case for odd v (assumed to happen half of the time)
  c = 0;
}
else
{
  c = 1;
  if ((v & 0xffff) == 0) 
  {  
    v >>= 16;  
    c += 16;
  }
  if ((v & 0xff) == 0) 
  {  
    v >>= 8;  
    c += 8;
  }
  if ((v & 0xf) == 0) 
  {  
    v >>= 4;
    c += 4;
  }
  if ((v & 0x3) == 0) 
  {  
    v >>= 2;
    c += 2;
  }
  c -= v & 0x1;
}

And three more examples which use floats and array lookups, which you've specified you do not want to use.

Upvotes: 2

Utkan Gezer
Utkan Gezer

Reputation: 3069

Several ways to do it. One on top of my head, you can divide it by 2, until it is 1:

int logbase2( unsigned int n ) {
    int exp = 0;
    if ( n == 0 )
        return -1;
    while ( n != 1 ) {
        n /= 2;
        exp++;
    }
    return exp;
}

And logbase2( yournumber ); shall yield the result you want. More generally, it shall yield the integer part of the actual logarithm on base 2 of the number yournumber.

Upvotes: 1

Related Questions