Un simple pero efectivo atoi

Hace mucho que no escribo en esta seccion del blog, pero bueno, no se alarmen. Hoy en uno de los foros que leo me pidieron que les enseñe a crear un atoi (convertir de cadena a entero) en c. Y como fue codigo 100% hecho por mi se me ocurrio compartirlo. Ademas por la explicacion que hice. Aqui va el codigo.

numero = 0;

for(i=0;cadena[i] != '\0' ;i ++) {

 digito=cadena[i] - '0';

 numero = numero * 10 + digito;

}

Como cada caracter es representado por un numero, a esto le podemos restar otros caracteres para obtener otro caracter o un numero. Por ejemplo para obtener el digito 5 desde el caracter '5' podemos hacer:

'5' - '0' = 5
'2' - '0' = 2

La idea es restar siempre el primer elemento de la secuencia ordenada de caracteres que queramos. Es posible aplciar esta tecnica para averiguar el numero de letra( 'g' - 'a').

Luego pensemos en un poco de matematica:

2345 = 2 x 1000 + 3 * 100 + 4 * 10 + 5

Esta idea nos da una pequeña intuicion. Tenemos que ir multiplicando cada digito(obtenido con la tecnica anterior) por un multiplo de 10 segun corresponda. Pero no es muy conveniente llegar al digito menos representativo para empezar a multiplicar.

Existe una mejor tecnica. Miren esta descomposicion efectuada gracias a la distribucion del producto:

2345 = 2 x 1000 + 3 * 100 + 4 * 10 + 5 = (2 * 100+ 3 * 10 + 4) * 10 + 5

Si seguimos desarrollando de esa manera, observaremos que al agregar un nuevo digito al numero, simplemente multiplicamos por 10 el numero anterior y le sumamos el digito siguiente:

numero = numero * 10 + digito

Todos sabemos que al multiplicar un numero por diez, se corre la coma a la derecha, apareciendo un cero final. Simplemente hay que sumarle el digito obtenido y listo.

Un agregado mas, en el for se recorre hasta que se obtiene un final de cadena. Pero se puede modificar para que recorra siempre que se obtenga un digito. Cuando este no aparezca mas se corta. Osea podremos parciar numeros desde cadenas como estos "1234holamundo"

Les dejo la pista para esto. En el for deberian chequear esta condicion: '0'<= cadena[i]<='9'

Numeros Palindromos (Capicuas)

En esta entrega chekearemos si un numero es palindromo, es decir, si es capicua (se lee igual de izquierda a derecha o viceversa).

La funcion es simple calculamos el numero inverso y despues camparamos:

int palindromo(int numero){

int original, inverso, digito;

original = numero;

inverso = 0;

while (numero != 0){

digito = numero % 10;

inverso = inverso * 10 + digito;

numero = numero / 10;

}

if (inverso == original) return 1;

return 0;

}

Podemos observar, que en el while se calcula el numero inverso. Simplemente se calcula el resto de dividir el numero por 10. Esto nos da el primer digito. A nuestro numero inverso lo multiplicamos por diez y le sumamos ese resto, para agregarle que obtuvimos antes. Y por ultimo a nuestro numero le calculamos la division entera (en c es por defecto al ser variables enteras) por 10 para quitar el digito leido.

Despues ponemos un IF para determinar la igualdad entre el numero y el inverso obtenido.

Maximo Comun Divisor

En esta entrada les paso un algoritmo hecho en C para calcular el maximo cumun divisor entre dos numeros enteros:

int mcd(int a,int b){

while (a!=b){

if(a>b) a = a -b;

if(b>a) b = b-a;

}

return a;

}

Determinar si un Numero es Primo

Aca les dejo una funcion para calcular si un numero es primo.

#include

int esprimo (int a){

int i;

if ( a == 2 || a==1 || a==3 ) return 1;

for ( i = 3; i <= (int)sqrt (a); i = i + 2) if ( a % i == 0 ) return 0;

return 1;

}

No es de las funciones mas eficiente si hay que calcular muchos numeros primos, pero para saber en particular si un numero es primo sirve.

En una proxima entrada le pasare un algoritmo conocido como la Criba de Eratóstenes, que que permite hallar todos los números primos menores que un número natural dado N.

Calcular Valor Absoluto

En esta entrada les paso un simple codigo para calcular el valor absoluto de un Short (16 bits) en una sola linea:

n = (n ^ (n>>15)) - (n>>15);

Un simple programa implementando esto:

int main(void){

short int n = -5510;

n = (n ^ (n>>15)) - (n>>15);

printf("Valor Absoluto %i \n",n);

}

En Assembler se puede implementar en tres simples lineas.
Aca les paso la misma funcion para Assembler con Sintaxys de AT&T (compila con Gcc):

.data

num:.long -145 # Numero a negar

p: .string "Numero Negado: %d\n" # String para mostrar el numero

.text

.global main

main:

movl num, %eax

movl %eax,%ebx # esta dos lineas cargo el numero en registro

sarl $15,%ebx

xorl %ebx, %eax

subl %ebx, %eax # esta tres lineas calculan el valor absoluto

pushl %eax

pushl $p

call printf # tres lineas para mostrarlo

addl $8, %esp

ret