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
    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

1

For your first question I assume you're considering only positive integers. If that's so then in binary we'll have $ 2^n = \mathtt{1}\underbrace{\mathtt{0\dots 0}}_n $ so the sum $2^n+2^m$, expressed as a binary number, will indeed have exactly two $\mathtt{1}$s, in places $n$ and $m$ (counting from the rightmost position, which we'll take as position zero), as long as $n\ne m$. If you have $n=m$, then $2^n+2^m=2\cdot2^n=2^{n+1}$, which will have a single $\mathtt{1}$ when expressed in binary.

Summing up (no pun intended), the sum of two distinct powers of 2 will indeed have exactly two $\mathtt{1}$s in its binary representation. In fact, this generalizes naturally: a positive integer is the sum of $k$ distinct powers of $2$ if and only if its binary representation has exactly $k$ $\mathtt{1}$s.

Thus your $f(n)$ will be true if and only if $n$ is either a power of two or the sum of two distinct powers of two. In particular, knowing $f(x)$ and $f(y)$ will not be sufficient to determine $f(x+y)$. Sorry.