# Finding the next power of two

Ron Kneusel emailed our internal PWUISATAI (People Who Use IDL Sitting Around Talking About IDL) group yesterday with a clever function he saw in some CUDA C code to calculate the next power of two greater than or equal to a given integer. His IDL translation:Both ISHFT and the OR operator are used here to perform bitwise operations on the input integer. Here's an example of using NEXT_POWER_2:functionnext_power_2, xcompile_optidl2, logical_predicate n = x -1; protects input n =ishft(n, -1)orn n =ishft(n, -2)orn n =ishft(n, -4)orn n =ishft(n, -8)orn n =ishft(n,-16)orn n =ishft(n,-32)orn n =ishft(n,-64)ornreturn, ++nend

IDL> a =I've used Ray Sterner's FACTOR, a part of the IDL astrolib, to learn that 4194304 is 23565946LIDL> b =next_power_2(a) IDL>factor, b 22 4194304 = 2

^{22}. Atle Borsholm replied to the group with an alternate take:

that gives the same result:functionn2, xreturn,ishft(1ull,total(ishft(1ull,indgen(64))ltx, /integer))end

IDL> b =Atle commented that although his version is shorter, Ron's may be faster. I was curious, so I made a simple time test:n2(a) IDL>

and ran it on my laptop:protime_test_next_power_2compile_optidl2 n_iter =1e6x =275259Lt0 =systime(/seconds)fori=1, n_iterdo!null =next_power_2(x) t1 =systime(/seconds)systime(/seconds)fori=1, n_iterdo!null =n2(x) t1 =systime(/seconds)end

`IDL> `**time_test_next_power_2**
NEXT_POWER_2: 2.14159489 s
N2: 2.77271295 s

So, Ron's version is slightly faster. In either case, we hope you might find these functions handy!
**Update**: An even simpler version from a zero-padding routine I'd written long ago:

IDL> a =3565946LIDL> b =2UL^ceil(alog(a)/alog(2)) IDL>

**Note**: I'll be out on vacation for a bit, so I have some guest bloggers lined up for the next few weeks.