## Stupid Question

**Moderators:** phlip, Moderators General, Prelates

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

Please help!!

- Xanthir
- My HERO!!!
**Posts:**5400**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 log

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

_{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).

(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

If you really really need speed, consult the manual of bit twiddling hacks.

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

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

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)

coding and xkcd combined

(Julian/Julian's)

### 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:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.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.

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

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)

coding and xkcd combined

(Julian/Julian's)

### 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:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.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.

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

### Re: Stupid Question

Well, since Integer.MIN_VALUE = -2

^{31}, it would be 1000 0000 0000 0000 0000 0000 0000 0000 in binary.she/they

gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.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.

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

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.

### Re: Stupid Question

That's -1...

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

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.

### Re: Stupid Question

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.

- Quizatzhaderac
**Posts:**1783**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.

### Who is online

Users browsing this forum: No registered users and 8 guests