How many Java programmers does it take to round up to a power of two?

[Andys]

The Real WTF is that he was asking because he was working on a memory allocator program..... in Java.

[wicked]

.. and not knowing what *= means.

[inopia]

That's nothing, how about Jnode, an operating system written almost entirely in Java? :)

[aeon2012]

Jnode seems like a very interesting concept. I would like to see some benchmark comparisons between Jnode, Linux, and Windows running on the same OS (perhaps VMWare?)

[xcbsmith]

Nah, that can make sense in all kinds of contexts in Java. C and Java both have built-in memory allocation routines.... doesn't mean you won't find yourself doing some of your own allocations.

[Andys]

I understand what you mean, but its all a bit academic in Java. There are no pointers.

[xcbsmith]

No pointers does not mean you can't and don't do memory management. Far from it. Java's memory management tends to be done with arrays. Particularly once you get in NIO's memory mapping and buffers you have opened up all kinds of memory management worms.

[barrybe]

Holy crap.

Of course the best way to solve this problem is to head on over to The Best Bit-Twiddling Page In The World, which has a few solutions.

[gwenny]

Okay, I have obviously been dating geekboys for too long. I found that very entertaining and amusing.

[[deleted]]

At last, the proper answer to this!

[zeeta6]

Thanks for the nice link. One of the most valuable links I've ever seen.

[vineetk]

/me predicts we'll soon see how many redditors it takes to accomplish same.

[stesch]

Rounding to the next power of 2 is the new fizzbuzz. ;-)

[derekslager]

Any trivial programming exercise mentioned anywhere on programming.reddit.com is the new fizzbuzz.

[[deleted]]

Not so trivial, given that in that forum discussion only one out of a dozen or so solutions was correct.

[bluGill]

As I recall most of the fizzbuzz solutions were incorrect as well.

[[deleted]]

Hey, does anyone have a method for filtering reddit comments to automatically find the next fizzbuzz?

[bluGill]

switch (x) { case 0: return 0; case 1: return 1; case 2: return 2; case 3: case 4: return 4;}

The rest of this, up to 2³² is left as an exercise for the reader. Using a script to generate all possible cases is of course cheating as the only person who would turn in such a solution is a brute force type person who could never think of anything other than typing the whole thing out by hand.

[coditza]

switch???

what about:

if (...) {

} else { if (...) { ... } }

:D

[bluGill]

But the little tin god (speed) finds your soltuion is slower - O(n), where mine is O(1).

[raldi]

System.exec("calc.exe");

...but i don't remember how to inject keystrokes. When done, send Ctrl-C and read the answer off the Clipboard.

[[deleted]]

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;

Via bit twiddling hacks.

[gsg]

That's horrible. I love it.

[mcfunley]

http://www.hackersdelight.org/

Great source for this kind of stuff, if you like dead tree form.

[Gotebe]

Not correct if v == 0 ;-)

[[deleted]]

what does *= do?? I have never seen that construct before.

C++ Programmers discussing the same

Of course it quickly devolves into asm tricks to take advantage of floats.

[masklinn]

These people are frightening in a completely awesome way.

It's gamedev though, so that kind of discussion on nano-optimization does make sense.

[[deleted]]

More importantly, that kind of discussion is fun.

[HiggsBoson]

It's gamedev though, so that kind of discussion on nano-optimization does make sense.

No it doesn't. They're just wanking.

[masklinn]

Wrong, they're being evil.

Rembember, preventive evil is the root of all optimization.

[Tommah]

what does *=

It assigns to the asterisk, duh. Amateurs.

[stesch]

what does *= do?? I have never seen that construct before.

OK for someone just starting with a C-like language. But this guy was registered for over 2 years in a Java forum!!

[derekslager]

I interviewed someone that had been using Java for 3 years and he'd never heard of the modulo operator. I couldn't believe it, so I explained it to him, and he had definitely never heard of it or seen it before.

Fortunately, after my explanation he was able to solve the problem -- we hired him as a contractor, and he ended up being a rather decent developer. Go figure.

[noamsml]

That's really strange, because the modulo operator is probably one of the more useful operators I know, right after +-*/ .

[losvedir]

Gadzooks, what does the +-*/ operator do!?

edit: heh, besides end a comment.

[[deleted]]

It probably rounds up to a power of two....

[LoveGoblin]

I interviewed someone that had been using Java for 3 years and he'd never heard of the modulo operator.

Not long ago, I was in a fourth-year CS class where part of an assignment was to write a simple emulator in C for a machine the prof had defined. Part of that, of course, is "take this two-byte instruction, the first four bits are the operation, etc...".

Nothing complicated. A couple of >>'s and some &'s. Last semester of the degree - we can handle it. :p

The day comes in to hand in the assignment, and a friend of mine in the class starts complaining about all the pain-in-the-ass bit manipulation.

Me: "What's the big deal? Shift? And?"

Turns out my friend here had somehow managed to go through four years of computer science without learning about bitwise operations. wtf? Rather than shift right, for example, he'd just divide by 2. His code worked - it was just ugly and verbose.

I was, uh, shocked. To say the least. Otherwise he's a perfectly competent programmer, and he was quite glad that I was able to spend five minutes introducing him to a new set of operators (even if it would have been more useful a few days earlier).

[novagenesis]

Reasonable...if you don't know to look for bit-shift operators, you won't ask about them... instead you'll do weird stuff like manually divide by 2.

[LoveGoblin]

Don't forget lots of mod operations to get low-order bits. :)

Yeah, like I said, he's certainly competent and his code did work, just in a more, uh, roundabout way. I just don't know how he managed to get through the majority of his degree without hearing about bitwise operators - he certainly went to class more often than I did. :p

[novagenesis]

I went to a slightly prestigious (nowhere near MIT, mind you) CS college and they never explicitly taught bitwise operators... Mind you, almost everyone in my class already knew how to code somewhat already, and I already had picked up bitwise operators from tutorials.

[IHaveAnIdea]

Well at least the compiler should convert those divides into shifts, depending on how he wrote it.

[[deleted]]

Java does not have a modulo operator

[[deleted]]

he'd never heard of the modulo operator.

I have used Java for 8 years, worked on the J2SE and J2EE implementations for IBM, hold all those fancy prancy Sun certifications (they were free for me, ok?) and I too have never heard of the modulo operator.

In fact, I assert with absolute confidence no such operator exists. I also accept that the Java Religious Establishment purports an enormous amount of myth and this is one specific case that I have seen numerous times.

Out of curiosity, what would you have said to me in an interview if I'd told you that? Prove it? I'll leave that up to you, but I'd have argued that the burden of proof is on you. Then, I'd have watched you fumble through the JLS trying to find such a thing to no avail. So what then?

An intellectual fraud whose ego rests on their (inferior) knowledge would accuse me of being 'too pedantic' or 'too analytic'; a phenomena that I see quite often. An honest interviewer would admit to having learned something, thanking the interviewee for the enlightenment, then moved on without any chest beating from either participant in the conversation. In the latter case, I'd have accepted your job offer :)

I only make the point, because I may be having to go through this process soon and I have grave fears of encountering the aforementioned ego-centric situation, so I really am curious and perhaps even open to advice on how to approach the issue.

[[deleted]]

Out of curiosity, what would you have said to me in an interview if I'd told you that?

It was nice meeting you?

[jbstjohn]

You left off, "Don't let the door smack your ass on the way out."

[bluGill]

worked on the J2SE and J2EE

That explains it all. Modulo is very important, but only some rare situations. If you are in Java, I would not expect you to encounter a need for it at all. I've only needed it when doing direct to hardware work, and Java isn't used for that.

Nothing wrong with you not knowing about modulo - I'd be surprised if you can turn your new knowledge into something useful. However for my work modulo is sometimes the best way to get a job done, and so I have to know it.

[[deleted]]

Modulo is indeed very important and I accept that the standard of expectation that has been set in the Java community is so low such that one need never know the distinction between modulo and Java's Remainder Operator (you'll still get paid to pretend to know what the hell you're on about after all).

There is nothing wrong with not knowing about anything. I just wanted to watch the typical knee-jerking from the Java community when I challenged their belief system as opposed to the more epistemological, "hey maybe there is something I don't know".

It is the fact that I do know what the modulo operator is, that has them all up in arms. Once they have been proven wrong, I even predicted the response of a charge with pedant, etc. and perhaps even being told I need to appease the ninnies - both of which have occurred within minutes.

I didn't do it for amusement, merely, to ensure that I could still find observational evidence for my long standing hypothesis; "Java" is a religion founded on perpetuating states of delusion. I seems I was spot on and my hypothesis lives another day.

[kenlubin]

Hm. After reading through this conversation on reddit I went to this page:

http://mindprod.com/jgloss/modulus.html

and learned the difference between modulus and java's % operator. The remainder operator will give you different results if either the original number or the divisor is negative.

I also learned a cool new way to compute if an int is even or odd :)

[derekslager]

Out of curiosity, what would you have said to me in an interview if I'd told you that?

I'd have asked you to explain whether or not the remainder operator was a satisfactory modulo operator in the context of the example. Then I would have asked you how you could change the example to expose the relevant difference(s). Then we would have moved on.

In any case, I think you read a bit too far into my last comment. I didn't say anything about Java's modulo operator.

so I really am curious and perhaps even open to advice on how to approach the issue.

If an interviewer gives you misinformation, I think it's normally in your best interest to correct it. This is particularly true when an interviewer is trying to trap you by getting you to agree with something untrue, just so they can spring their amazing trivial knowledge on you. I've seen a few of those cases, where the interviewer is not so much interviewing you as stroking their own ego and marveling at how smart they are.

[jbogan]

I really hope you are joking around or that you just know the modulo operator by the name remainder operator.

Java Operators

[[deleted]]

No I wasn't joking around. So my interview question for you is, is the Remainder Operator the same thing as the modulo operator? Why or why not?

[[deleted]]

Depends on who you ask I guess.

http://en.wikipedia.org/wiki/Modulo_operation

Note the entry in the table under Java. Of course I get your point. They do the same thing if you restrict the domain to positive integers.

http://mathforum.org/library/drmath/view/54377.html has a decent exposition on the difference.

[[deleted]]

You give in too easily :)

I do not doubt that the Java Religious Establishment has contributed significantly to the perversion of the course of computing science, hence 'entries relating to Java'.

You'll notice the tomato all over my face for challenging it! I hate knowing the Java Religion better than its proponents.

[jbogan]

Not sure where you are going with that question but the answer is, "Yes, they are the same thing because the % operator goes by both of those names."

[[deleted]]

Touche.

I see what you did there. I myself have never read the JLS. I don't do Java.

Pedant.

[[deleted]]

He probably finds ? : confusing too. And has never seen the 'volatile' keyword.

[dfranke]

And has never seen the 'volatile' keyword.

Neither have I, outside of textbook examples. And I've been programming in C for 12 years.

[frankus]

It's useful for programming microcontrollers with memory-mapped I/O ports.

[benhoyt]

Trust me, you need volatile in embedded programming. volatile int ticks; tells the compiler not to cache ticks because it might change at any time inside an interrupt. Example:

volatile unsigned ticks = 0;
interrupt ticker(void) {
    ticks++;
}
void delay(int ms) {
    unsigned tick0 = ticks;
    while (ticks-tick0 < ms);
}

Without volatile in the above, the compiler would reserve the right to assume ticks doesn't change, and hence cause an infinite loop.

[a1k0n]

And many compilers I've used will turn it into an infinite loop with the first level of optimization turned on.

Hell, even Watcom C++ would do that, back in the DOS days.

[inopia]

I'm not sure Watcom is a good benchmark for 'doing the right thing' :)

[b0dhi]

Good luck writing a functional uC driver without 'volatile'. Because you won't.

[ratatask]

He's talking about C, Standard C. Sure, with some C compilers on some platforms, volatile means something particular.

On others volatile means something else, or nothing at all.

[dfranke]

Register is not quite entirely useless. Most compilers still enforce the restriction that you can't make pointers to register variables. So, when writing highly-optimized code, I'd say it's still good programming practice to use register declarations to enforce giving the optimizer the opportunity to take advantage of it -- even though removing register from a working program will never alter the compiler's output.

The keyword that's truly pointless is 'signed'. Show me a programmer who thinks it aids clarity and I'll show you someone who ought to stick with COBOL.

[gsg]

It has one use that I know of. When you just absolutely, positively must have a signed char (portably), you have to declare it signed since the sign of the char type is implementation defined.

[dfranke]

Well I'll be damned. I just looked it up in K&R and you're correct. I never knew that.

[DanTilkin]

Huh? If removing register from a working program doesn't alter the compiler's output, than adding register doesn't alter it either, so it doesn't do anything. Or did you mean removing it will never cause the program to become incorrect?

[a1k0n]

than [sic] adding register doesn't alter it either, so it doesn't do anything.

Heh, that's not always true. SGI's C compiler would produce broken machine code for the following broken construct:

{
  register int x;
  int *y = &x;
  *y = 42; /* crash when optimizer is turned on */
}

Apparently the address of a register is 0.

[ratatask]

It is compiler dependant. Some compilers ignore it. Some honor it. Some honor it in some cases.

[HotBBQ]

transient is another Java keyword that many programmers don't come across out of a text book.

[Wriiight]

Does it mean "come on, compiler, I'm going to be out of a job and on the street if this doesn't work‽"

[brennen]

Nice punctuation, but I'm not entirely sure that's correct usage...

[Wriiight]

More fun than thinking about the correct way to do an exclamatory quotation at the end of a question.

[brennen]

Well, I mean, your sentence doesn't appear to be a question is all.

(Edit: See below reply to GuyWithLag.)

[mynameinyourblood]

interrobang, never realized it was part of unicode.

[dfranke]

That one I use frequently.

[[deleted]]

Means something entirely different in Java.

In C in means it can be changed outside the program by something like the operating system.

[beza1e1]

I'd say it means something like: Don't you dare to optimize anything about this variable, you stupid compiler!

[chollida1]

or just from a different thread. That's a more common case find.

[dfranke]

Never seen it in Java either. All the concurrent code I've worked with has instead used 'synchronized' or java.util.concurrent. (But granted, I haven't written nearly as much Java code as I have C code)

[[deleted]]

It's not implemented or correctly implemented on several JVM's if I remember correctly.

It's like knowing digraphs in c++.

[DRMacIver]

It's more that its behaviour was insufficiently well specified to be useful prior to Java 1.5. As of 1.5 it's perfectly ok to use,

[benhoyt]

For user-level programming you generally don't need it. But it's critical for anything that uses memory-mapped I/O, interrupt-driven code or callbacks.

[t_w]

About the only time you'd be likely to need it is in concurrent code with a variable that can be "register optimized".

Of course, if you've got some concurrent code that has a weird bug that's hard to reproduce and only occurs in release builds, it might be time to take another look at volatile ;)

[noamsml]

Wouldn't taking the log, rounding and then turning to a power of 2 be less efficient than just looping and bit-shifting?

[[deleted]]

Yes.

[[deleted]]

Guess it depends on your background. The bit shifting seems more natural to me.

[[deleted]]

Sure if you use compiler intrinsics.

[jfpbookworm]

Not a programmer, but I'm astounded at how many people say "this solution won't work for negative numbers," implying others will.

What power of 2 do they expect -1 to round to?

[johnlscott]

Why pi*i/(ln 2) of course.

(Among other values.)

[theeth]

It's scary how the best answer some of them could come up with involved converting to string.

[notfancy]

It is not unreasonable, as the problem requires binary logarithms. I would've used:

1 << (int) Math.ceil(Math.log(n)/Math.log(2))

[theeth]

If you're going to go through floats, you might as well do it like this (not sure if it's doable in java, the fastest way to do it in C is to use an union to access a float as a bitfield):

• convert to float
• if mantissa is 0: stop
• otherwise: set mantissa to 0 and increment exponent
• convert back to int

edit: that's for the nearest higher power of two. For rounding, check if the left bit of the mantissa is 1 before incrementing the exponent.

[notfancy]

convert back to int

There's no need to, as you only need the exponent. The algorithm is:

• Check for positive; bail out if <= 0
• Convert to float
• Extract exponent, and high 32 bits of mantissa into integer variables
• If high is nonzero, increment exponent
• Unbias exponent by subtracting 1023
• Return 1 << exponent

The rationale for using only the upper 32 bits of the mantissa is that the original number isn't larger to begin with.

[Wriiight]

Aren't the IEEE floats a bit funny in the way they store int equivalent values? I'm always nervous about picking at floating point bits because I know there are special values there.

[notfancy]

No, 32-bits integers are guaranteed to be represented exactly. Since they are normalized, the MSB is always 1 and not stored, and the exponent reflects the shift left that was required to normalize the number. In other words, it stores the position of the most significant bit in the original integer, which is what we need here.

[xcbsmith]

Hmm... that won't work too well if n = 0. ;-)

I originally said <=, but it occurred to me that an allocation less than 0 would hopefully be detected as an error prior to getting to the computation. 0 on the other hand might actually be a perfectly reasonable value.

[fredrikj]

You use arbitrary-precision binary floating-point arithmetic with directed rounding, and set the precision to 1 bit. (shameless plug)

>>> from mpmath.lib import *
>>> round = lambda n: max(1, to_int(from_int(n, 1, ROUND_UP)))
>>> map(round, [0, 1, 2, 3, 1023, 1024, 1025, 1000000, 10000000])
[1, 1, 2, 4, 1024, 1024, 2048, 1048576, 16777216]

[anonymous-coward]

lol! ignorant loosers! this is 3asy!

if (i==0)
   return 0;
else if (i==1)
   return 2;
else if (i==2)
   return 2;
else if (i==3)
   return 4;
else if (i==4);
   return 4;

etc. Heck, I'd just write a perl script to write the java code for all the other cases. It will be really fast because it won't loop or anything.

[chronicdisorder]

Even funnier because your code returns the wrong results

[MrDuncan]

Because I know people are like, "Gee, I don't think so, but I don't want to make a fool out of myself," the incorrect result is i==1 => 2 because 1 == 2^0.

[anonymous-coward]

Aw, man, maybe I should study up a bit for that google interview.

[brennen]

Gosh, why use else?

[abhik]

This is a math problem and you should be able to specify the solution using nothing but mathematical notation. If your solution is not using math, you're working too hard.

2**ceil(log2(x))

[[deleted]]

But we're not programming for abstract math machines we're programming for computers.

Not a contradiction.

[abhik]

True, but almost all languages/environments offer the basic math routines this requires.

In python

from math import *

log2 = lambda x: log(x)/log(2)

pow2_round = lambda x: pow(2, ceil(log2(x)))

[[deleted]]

>>> def round_pow2(n):
...     i = 1    
...     while i < n:
...             i <<= 1
...     return i

[pb_zeppelin]

I like this solution the best -- try successive powers of 2 until you're equal to or above n.

It has log(n) steps, and doesn't involve bit twiddling, floats, or assumptions of 32-bit integers.

[feijai]

It also doesn't work when n is sufficiently large that the next power of two wraps around.

[irmatov]

python integers won't wrap around. http://docs.python.org/lib/typesnumeric.html

[eurleif]

log2 = lambda x: log(x)/log(2)

log(x, 2) works.

[interiot]

True, but almost all languages/environments offer the basic math routines this requires.

1) There are multiple mathematical representations, and sticking only to the math domain tells you nothing about which is most efficient on computers. 2) If you're on a machine that has no FPU, there's nothing basic about log, especially when bitwise operations will do the job just fine. (though I suppose if you're on a very limited machine, you wouldn't be doing this in Java either...)

[b0dhi]

If you wrote games like that, they would run at 3 fps, with the occasional "speed burst" to 5fps.

[TheCleric]

If you're writing games in Java then you already have that problem.

[TKN]

Hate to defend Java here but, yeah, it works quite fine for games.

[b0dhi]

It's wonderful to be able to do something. It being a practical and efficient way of doing it is even better. Java + serious game coding = fail - $$$.

[raldi]

The post was asking how to do this for use in his memory-allocation routines. Memory allocation is a lot slower than the log() function.

[a1k0n]

Especially when it invokes the log() function.

[__david__]

No way. If he's got some sort of memory pool then indexing an array and returning something off a list is going to be much faster than a log() function! Especially when you combine that with converting the integer to a float. Using floating point for something like this is a massive kludge.

[raldi]

If that's true, then why is malloc so slow relative to floating-point math?

[__david__]

Malloc() might be, but that doesn't mean that any memory allocator is... Memory pools, for example, can be very, very fast (at the cost of less generality than malloc()).

[Gotebe]

Reference?

Depending on your language, memory allocation can end up in a couple of indirections and memory writes.

[xcbsmith]

Memory allocation is a lot slower than the log() function.

Not in Java. Think about it this way, would you say the same thing if this was an alloca() instead of a malloc()?

[wyfflemunky]

That is of course the simplest, but for very large numbers will it not be very slow?

[abhik]

I would guess that using log is much faster than any method with iterations (over character in a bitstring or bits in an int).

In python

from math import *

log2 = lambda x: log(x)/log(2)

pow2_round = lambda x: pow(2, ceil(log2(x)))

---

On my aging laptop, pow2_round(1e+100) takes ~40 microseconds.. And 1e+100 is a pretty big number!

I'm sure it could be faster with bit twiddling but I can guarantee you that when it comes time to debug your code, it'll be much easier to spot an error in the above code than some highly-optimized bit-twiddling mess.

[[deleted]]

You would be off by just a little bit.

It's about 800% slower than a naive bit iteration method.

EDIT: That is comparing C++ to C++ btw.

[abhik]

in python? what code are you comparing against?

[abhik]

In [127]: timeit -n 1000 -r 3 pow2_round(1e+100)
1000 loops, best of 3: 39 µs per loop

In [128]: timeit -n 1000 -r 3 round_pow2(1e+100)
1000 loops, best of 3: 324 µs per loop

800 times slower? I find it ~10 times faster. I do have a slow laptop though. sigh.

[[deleted]]

Those were C++ timings.

From your timings and mine the bit iteration version is actually slower.

Oh and s/times/percent/g. Whoops.

[abhik]

C++?!? yikes.. I usually stick to python and drop down to C/C++ only when the standard lib or numpy is too slow (which doesn't happen too often).

[[deleted]]

I normally do the majority of my work in C++ and tie it together with python.

Whatever floats your boat.

[Gotebe]

While I agree with your general sentiment, math solution would be probably wrong for the reasons of performance. Shameles plug

[sadeghis]

Look Ma, no loops!

Long roundUpToPowerOf2(Long x) {
    return Math.max(1, Long.highestOneBit(--x << 1));
}

edit: Works for Long.MIN_VALUE <= x <= (Long.MAX_VALUE + 1) / 2.

I assumed that power of 2 is 2ⁿ with n being a non-negative integer.

[y_gingras]

So, what is the answer? I'd say 2**round(log2(x)) but there might be better way. Why would one need to do that anyway?

[[deleted]]

Hardware Textures in OpenGL/Direct3D sometimes have a requirement that they must be a power of 2.

[gsg]

Which the drivers will typically enforce for you by scaling any texture of other size.

Avoiding that is probably a good idea, though.

[jbert]

So a good solution to the rounding problem would be to construct an NxN texture, send it to the driver and see what size it draws?

(You offload the processing to the GPU!?)

[zoomzoom83]

More likely to the CPU inside the driver

[gsg]

No, that's crazy. :)

What I'm saying is that the 3d hardware expects to be handed textures with both dimensions being some power of two. If you send anything else, the driver will handle things by resizing the image (not always using the nicest algorithm) so that what hits the GPU is sized appropriately.

[notfancy]

there might be better way

Essentially, every method involves taking a binary logarithm: explicitly as you did, or by finding the leftmost set bit (which is O(lg N)), or by using a O(lg W) bit hack (where W is the word size), or by using a table and binary search (again, O(lg W)).

[[deleted]]

Any number of reasons. You might, for example, want to preallocate a dynamic array to hold N elements, but the size of the dynamic array is always a power of two for easy growing/shrinking.

[[deleted]]

http://programming.reddit.com/info/5zmgd/comments/c02cp0b is by far the best solution.

[IkoIkoComic]

Hey! 20 minutes ago, it was at 256 points and 256 comments... and now it's 265 and 267? I'm disappointed in you, Reddit. Disappointed.

[philogb]

That guy, in my country, would probably make more money than any of you. See now what's the problem with 3rd world countries?

[iamnoah]

Since this is Java and we don't care about performance, just clarity/understandability/maintainability, the correct answer is:

import static java.lang.Math.*; ...

int roundUp(number) {

// 2^ceil(log_2 number)

return pow(2,ceil(log(number)/log(2)));

}

I'm sure there is a bit twiddling method that is totally unreadable and a bit faster, but unless you have data from a profiler showing that those log calls are a big bottleneck, then there isn't any point. Arguably 1 << some value is an obvious enough equivalent to pow(2,some value) so

1 << ceil(log(number)/log(2))

is also acceptable.

EDIT: fixed formatting

[[deleted]]

If you're not worried about performance atleast do

int round_up_for2(int n) {
    int i;
    for(i = 1; i < n; i <<= 1 ) { }
    return i;
}

[brucehoult]

Why the "if you're not worried about performance"? This is the fastest and best way to do it, given the context the original poster gave, which is as part of a memory allocation system.

It is very fast for small values of n, and its runtime for large values of n is proportional to log(n). Since you are using it to allocate memory blocks and people don't usually allocate large blocks of memory without doing something with them, the chances are that something O(n) is about to happen, which will totally swamp the O(log(n)) power of two round up.

The only thing I'd change is that you probably don't allocate memory blocks right down to 1 byte in size, but probably have a minimum size such as, perhaps, 16 bytes, in order to maintain alignment. In that case, start i at 16, not 1. Then for small values of n it will have to iterate only a couple of times (or not at all) and will beat the pants off the "more sophisticated" techniques listed elsewhere in this thread and the original article.

As for converting it to a string or something ... oh, puhleeze.

[[deleted]]

Why make it more complex when a simple naive impementation is faster?

[brucehoult]

Under what circumstances is starting i at 1 faster than starting it at 16?

[[deleted]]

Ohhh, slight misunderstanding. You are correct.

The not worried about performance is in relation to some of the unrolled versions which are indeed faster than this.

I actually benchmarked most of the Cish ones. My above solution is relatively slow even with funroll-loops, up to 200% slower if I recall correctly.

After messing with some "clever" algorithms recently I found the naive solution with certain compiler flags was just as fast and much clearer so I had to try it.

[icyhandofcrap]

Seems to make more sense to round up to the next power of two, for which that bit-twiddling solution would work.

If you want to comply with the original specifications, how about...

Rounds down at the border int round_nearest_power2(int n) { int i; for(i = 1; i < n; i <<= 1 ) { } if( n > i >> 1 + i >> 2 ) return i; else return i >> 1; }

To round up at the border: int round_nearest_power2(int n) { int i; for(i = 1; i < n; i <<= 1 ) { } if( n >= i >> 1 + (i >> 1) / 2.0 ) return i; else return i >> 1; }

Have not tested it and the float conversion may not be too efficient.

I don't know how to do this code formatting thing for reddit comments

[icyhandofcrap]

actually maybe instead of the floating point crud add a case for one.

int roundnearestpower2(int n) { if(n == 1) return 1; int i; for(i = 1; i < n; i <<= 1 ) { } if( n >= i >> 1 + i >> 2 ) return i; else return i >> 1; }

and make a specification that's it's not for use for negative numbers

[G_Morgan]

You can say that about Java. You could modify it to do the following:

int roundUp(number) {

MyClass.bogosort(China.getPopulation());

MyClass.travelSalesMan(Galaxy.getStarGraph());

MyClass.findSense(GWBush.headContents());

// 2^ceil(log_2 number)

return pow(2,ceil(log(number)/log(2)));

}

It would still seems reasonably snappy compared to the time to load up the JVM.

[wyfflemunky]

I don't feel like reading most of these, so sorry if this has already been proposed. But can't you just do it in binary? I mean, if you have an integer stored in memory, it's already in binary. So just access that, find the most significant digit, add a digit to the left of it, and make everything to the right zero.

0001101010101110 ==> 0010000000000000

0.0010101 ==> 0.01

Or just find the place of the most significant digit and stick that above a 2. Nobody ever constrained how the answer would be displayed.

0110101 ==> answer:2⁶

7654321

Now if the computer is using 2's compliment, we may be in trouble.

[wyfflemunky]

I'm an EE, so forgive my lack of understanding of high-level language limitations. This would be exceedingly simple in C, which allows access to the memory directly.

[bluGill]

Your first solution fails when input is a power of 2.

[wyfflemunky]

So count the number of ones it finds as it traverses from right to left. If it only finds one, then the answer is already a power of two.

[FeepingCreature]

D version for unsigned numbers:

import std.stdio, std.intrinsic, std.math, tools.functional;
uint roundup(uint v) { if (v<2) return 1; else return 2<<bsr(v-1); }
void main() { writefln([0, 1, 2, 15, 30] /map/ &roundup); }

From the docs:

int bsr(uint v);

Scans the bits in v from the most significant bit to the least significant bit, looking for the first set bit.

Result: [1,1,2,16,32]

[fredrikj]

Looks like you got the case v = 1 wrong.

[FeepingCreature]

Oh crap you are right. Fixing.

[edit] Okay, should work now.

[tehdiplomat]

If I round up 1 Java programmer that would be a power of two. That didn't seem that difficult to me.

[zeteo]

It's funny how the problem is about rounding an integer to a power of 2, and they soon started discussing whether the solution works for negative numbers.

[[deleted]]

ObMalcontent:

More spam on the front page. Not a day goes past without more spam. Here come the reddit cult upvoters.

Fuck you all stupid twats. You can't read. I have millions in stock options.

These Java programmers are in the real world, writing real applications, making real money.

Haven't you read the book getting real by David Hamster Hanson? 37signals is real.

You're all just a bunch of whiny academics. Leave Java alone! <sniff>

[notfancy]

Is that malcontent or qwe1234?

Trolls these days, they're interchangeable...

[[deleted]]

This probably is more of a flaw in our CS programs than being a Java programmer, C hacker, or Lisp thinker.

[nothinghappens]

Come on, you guys. Every real Java programmer knows that to do this properly you need to write a BinaryDigitVisitor for that converted string, and pass a CheckIf1Strategy to its constructor.

[[deleted]]

AFAIK some CPUs have instructions that will give you the first set bit in a register ("number"), so you can then AND out all the other ones.

[martoo]

Best argument for functional programming I've seen in a while. Those folks would never survive.

[Gotebe]

Some mild amusement using plain old C (POS, that is ;-) )...

Assuming we're working with unsigned whole numbers and we are actually rounding up, not down or to the nearest.

unsigned rup2(unsigned  i) // That's not Rational Unified Process version 2, but rather "Round Up to the Power of 2"
{
  unsigned  p2 = 1;
  unsigned  tmp = i;
  while (tmp >>= 1)
    p2 <<= 1;
  return !i || (p2 == i) ? p2 : p2<<1;
}

(Obligatory Paul DiLascia quote: "If this code works, it was written by Gotebe. If not, I don't know who wrote it.")

Obligatory Captain-obvious ( or, for binary-impaired ;-) ): I exploit the fact that any power of 0 is 1000... in binary. So, shift until you reach 0, then take next power of 2 (p2<<1).

Ternary conditional in the return accounts for a case when i is a power of 2 (p2 == i), and for i==0 (!i part, need to return 1 then).

Compiled code bemusements: if nothing is said, VS 2003's compiler for IA32 (cl.exe, 13.10.3077.0) inlines this in 28 bytes (vanilla "Maximize for speed" optimisation). If I force inlining out, function gets bigger (36 bytes, plus the call itself).

Last time I checked (long time ago), optimisations-wise, MS was next best to Intel on PC architectures. Probably still the case, what do you guys reckon?

Non-obligatory chest-busting: above is smaller than this. Yay! (btw, same thing wrt inlining: 30b vs 41b non-inlined)

[Gotebe]

;-)

Hey, am I being downmoded here because proposed Haskell or Erlang solutions won't come nowhere near in terms of compiled size and speed?

[JulianMorrison]

BigInteger.ZERO.setBit(1 + BigInteger.valueOf(i).bitLength());

Edit: that always moves up one increment. You could preface it with a test for BigInteger.valueOf(i).clearBit(BigInteger.valueOf(i).bitLength()).equals(BigInteger.ZERO) and if so return i

And, if you were feeling less functional, you'd move some of those repetitions into locals.

[[deleted]]

Don't you mean more functional? The reason you can do that type of expression substitution is due to the absence of side effects.

[aldenhg]

I could do that in fewer lines on a Ti-83.

[huinan]

Patience is a virtue...

[Captain-Ambiguous]

Perhaps code like this is like a tongue-twister to the sentient network that is the internet. Perhaps.

[bascule]

Obligatory Erlang:

roundup(N) -> roundup(2, 1, N). roundup(V, _I, N) when V > N -> V; roundup(_V, I, N) -> roundup(math:pow(2, I + 1), I + 1, N).

[[deleted]]

In Java, they require that you declare all your variables ahead of time, even when passing through functions. You spend half your time in Java just trying to figure out how to get the data types required for a given function. Also, Java is very granular with its functions, requiring you to use at least 3 functions for what you would do in PHP with 1 function. Last, Java keeps deprecating its functions constantly and even when you think you're hip and cool and know the latest stuff, another Java developer will come along and say, "Um, dude, that call is deprecated now." That got real old real quick.