Stupid Question

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

snow5379
Posts: 247
Joined: Tue Apr 12, 2011 6:06 pm UTC

Stupid Question

Postby snow5379 » 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!! :(

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Stupid Question

Postby Xanthir » 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).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Sc4Freak
Posts: 673
Joined: Thu Jul 12, 2007 4:50 am UTC
Location: Redmond, Washington

Re: Stupid Question

Postby Sc4Freak » 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.

User avatar
Dropzone
Posts: 405
Joined: Sun Dec 30, 2007 10:12 pm UTC
Location: North Lincs., UK

Re: Stupid Question

Postby Dropzone » 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.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Stupid Question

Postby Jplus » 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;

}
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Sizik
Posts: 1260
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Stupid Question

Postby Sizik » 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. :D
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Stupid Question

Postby Jplus » 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). :P
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Sizik
Posts: 1260
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Stupid Question

Postby Sizik » 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). :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.
Last edited by phlip on Fri Jul 27, 2012 12:00 pm UTC, edited 1 time in total.
Reason: Remove unnecessary jsMath
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
sourmìlk
If I can't complain, can I at least express my fear?
Posts: 6393
Joined: Mon Dec 22, 2008 10:53 pm UTC
Location: permanently in the wrong
Contact:

Re: Stupid Question

Postby sourmìlk » 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).
Terry Pratchett wrote:The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.

User avatar
Sizik
Posts: 1260
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Stupid Question

Postby Sizik » 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.
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Stupid Question

Postby korona » 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.
Last edited by korona on Wed Jul 25, 2012 7:11 pm UTC, edited 1 time in total.

User avatar
Sizik
Posts: 1260
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Stupid Question

Postby Sizik » Wed Jul 25, 2012 7:09 pm UTC

That's -1...
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
sourmìlk
If I can't complain, can I at least express my fear?
Posts: 6393
Joined: Mon Dec 22, 2008 10:53 pm UTC
Location: permanently in the wrong
Contact:

Re: Stupid Question

Postby sourmìlk » 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.
Terry Pratchett wrote:The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.

User avatar
Sizik
Posts: 1260
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Stupid Question

Postby Sizik » 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.
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
Quizatzhaderac
Posts: 1824
Joined: Sun Oct 19, 2008 5:28 pm UTC
Location: Space Florida

Re: Stupid Question

Postby Quizatzhaderac » 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;
}
The thing about recursion problems is that they tend to contain other recursion problems.

User avatar
thoughtfully
Posts: 2253
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN
Contact:

Re: Stupid Question

Postby thoughtfully » 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.
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 10 guests