-3

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?

Improve this question
2
  • What operations are you allowed to use? Commented Nov 28, 2014 at 17:57
  • @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? Commented Nov 28, 2014 at 18:00

2 Answers 2

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.