Page **1** of **1**

### Stupid Question

Posted: **Mon Jul 23, 2012 4:07 am UTC**

by **snow5379**

In Java what's the best way to change 1 to 0, 2 to 1, 4 to 2, 8 to 3, 16 to 4, 32 to 5, and so on? Basically I'm trying to make a function where function(2^n)=n. I think this is called a binary logarithm but I'm not sure. I'm going to be calling this function a lot and only passing it powers of 2 so I'm hoping to have a very clean simple function but I can't think of one that doesn't use a loop.

Please help!!

### Re: Stupid Question

Posted: **Mon Jul 23, 2012 4:15 am UTC**

by **Xanthir**

The Math.log function does a natural logarithm (that is, base e). You want base 2. If you remember your basic rules of logarithms, you can turn a log_{a} into a log_{b} by just doing log_{a}(x)/log_{a}(b).

In other words, function binlog(n) = Math.log(n) / Math.log(2).

### Re: Stupid Question

Posted: **Mon Jul 23, 2012 4:48 am UTC**

by **Sc4Freak**

If you know in advance the number is a power of two, I'd usually just write a loop. But that's just because I tend not to like floats for integer operations.

If you really really need speed, consult the

manual of bit twiddling hacks.

### Re: Stupid Question

Posted: **Mon Jul 23, 2012 11:02 pm UTC**

by **Dropzone**

I'd go for

int log2(int n) { return 31 - Integer.numberOfLeadingZeros(n); }. It's simple, and

PrintAssembly shows that the JIT is smart enough to compile it into a

bsr instruction, so it's probably the fastest implementation.

...actually, if I'm reading it correctly, the JIT compiles it to (pseudocode)

31 - (31 - bsr(n)). I'm not sure how it manages to miss the obvious optimization opportunity there.

### Re: Stupid Question

Posted: **Wed Jul 25, 2012 4:12 pm UTC**

by **Jplus**

Code: Select all

`int _log2_floor (int32_t x) {`

int log = 0;

if (x & 0xffff0000) { x &= 0xffff0000; log += 16; }

if (x & 0xff00ff00) { x &= 0xff00ff00; log += 8; }

if (x & 0xf0f0f0f0) { x &= 0xf0f0f0f0; log += 4; }

if (x & 0xcccccccc) { x &= 0xcccccccc; log += 2; }

if (x & 0xaaaaaaaa) { x &= 0xaaaaaaaa; log += 1; }

return log;

}

### Re: Stupid Question

Posted: **Wed Jul 25, 2012 4:58 pm UTC**

by **Sizik**

Code: Select all

`int log2floor(int n) `

{

if(n == 1)

return 0;

else

return 1 + log2floor(n/2);

// Alternatively:

// return n == 1 ? 0 : 1 + log2floor(n/2);

}

Doesn't loop.

### Re: Stupid Question

Posted: **Wed Jul 25, 2012 5:07 pm UTC**

by **Jplus**

But it does recurse on the stack.

EDIT: Oh, and consider what happens when n is zero (which always happens after enough recursions).

### Re: Stupid Question

Posted: **Wed Jul 25, 2012 5:22 pm UTC**

by **Sizik**

Jplus wrote:EDIT: Oh, and consider what happens when n is zero (which always happens after enough recursions).

Then it looks like I will get a sign error, as it would compute ∞ instead of −∞ (after infinite time of course).

Edit: that's assuming infinite-length integers, which ints are not.

I suppose you could insert

Code: Select all

`else if(n < 1)`

return java.lang.Integer.MIN_VALUE

to stand for negative infinity.

### Re: Stupid Question

Posted: **Wed Jul 25, 2012 6:09 pm UTC**

by **sourmìlk**

Sizik wrote:Edit: that's assuming infinite-length integers, which ints are not.

I suppose you could insert

Code: Select all

`else if(n < 1)`

return java.lang.Integer.MIN_VALUE

to stand for negative infinity.

What's the binary for Integer.MIN_VALUE (I don't think you have to specify java.lang which is implicitly included, though it could be that my IDE always did an import java.lang that I never noticed).

### Re: Stupid Question

Posted: **Wed Jul 25, 2012 6:52 pm UTC**

by **Sizik**

Well, since Integer.MIN_VALUE = -2^{31}, it would be 1000 0000 0000 0000 0000 0000 0000 0000 in binary.

### Re: Stupid Question

Posted: **Wed Jul 25, 2012 7:01 pm UTC**

by **korona**

No, it is 0xFFFFFFFF i.e. 1111 1111 1111 1111 1111 1111 1111 1111.

EDIT: Yes, you're right, I don't know what I was thinking.

### Re: Stupid Question

Posted: **Wed Jul 25, 2012 7:09 pm UTC**

by **Sizik**

That's -1...

### Re: Stupid Question

Posted: **Wed Jul 25, 2012 10:03 pm UTC**

by **sourmìlk**

Sizik wrote:Well, since Integer.MIN_VALUE = -2^{31}, it would be 1000 0000 0000 0000 0000 0000 0000 0000 in binary.

Oh. I would have thought it would have been this, but you threw me off when you referred to it as negative infinity and not -1 * 2 ^ 31.

### Re: Stupid Question

Posted: **Thu Jul 26, 2012 1:58 pm UTC**

by **Sizik**

sourmìlk wrote:Sizik wrote:Well, since Integer.MIN_VALUE = -2^{31}, it would be 1000 0000 0000 0000 0000 0000 0000 0000 in binary.

Oh. I would have thought it would have been this, but you threw me off when you referred to it as negative infinity and not -1 * 2 ^ 31.

I said that it would stand for negative infinity (since it's the lowest negative number a 32-bit signed integer can hold), not that it IS negative infinity.

### Re: Stupid Question

Posted: **Mon Aug 27, 2012 9:40 pm UTC**

by **Quizatzhaderac**

Integer.numberOfTrailingZeros(int i) should be sufficient (if you're sure the number is a power of 2) and probably the quickest. If you're not sure what's coming in:

Code: Select all

`public byte binaryLog(long operand) {`

if (operand < 1) throw new IllegalArgumentException("operand is not a power of 2: "+operand);

byte result;

for(result =0;operand != 1;result++) {

operand = operand >> 1;

}

return result;

}

### Re: Stupid Question

Posted: **Mon Aug 27, 2012 10:59 pm UTC**

by **thoughtfully**

You can get the whole number part of the logarithm by just shifting off bits until zero. This is just counting binary digits, and you can count octal, hex, etc digits by shifting off the corresponding number of bits at each iteration.