Determine if sum is a power of 2

Question

What is the fastest (in asymptotic worst-case time complexity) algorithm for determining if a sum of arbitrary positive integers is a power of two?

@RenéG That doesn't really answer the question. For instance, is addition considered to be constant-time, regardless of the size of the operands? — Sneftel, Nov 28 '14 at 18:00

score 2 · Accepted Answer · answered Nov 28 '14 at 17:57

2

One cute bit twiddling trick is to test if x&(x-1) is equal to 0.

Note that you need to decide what to do if x is equal to 0, this test will mark 0 as a power of 2 so you may want an exception for this case.

answered Nov 28 '14 at 17:57

Peter de Rivaz

score 1 · Answer 2 · answered Nov 28 '14 at 17:58

1

Subtract 1 from the sum and perform a bitwise AND with the original number. Powers of 2 will have a result of 0.

answered Nov 28 '14 at 17:58

2 Answers2