0
$\begingroup$

I want to optimize a function that determines whether a given number $n$ is EITHER (a power of 2) OR (the sum of powers of 2). Using, this answer, it appears that a sum of power of 2s contain at most two 1s in binary representation. If my observation is incorrect, it defeats the purpose of this question so please state the same otherwise read on.

Let $f(n)$ be $true$ if the binary representation of $n$ contains at most two 1s.

I am working with a 2D grid of such numbers and currently calculate the following as unrelated operations:

  • $a=f(x)$
  • $b=f(y)$
  • $c=f(x+y)$
  • $d=f(x-y)$

Is it possible to reduce these four distinct computations by inferring one from the other?

  • 0
    I don't understand. Any power of 2 is already a power of 2, so why does it need to be represented as a sum of 2 powers of 2?2012-09-04
  • 0
    The functions test arbitrary coordinates that do not have to be a power of 2. I will try to clarify the question as best I can.2012-09-04

1 Answers 1