Page 1 of 1

### Stupid Question

Posted: Mon Jul 23, 2012 4:07 am UTC
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
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 loga into a logb by just doing loga(x)/loga(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
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
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

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

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
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
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
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
Well, since Integer.MIN_VALUE = -231, 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
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
That's -1...

### Re: Stupid Question

Posted: Wed Jul 25, 2012 10:03 pm UTC
Sizik wrote:Well, since Integer.MIN_VALUE = -231, 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
sourmìlk wrote:
Sizik wrote:Well, since Integer.MIN_VALUE = -231, 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
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
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.