## 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

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!!

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

### Re: Stupid Question

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)))

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

### Re: Stupid Question

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.

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

### Re: Stupid Question

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.

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

### Re: Stupid Question

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)

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

### Re: Stupid Question

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

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

### Re: Stupid Question

But it does recurse on the stack.

EDIT: Oh, and consider what happens when n is zero (which always happens after enough recursions).
"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)

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

### Re: Stupid Question

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

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

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.

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

### Re: Stupid Question

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

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.

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

### Re: Stupid Question

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.

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

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.

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

### Re: Stupid Question

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.

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

### Re: Stupid Question

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.

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

### Re: Stupid Question

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.

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 4 guests