Dado un entero positivo, encontrar su sparsest representación binaria utilizando coeficientes en $\{0,\pm 1\}$

Question

Sabemos que cualquier número entero positivo se puede representar como

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

donde $a_i \in \{ 0, \pm 1 \}$. Dado arbitrariamente un entero grande, ¿cómo podemos encontrar su sparsest representación binaria, es decir, la combinación que contiene el menor número posible de cero $a_i$'s?

Answer 1

Un algoritmo es escribir el número en binario estándar. A partir de la $a_0$ plazo, si usted tiene dos términos $a_i,a_{i+1}$ tanto $1$, usted puede reemplazar con $a_i=-1,a_{i+2}=1$. Si $a_{i+2}$ ya $1$, ahora es $2$ y la puedes llevar, establecimiento $a_{i+2}=0, a_{i+3}=1$. A seguir adelante. Esto va a terminar cuando se puede conseguir en la mayoría un poco más alto que el que comenzó, como usted sabe que poco empezó de cero. Como hacer dos pasadas por el binario de expansión de la serie, esto es $O(\log n)$

Answer 2

Escribir el número en binario (si es negativo escriba su valor absoluto) y supongamos que hay $k$ bloques consecutivos.

comience con la respuesta $2k$.

Por cada dos bloques consecutivos con exactamente un $0$ entre ellos reste $1$ a la respuesta.

Para cada bloque de tamaño $1$ que no tiene exactamente un cero entre el bloque siguiente restar $1$ a la respuesta.

El valor restante es el resultado.

Código c++:

#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);
}

Answer 3

Yo creo que lo más eficiente la representación sería venir para arriba con una representación de secuencias de unos en la representación binaria.

Entonces no veo cómo podría vencer siguientes heurísticas:

1. una sola ocurrencia de 1 es sólo que el término
2. doble aparición, por conveniencia sólo los términos
3. tres o más (conjunto de bits de $k$ $l$ (no incluido) -> $2^l-2^k$)
4. una sola $0$ en una serie de $1$'s sólo puede ser restado

Answer 4

Bueno, para explicar mi comentario (funciona incluso mejor de lo que yo hubiera pensado):

Digamos que queremos representar el número de $K$. El uso de la primera n "dígitos" $a_0,...,a_{n-1}$ sólo puede crear los números entre el $-2^n+1$ (tomando todos los ser $-1$) y $2^n-1$ (tomando todo como 1). Por otro lado, la mayor dígitos $a_n,a_{n+1},...$, por lo que de no cambiar el número de mod $2^n$. En conjunto, esto significa que cualquiera de las $\sum_{i=0}^{n} a_i 2^i = (K \mod 2^n)$ o $\sum_{i=0}^{n} a_i 2^i = (K \mod 2^n)-2^n$. (O estamos en el caso extremo de que $(K \mod 2^n) =0$.)

Pero entonces se puede calcular el óptimo representación de $(K \mod 2^n)$ $(K \mod 2^n) -2^n$ recursivamente: Supongamos que sabemos que la óptima representación de $(K \mod 2^{n-1})$$(K \mod 2^{n-1}) -2^{n-1}$.

Ahora nos encontramos con la óptima para $(K \mod 2^n)$. Podemos tener $(K \mod 2^n) = (K \mod 2^{n-1})+2^{n-1}$, en este caso la única representación es la de $(K \mod 2^{n-1})$$a_{n-1} =1$. O tenemos $(K \mod 2^n) = (K\mod 2^{n-1})$, en este caso se pueden tomar ya sea la representación de $(K \mod 2^{n-1})$ $a_{n-1} = 0$ o de la representación de $(K \mod 2^{n-1}) -2^{n-1}$$a_{n-1} = -1$, el que sea menor.

La óptima representación de $(K \mod 2^{n})- 2^n$ se puede encontrar en una manera similar. Repita esto hasta llegar a $(K \mod 2^n) = K$