Sistema de numeración binaria sesgado

Para convertir un número decimal a un número binario asimétrico, se puede utilizar la siguiente fórmula: ^{[ 3 ]}

Caso base :${\displaystyle a(0)=0}$

Caso de inducción :${\displaystyle a(2^{n}-1+i)=a(i)+10^{n-1}}$

Límites :${\displaystyle 0\leq i\leq 2^{n}-1,n\geq 1}$

Para convertir un número binario asimétrico a decimal, se puede utilizar la definición de un número binario asimétrico:

${\displaystyle S=\sum _{i=0}^{N}b_{i}(2^{i+1}-1)}$, dónde${\displaystyle b_{i}\in {0,1,2}}$, st. solo el bit menos significativo (lsb) ${\displaystyle b_{lsb}}$es 2.

#include <iostream> #include <cmath> #include <algorithm> #include <iterator>usando el espacio de nombres std ;dp largo [ 10000 ];//Usando la fórmula a(0) = 0; para n >= 1, a(2^n-1+i) = a(i) + 10^(n-1) para 0 <= i <= 2^n-1, //tomado de The On-Line Encyclopedia of Integer Sequences (https://oeis.org/A169683)long convertToSkewbinary ( long decimal ){int maksIndex = 0 ; marcas largas = 1 ; mientras ( maks < decimal ){ maks *= 2 ; maksIndex ++ ; }for ( int j = 1 ; j <= maksIndex ; j ++ ){ long power = pow ( 2 , j ); for ( int i = 0 ; i <= power -1 ; i ++ ) dp [ i + power -1 ] = pow ( 10 , j -1 ) + dp [ i ]; }return dp [ decimal ]; } int main () { std :: fill ( std :: begin ( dp ), std :: end ( dp ), -1 ); dp [ 0 ] = 0 ; // Se puede comparar con los números dados en //https://oeis.org/A169683 for ( int i = 50 ; i < 125 ; i ++ ) { long current = convertToSkewbinary ( i ); cout << current << endl ; }devolver 0 ; }

#include <iostream> #include <cmath>usando el espacio de nombres std ;// Decimal = (0|1|2)*(2^N+1 -1) + (0|1|2)*(2^(N-1)+1 -1) + ... // + (0|1|2)*(2^(1+1) -1) + (0|1|2)*(2^(0+1) -1) // // Entrada esperada: Un entero/long positivo donde los dígitos son 0, 1 o 2, y el único bit/dígito no cero menos significativo es 2. // long convertToDecimal ( long skewBinary ){int k = 0 ; long decimal = 0 ; while ( skewBinary > 0 ) { int digit = skewBinary % 10 ; skewBinary = ceil ( skewBinary / 10 ); decimal += ( pow ( 2 , k + 1 ) - 1 ) * digit ; k ++ ; } return decimal ; } int main () {int test [] = { 0 , 1 , 2 , 10 , 11 , 12 , 20 , 100 , 101 , 102 , 110 , 111 , 112 , 120 , 200 , 1000 };for ( int i = 0 ; i < sizeof ( test ) / sizeof ( int ); i ++ ) cout << convertToDecimal ( test [ i ]) << endl ;;devolver 0 ; }

Dado un número binario asimétrico, su valor se puede calcular mediante un bucle, calculando los valores sucesivos de${\displaystyle 2^{n+1}-1}$y añadiéndolo una o dos veces por cada uno${\displaystyle n}$de tal manera que el${\displaystyle n}$El dígito i es 1 o 2 respectivamente. Ahora se presenta un método más eficiente, con solo representación de bits y una resta.

El número binario asimétrico de la forma${\displaystyle b_{0}\dots b_{n}}$sin 2 y con${\displaystyle m}$1s es igual al número binario${\displaystyle 0b_{0}\dots b_{n}}$menos${\displaystyle m}$. Dejar${\displaystyle d^{c}}$representa el dígito${\displaystyle d}$repetido${\displaystyle c}$veces. El número binario sesgado de la forma${\displaystyle 0^{c_{0}}21^{c_{1}}0b_{0}\dots b_{n}}$con${\displaystyle m}$1s es igual al número binario${\displaystyle 0^{c_{0}+c_{1}+2}1b_{0}\dots b_{n}}$menos${\displaystyle m}$.

De forma similar a la sección anterior, el número binario${\displaystyle b}$de la forma${\displaystyle b_{0}\dots b_{n}}$con${\displaystyle m}$1s es igual al número binario sesgado${\displaystyle b_{1}\dots b_{n}}$más${\displaystyle m}$Tenga en cuenta que, dado que la suma no está definida, añadir${\displaystyle m}$corresponde a incrementar el número${\displaystyle m}$veces. Sin embargo,${\displaystyle m}$está acotado por el logaritmo de${\displaystyle b}$y el incremento requiere un tiempo constante. Por lo tanto, la transformación de un número binario en un número binario asimétrico se realiza en un tiempo lineal con respecto a la longitud del número.