c++ - raiz - ¿Cómo representar un número en la base 2 ^ 32?
logaritmo en base 2 de raiz de 2 (5)
Si tengo un número base 10 o base 16, ¿cómo lo cambio a base 2 ^ 32?
La razón por la que trato de hacer esto es por la implementación de BigInt como lo sugirieron otros miembros aquí. ¿Por qué usar una base más alta para implementar BigInt?
¿Será lo mismo que un entero (base 10) hasta 2 ^ 32? ¿Qué pasará después?
Si tengo un número base 10 o base 16, ¿cómo lo cambio a base 2 ^ 32?
Al igual que lo convierte a cualquier otra base. Desea escribir el número n como
n = a_0 + a_1 * 2^32 + a_2 * 2^64 + a_3 * 2^96 + ... + a_k * 2^(32 * k).
Entonces, encuentra la mayor potencia de 2 ^ 32 que se divide en n , resta el múltiplo de esa potencia de n , y repite con la diferencia.
Sin embargo, ¿estás seguro de haber hecho la pregunta correcta?
Sospecho que quieres hacerte una pregunta diferente. Sospecho que quieres preguntar: ¿cómo puedo analizar un número de base 10 en una instancia de mi BigInteger ? Eso es fácil. Codifique su implementación y asegúrese de haber implementado + y * . Soy completamente indiferente a la forma en que realmente representas internamente enteros, pero si quieres usar la base 2 ^ 32, bien, hazlo. Entonces:
BigInteger Parse(string s) {
BigInteger b = new BigInteger(0);
foreach(char c in s) { b = b * 10 + (int)c - (int)''0''; }
return b;
}
Te dejo traducir esto a C.
Creo que esto es algo totalmente razonable de hacer.
Lo que está haciendo es representar un número muy grande (como una clave de cifrado) en una matriz de enteros de 32 bits.
Una representación de base 16 es base 2 ^ 4, o una serie de 4 bits a la vez. Si está recibiendo una secuencia de 16 "dígitos" base, complete los 4 bits bajos del primer entero en su matriz, luego el siguiente más bajo, hasta que lea 8 "dígitos". Luego ve al siguiente elemento en la matriz.
long getBase16()
{
char cCurr;
switch (cCurr = getchar())
{
case ''A'':
case ''a'':
return 10;
case ''B'':
case ''b'':
return 11;
...
default:
return cCurr - ''0'';
}
}
void read_input(long * plBuffer)
{
long * plDst = plBuffer;
int iPos = 32;
*(++plDst) = 0x00;
long lDigit;
while (lDigit = getBase16())
{
if (!iPos)
{
*(++plDst) = 0x00;
iPos = 32;
}
*plDst >> 4;
iPos -= 4;
*plDst |= (lDigit & 0x0F) << 28
}
}
Hay algo que hacer, como terminar cambiando * plDst por iPos, y haciendo un seguimiento del número de enteros en su matriz.
También hay algo de trabajo para convertir desde la base 10.
Pero esto es suficiente para que comiences.
Estás tratando de encontrar algo de la forma
a0 + a1 * (2^32) + a2 * (2^32)^2 + a3 * (2^32)^3 + ...
que es exactamente la definición de un sistema base-2 32 , ¡así que ignora a todas las personas que te dijeron que tu pregunta no tiene sentido!
De todos modos, lo que describes se conoce como conversión base . Hay formas rápidas y hay formas fáciles de resolver esto. Las formas rápidas son muy complicadas (hay capítulos enteros de libros dedicados al tema), y no voy a tratar de abordarlos aquí (sobre todo porque nunca he intentado usarlos).
Una manera fácil es implementar primero dos funciones en su sistema numérico, multiplicación y adición. (es decir, implementar BigInt add(BigInt a, BigInt b) y BigInt mul(BigInt a, BigInt b) ). Una vez que haya resuelto eso, notará que un número de base 10 se puede expresar como:
b0 + b1 * 10 + b2 * 10^2 + b3 * 10^3 + ...
que también se puede escribir como:
b0 + 10 * (b1 + 10 * (b2 + 10 * (b3 + ...
así que si te mueves de izquierda a derecha en tu cadena de entrada, puedes despegar una base-10 dígitos a la vez, y usar tus funciones add y mul para acumular en tu BigInt :
BigInt a = 0;
for each digit b {
a = add(mul(a, 10), b);
}
Descargo de responsabilidad: este método no es eficiente desde el punto de vista de la computación, pero al menos lo ayudará a comenzar.
Nota: Convertir desde base-16 es mucho más simple, porque 2 32 es un múltiplo exacto de 16. Así que la conversión básicamente se reduce a concatenar bits.
La base 16 es fácil, ya que 2 32 es 16 8 , una potencia exacta. Entonces, comenzando desde el dígito menos significativo, lea 8 dígitos de la base 16 a la vez, convierta esos dígitos en un valor de 32 bits, y ese es el siguiente "dígito" de la base 2.
La base 10 es más difícil. Como dices, si es menor que 2 32 , entonces simplemente tomas el valor como una única base-2 32 "dígito". De lo contrario, el método más simple que puedo pensar es usar el algoritmo de división larga para dividir repetidamente el valor de la base 10 en 2 32 ; en cada etapa, el resto es la siguiente base-2 32 "dígito". Tal vez alguien que sabe más teoría de números que yo podría proporcionar una mejor solución.
Supongamos que estamos hablando de un número de base 10:
a[0]*10^0 + a[1]*10^1 + a[2]*10^2 + a[3]*10^3 + ... + a[N]*10^N
donde cada a[i] es un dígito en el rango de 0 a 9 inclusive.
Voy a suponer que puedes analizar la cadena que es tu valor de entrada y encontrar la matriz a[] . Una vez que puede hacer eso, y suponiendo que ya ha implementado su clase BigInt con los operadores + y * , entonces está en casa. Simplemente puede evaluar la expresión anterior con una instancia de su clase BigInt .
Puede evaluar esta expresión de manera relativamente eficiente utilizando el método de Horner .
Acabo de anotar esto, y apostaría a que hay esquemas de conversión de bases mucho más eficientes.