CODEWITHSUNDEEP
algorithmmathbitwise-operators
Hannesh
Hannesh

Reputation: 7488

The opposite of 2 ^ n

The function a = 2 ^ b can quickly be calculated for any b by doing a = 1 << b. What about the other way round, getting the value of b for any given a? It should be relatively fast, so logs are out of the question. Anything that's not O(1) is also bad.

I'd be happy with can't be done too if its simply not possible to do without logs or a search type thing.

Upvotes: 6

Views: 2257

Answers (7)

starblue
starblue

Reputation: 56772

In Java you can use Integer.numberOfLeadingZeros to compute the binary logarithm. It returns the number of leading zeros in the binary representation, so

  • floor(log2(x)) = 31 - numberOfLeadingZeros(x)
  • ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)

Upvotes: 1

Margus
Margus

Reputation: 20048

Or you can write:

while ((a >>= 1) > 0) b++;

This is O(1). One could imagine this to be expanded to:

b = (((a >> 1) > 0) ? 1 : 0) + (((a >> 2) > 0) ? 1 : 0) + ... + (((a >> 31) > 0) ? 1 : 0);

With a complier optimization, that once (a >> x) > 0) returns false, rest won't be calculated. Also comparing with 0 is faster then any other comparison. Also: alt text, where k is maximum of 32 and g is 1.

Reference: Big O notation

But in case you where using BigInteger, then my code example would look like:

    int b = 0;
    String numberS = "306180206916083902309240650087602475282639486413"
            + "866622577088471913520022894784390350900738050555138105"
            + "234536857820245071373614031482942161565170086143298589"
            + "738273508330367307539078392896587187265470464";
    BigInteger a = new BigInteger(numberS);

    while ((a = a.shiftRight(1)).compareTo(BigInteger.ZERO) > 0) b++;

    System.out.println("b is: " + b);

Upvotes: 2

CashCow
CashCow

Reputation: 31445

If a is a double rather than an int then it will be represented as mantissa and exponent. The exponent is the part you are looking for, as this is the logarithm of the number.

If you can hack the binary representation then you can get the exponent out. Look up the IEEE standard to see where and how the exponent is stored.

For an integral value, if some method of getting the most significant bit position is not available then you can binary-search the bits for the upper-most 1 which is therefore O(log numbits). Doing this may well actually perform faster than converting to a double first.

Upvotes: 1

Graham Borland
Graham Borland

Reputation: 60681

Some architectures have a "count leading zeros" instruction. For example, on ARM:

MOV R0,#0x80      @ load R0 with (binary) 10000000
CLZ R1,R0         @ R1 = number of leading zeros in R0, i.e. 7

This is O(1).

Upvotes: 2

kennytm
kennytm

Reputation: 523334

Build a look-up table. For 32-bit integers, there are only 32 entries so it is O(1).

Most architectures also have an instruction to find the position of the most significant bit of a number a, which is the value b. (gcc provides the __builtin_clz function for this.)

For a BigInt, it can be computed in O(log a) by repeatedly dividing by 2.

int b = -1;
while (a != 0) {
  a >>= 1;
  ++ b;
}

Upvotes: 13

Mark Byers
Mark Byers

Reputation: 838296

For this sort of thing I usually refer to this page with bit hacks:

For example:

Find the log base 2 of an integer with a lookup table:

static const char LogTable256[256] = 
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
  r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else 
{
  r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

There are also a couple of O(log(n)) algorithms given on that page.

Upvotes: 7

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 798706

It can't be done without testing the high bit, but most modern FPUs support log2 so all is not lost.

Upvotes: 0

Related Questions