cómo encontrar 2 a la potencia de n. n va de 0 a 200

Question

Supongamos que mi sistema es una máquina de 32 bits. Considerando esto, si uso long int para n> 63 obtendré mi valor como 0. ¿Cómo resolverlo?

Answer 1

double es perfectamente capaz de almacenar potencias de dos hasta 1023 exactamente. No permita que alguien le diga que los números de punto flotante son de alguna manera siempre inexactos. Este es un caso especial donde no lo son!

double x = 1.0; 
for (int n = 0; n <= 200; ++n) 
{ 
    printf("2^%d = %.0f\n", n, x); 
    x *= 2.0; 
} 

Algunos salida del programa:

2^0 = 1 
2^1 = 2 
2^2 = 4 
2^3 = 8 
2^4 = 16 
... 
2^196 = 100433627766186892221372630771322662657637687111424552206336 
2^197 = 200867255532373784442745261542645325315275374222849104412672 
2^198 = 401734511064747568885490523085290650630550748445698208825344 
2^199 = 803469022129495137770981046170581301261101496891396417650688 
2^200 = 1606938044258990275541962092341162602522202993782792835301376 

Answer 2

limitarnos a esperar a un compilador de 256 bits, a continuación, utilizar int :-)

No, en serio, ya que lo que desea es comenzar con 1 y seguir doblando, lo mejor es conseguir una biblioteca entero grande como GNU MP.

---

Se podría hacer eso con un trozo de código como (no probado):

#include <stdio.h> 
#include "gmp.h" 

int main (void) { 
    int i; 
    mpz_t num; 

    mpz_init_set_ui (num, 1); 
    for (i = 0; i <= 200; i++) { 
     printf ("2^%d = ", i); 
     mpz_out_str (NULL, 10, num); 
     printf ("\n"); 
     mpz_mul_ui (num, num, 2); 
    } 

    return 0; 
} 

---

Usted podía código de su propia estructura de datos de una gran variedad de productos largos con sólo dos operaciones , duplicar e imprimir, pero creo que sería mucho más fácil simplemente usar GMP.

Si hace desea hacer su propia versión, eche un vistazo a esto. Es una variación/simplificación de algunas bibliotecas grandes enteros que he desarrollado en el pasado:

#include <stdio.h> 
#include <stdlib.h> 

// Use 16-bit integer for maximum portability. You could adjust 
// these values for larger (or smaller) data types. SZ is the 
// number of segments in a number, ROLLOVER is the maximum 
// value of a segment plus one (need to be less than the 
// maximum value of your datatype divided by two. WIDTH is 
// the width for printing (number of "0" characters in 
// ROLLOVER). 

#define SZ 20 
#define ROLLOVER 10000 
#define WIDTH 4 
typedef struct { 
    int data[SZ]; 
} tNum; 

 

// Create a number based on an integer. It allocates the segments 
// then initialises all to zero except the last - that one is 
// set to the passed-in integer. 

static tNum *tNumCreate (int val) { 
    int i; 

    tNum *num = malloc (sizeof (tNum)); 
    if (num == NULL) { 
     printf ("MEMORY ERROR\n"); 
     exit (1); 
    } 

    for (i = 0; i < SZ - 1; i++) { 
     num->data[i] = 0; 
    } 
    num->data[SZ-1] = val; 
} 

// Destroy the number. Simple free operation. 

static void tNumDestroy (tNum *num) { 
    free (num); 
} 

 

// Print the number. Ignores segments until the first non-zero 
// one then prints it normally. All following segments are 
// padded with zeros on the left to ensure number is correct. 
// If no segments were printed, the number is zero so we just 
// output "0". Then, no matter what, we output newline. 

static void tNumPrint (tNum *num) { 
    int i, first; 
    for (first = 1, i = 0; i < SZ; i++) { 
     if (first) { 
      if (num->data[i] != 0) { 
       printf ("%d", num->data[i]); 
       first = 0; 
      } 
     } else { 
      printf ("%0*d", WIDTH, num->data[i]); 
     } 
    } 
    if (first) { 
     printf ("0"); 
    } 
    printf ("\n"); 
} 

 

// Double a number. Simplified form of add with carry. Carry is 
// initialised to zero then we work with the segments from right 
// to left. We double each one and add the current carry. If 
// there's overflow, we adjust for it and set carry to 1, else 
// carry is set to 0. If there's carry at the end, then we have 
// arithmetic overflow. 

static void tNumDouble (tNum *num) { 
    int i, carry; 
    for (carry = 0, i = SZ - 1; i >= 0; i--) { 
     num->data[i] = num->data[i] * 2 + carry; 
     if (num->data[i] >= ROLLOVER) { 
      num->data[i] -= ROLLOVER; 
      carry = 1; 
     } else { 
      carry = 0; 
     } 
    } 
    if (carry == 1) { 
     printf ("OVERFLOW ERROR\n"); 
     exit (1); 
    } 
} 

 

// Test program to output all powers of 2^n where n is in 
// the range 0 to 200 inclusive. 

int main (void) { 
    int i; 
    tNum *num = tNumCreate (1); 
    printf ("2^ 0 = "); 
    tNumPrint (num); 
    for (i = 1; i <= 200; i++) { 
     tNumDouble (num); 
     printf ("2^%3d = ", i); 
     tNumPrint (num); 
    } 
    tNumDestroy (num); 
    return 0; 
} 

y su salida asociada:

2^ 0 = 1 
2^ 1 = 2 
2^ 2 = 4 
2^ 3 = 8 
2^ 4 = 16 
2^ 5 = 32 
2^ 6 = 64 
2^ 7 = 128 
2^ 8 = 256 
2^ 9 = 512 
: : : : : 
2^191 = 3138550867693340381917894711603833208051177722232017256448 
2^192 = 6277101735386680763835789423207666416102355444464034512896 
2^193 = 12554203470773361527671578846415332832204710888928069025792 
2^194 = 25108406941546723055343157692830665664409421777856138051584 
2^195 = 50216813883093446110686315385661331328818843555712276103168 
2^196 = 100433627766186892221372630771322662657637687111424552206336 
2^197 = 200867255532373784442745261542645325315275374222849104412672 
2^198 = 401734511064747568885490523085290650630550748445698208825344 
2^199 = 803469022129495137770981046170581301261101496891396417650688 
2^200 = 1606938044258990275541962092341162602522202993782792835301376 

Answer 3

Si unsigned long int es de 64 bits, entonces el valor más grande para 2^n que se puede representar es 2^63 (es decir, n = 63):

unsigned long int x = (1UL << n); // n = 0..63

Answer 4

Ha sido mucho tiempo desde que he usado Java en serio, pero: BigInteger clase? Tiene todas las operaciones matemáticas (multiply, pow) y bitwise (shiftLeft) usuales.

Sin embargo, su etiquetado es un poco confuso, ¿qué idioma prefirió?

Answer 5

En C/C++ No conozco una forma estándar de almacenar enteros tan grandes, la solución de pax es el camino a seguir.

Sin embargo para Java, usted tiene una salida, BigInteger

Answer 6

Uso java.math.BigInteger.shiftLeft.

for (int i = 0; i <= 200; i++) { 
     System.out.format("%d = %s%n", i, BigInteger.ONE.shiftLeft(i)); 
    } 

Extracto de output:

0 = 1 
1 = 2 
2 = 4 
3 = 8 
4 = 16 
: 
197 = 200867255532373784442745261542645325315275374222849104412672 
198 = 401734511064747568885490523085290650630550748445698208825344 
199 = 803469022129495137770981046170581301261101496891396417650688 
200 = 1606938044258990275541962092341162602522202993782792835301376 

Si BigInteger no está disponible, también se puede hacer precisamente manualmente la multiplicación y la almacena en un String.

String s = "1"; 
    for (int i = 0; i < 200; i++) { 
     StringBuilder sb = new StringBuilder(); 
     int carry = 0; 
     for (char ch : s.toCharArray()) { 
      int d = Character.digit(ch, 10) * 2 + carry; 
      sb.append(d % 10); 
      carry = d/10; 
     } 
     if (carry != 0) sb.append(carry); 
     s = sb.toString(); 
     System.out.format("%d = %s%n", i + 1, sb.reverse()); 
    } 

(see full output)

Answer 7

Python soporta grandes números enteros fuera de la caja. En cualquier solicitud de Linux, ejecute esto:

$ python -c "for power in range(201): print power, 2**power" 
0 1 
1 2 
2 4 
3 8 
4 16 
5 32 
6 64 
<snip> 
196 100433627766186892221372630771322662657637687111424552206336 
197 200867255532373784442745261542645325315275374222849104412672 
198 401734511064747568885490523085290650630550748445698208825344 
199 803469022129495137770981046170581301261101496891396417650688 
200 1606938044258990275541962092341162602522202993782792835301376 

Esto se puede hacer fácilmente en una secuencia de comandos si es necesario. Ver cualquier tutorial de Python.

Answer 8

Uso esquema!

1 => (expt 2 200) 
1606938044258990275541962092341162602522202993782792835301376