How to obtain the next Power Of Two of a given number?

Question

Possible Duplicate:
bit twiddling: find next power of two

For example, i receive the number 138, the next POT number is 256.

i receive the number 112, the next POT is 128.

I need to do an algorithm that calculates that

Thanks

This is homework, isn't it? You must tag homework as such. – Marcin Oct 07 '11 at 10:14 — Marcin, Oct 07 '11 at 10:14
Why is 256 instead of 128 the next POT for 112? – sth Oct 07 '11 at 10:17 — sth, Oct 07 '11 at 10:17

score 15 · Accepted Answer · edited Jan 18 '16 at 17:08

15

A really clever programmer would look at the java.lang.Integer.highestOneBit(int) method, and consider the left-shift operator (<<).

edited Jan 18 '16 at 17:08

Ragunath Jawahar

19,513
22
110
155

answered Oct 08 '11 at 00:47

Jeff Grigg

1,004
8
7

1

+1; didn't know that method existed! – S.L. Barth is on codidact.com Oct 08 '11 at 06:30
3

A concrete formula is missing. Assuming the next power of two of 128 is 128, then what about `Math.max(1, Integer.highestOneBit(i - 1) << 1)`? – Thomas Mueller Feb 22 '17 at 08:15

score 6 · Answer 2 · answered Oct 07 '11 at 10:20

Here is a very simple algorithm (since this is homework, you'll have to code it up yourself):

Start with 1 as the first candidate power of two.
Keep shifting the candidate number by one bit to the left until it's greater than, or equal to, the target number.

score 5 · Answer 3 · answered Oct 07 '11 at 10:17

5

Assuming the input is a positive integer, one unconventional solution would be to look at the bit pattern of the number. Find the first '1' from the left, then think about the value of the bit to the left of that.

answered Oct 07 '11 at 10:17

S.L. Barth is on codidact.com

8,198
71
51
66

can you explain me how to do it please? – NullPointerException Oct 07 '11 at 13:05

How to obtain the next Power Of Two of a given number?

3 Answers3