# Given a positive integer, find its sparsest binary representation using coefficients in $\{0,\pm 1\}$

We know that any positive integer can be represented as

$$\displaystyle\sum_{i=0}^\infty a_i \cdot 2^i$$

where $a_i \in \{ 0, \pm 1 \}$. Given an arbitrarily large integer, how can we find its sparsest binary representation, i.e., the combination containing the least possible number of nonzero $a_i$’s?

• I don't see a closed form, however I think a sort of dynamic programming approach should work nicely. – mlk May 29 '17 at 15:06

One algorithm is to write the number in standard binary. Starting from the $a_0$ term, if you have two terms $a_i,a_{i+1}$ that are both $1$, you can replace them with $a_i=-1,a_{i+2}=1$. If $a_{i+2}$ was already $1$, it is now $2$ and you can carry, setting $a_{i+2}=0, a_{i+3}=1$. Keep going. This will terminate when you get at most one bit higher than you started with, as you know that bit started out zero. As you make two passes through the binary expansion of the number, this is $O(\log n)$

• Binary! Of course. That’s the breakthrough I needed. Will comment later on how it worked. – CBlew May 29 '17 at 15:50
• In the end, it worked swimmingly. Thank you. – CBlew May 30 '17 at 9:00

I think the most efficient representation would be to come up with a representation for sequences of ones in the binary representation.

Then I don't really see how you could beat following heuristics:

1. a single occurrence of 1 is just that term
2. double occurrence, for convenience just the terms
3. three or longer (bits set from $k$ up to $l$ (not inclusive) -> $2^l-2^k$)
4. a single $0$ in a series of $1$'s can just be subtracted
• Could you please elaborate on step 4? Subtracted how? – CBlew May 29 '17 at 17:55
• $0b11101111 = 2^8-2^0-2^4$. $2^8-2^0$ for the sequence of 8 ones and an additional $-2^4$ to clear the 5-th bit from the right (count starts at 0) – Pieter21 May 29 '17 at 19:34
• Understood. So, in a sense, we could drop steps 2 and 4, and change step 3 to “two or longer” and get the same result. (If, of course, we apply steps iteratively, each time starting from the beginning.) – CBlew May 30 '17 at 8:58

Write the number in binary (if it is negative write its absolute value) and suppose that there are $k$ blocks of consecutive ones.

start with the answer $2k$.

For every two consecutive blocks with exactly one $0$ between them subtract $1$ to the answer.

For every block of size $1$ that does not have exactly one zero between the next block subtract $1$ to the answer.

The remaining value is your result.

Some c++ code:

#include <bits/stdc++.h>
using namespace std;

const int MAX=100;
vector <int> A(MAX);
vector <int> L; // left end of blocks
vector <int> R; // right end of blocks

void tobin(int x){
for(int i=0;i<MAX;i++){
A[i]=x%2;
x/=2;
}
}

int main(){
int n;
scanf("%d",&n);
tobin(n);
for(int i=0;i<MAX;i++){
if( (i==0 || A[i-1]%2 == 0 ) && A[i]%2 ) L.push_back(i);
if( (i==MAX-1 || A[i+1]%2 == 0 ) && A[i]%2 ) R.push_back(i);
}
int res=2*L.size();
for(int i=0;i+1<L.size();i++){
if(R[i]+2== L[i]) res--;
}
for(int i=0;i<L.size();i++){
if(L[i]== R[i] && (i==L.size()-1 || R[i]+2 != L[i]) ) res--;
}
printf("%d\n",res);
}

• I knew I’d have to start reading K&R sooner or later. But I believe I get the general idea. Thank you. – CBlew May 29 '17 at 15:51

Okay, to elaborate on my comment (It works even better than I would have thought):

Let us say we want to represent the number $K$. Using the first n "digits" $a_0,...,a_{n-1}$ you can only create the numbers between $-2^n+1$ (taking all to be $-1$) and $2^n-1$ (taking all as 1). On the other hand, the higher digits $a_n,a_{n+1},...$ and so on do not change the number mod $2^n$. Together this means that either $\sum_{i=0}^{n} a_i 2^i = (K \mod 2^n)$ or $\sum_{i=0}^{n} a_i 2^i = (K \mod 2^n)-2^n$. (Or we are in the edge case that $(K \mod 2^n) =0$.)

But then we can calculate the optimal representation of $(K \mod 2^n)$ and $(K \mod 2^n) -2^n$ recursively: Assume we know the optimal representation of $(K \mod 2^{n-1})$ and $(K \mod 2^{n-1}) -2^{n-1}$.

Now we find the optimal one for $(K \mod 2^n)$. We can either have $(K \mod 2^n) = (K \mod 2^{n-1})+2^{n-1}$, in this case the only representation is the one of $(K \mod 2^{n-1})$ with $a_{n-1} =1$. Or we have $(K \mod 2^n) = (K\mod 2^{n-1})$, in this case we can take either the representation of $(K \mod 2^{n-1})$ and $a_{n-1} = 0$ or the representation of $(K \mod 2^{n-1}) -2^{n-1}$ and $a_{n-1} = -1$, whichever is shorter.

The optimal representation for $(K \mod 2^{n})- 2^n$ can be found in a similar way. Repeat this until you reach $(K \mod 2^n) = K$