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 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
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. :D

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). :P

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). :P


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 = -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
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 = -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
by Sizik
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
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.