C Piscine — C 04

El puente entre texto y números. Se escriben ft_strlen, ft_putstr, ft_putnbr, ft_atoi y sus versiones en base arbitraria. 6 ejercicios (ex00–ex05).

Números, bases y representación — El tema del módulo. Un int en memoria es un patrón de bits; «42» es solo una forma de escribirlo en base 10. La misma cantidad es 101010 en binario, 2a en hexadecimal o 52 en octal: cambia la notación, no el valor. Convertir texto→número (atoi) y número→texto (putnbr) es traducir entre esas representaciones, y hacerlo en cualquier base obliga a entender la notación posicional de raíz: cada dígito vale su símbolo por la base elevada a su posición. Este módulo también es el primer contacto con los límites del int —el overflow— y con el caso más venenoso de todo C: INT_MIN, el negativo que no tiene positivo.

GGlosario de teoría

C 04 traduce entre texto y números, y para eso hay que saber cómo se escribe un número en una base, cómo lo guarda la máquina y dónde están sus límites. Aquí está cada idea explicada desde cero y con un ejemplo sacado del propio módulo. En el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace a su entrada.

Texto y salida

Cadena de C y terminador nulo (\0)

Una cadena en C es una fila de char seguidos en memoria que acaba en un byte con valor 0, el terminador nulo ('\0'). La longitud no se guarda en ningún sitio: para saberla hay que contar hasta ese 0. "42" ocupa 3 bytes: '4', '2' y '\0'.

ft_strlen es exactamente ese recuento, y ft_putstr usa la misma condición, while (str[i]), para saber cuándo dejar de escribir.

write, descriptores de fichero, stdout y stderr

write(fd, dirección, n) escribe n bytes a partir de una dirección de memoria en el destino fd. El fd (descriptor de fichero) es un número pequeño que identifica un destino abierto: todo programa empieza con el 0 (entrada estándar, stdin), el 1 (salida estándar, stdout) y el 2 (salida de errores, stderr). Se declara en <unistd.h>.

En C 04 siempre es write(1, &c, 1): un byte cada vez por stdout. Por eso ft_putnbr no puede escribir el número 4 directamente: tiene que tener el carácter '4' en una variable y pasar su dirección.

Llamada al sistema (syscall)

Un programa no puede tocar la pantalla ni el disco por su cuenta: se lo pide al núcleo del sistema operativo (el kernel) mediante una llamada al sistema. write es una envoltura casi directa de la syscall del mismo nombre. printf, en cambio, es una función de biblioteca: da formato al texto, lo guarda en un búfer y al final acaba llamando a write.

Cada syscall cuesta mucho más que una función normal, así que escribir de byte en byte, como hace ft_putstr, es lento. Para la piscine da igual; importa más adelante.

ASCII y el truco de '0'

Para el ordenador cada carácter es un número según la tabla ASCII: '0' es 48, '1' es 49… hasta '9', 57. Como los dígitos van seguidos, el valor de un dígito escrito es c - '0', y el carácter de un valor de 0 a 9 es v + '0'.

ft_atoi usa lo primero (str[i] - '0') y ft_putnbr lo segundo (n % 10 + '0'). En las versiones en base ya no vale: los símbolos de "0123456789ABCDEF" no son consecutivos en ASCII ('9' es 57 y 'A', 65), así que el valor se saca de la posición en la cadena base.

Espacios en blanco (isspace)

Para la biblioteca de C son «blancos» seis caracteres: el espacio (32) y cinco de control, del 9 al 13: tabulador \t, salto de línea \n, tabulador vertical \v, salto de página \f y retorno de carro \r. Es lo que devuelve verdadero en isspace.

La atoi de verdad salta todos los que haya al principio, y por eso ft_atoi empieza con while (str[i] == ' ' || (str[i] >= 9 && str[i] <= 13)).

Números y su representación

Notación posicional y base

En la notación posicional, cada dígito vale su símbolo multiplicado por la base elevada a su posición, contando desde la derecha y desde 0. En base 10, 423 es 4·10² + 2·10¹ + 3·10⁰. La base es cuántos símbolos distintos hay; con base b, los dígitos van de 0 a b − 1.

Sacar los dígitos es hacer lo contrario: n % b es la última cifra y n / b es el resto del número sin ella. 423 % 10 = 3 y 423 / 10 = 42. En ft_putnbr_base la base es una cadena: su longitud es b, y el símbolo del dígito d es base[d].

Binario, octal y hexadecimal

Son las bases 2, 8 y 16, las que más se usan en informática porque encajan con los bits: un dígito octal son 3 bits y uno hexadecimal, 4. En hexadecimal, después del 9 vienen A (10) a F (15).

El 42 es 101010 en binario, 52 en octal y 2a en hexadecimal. ft_putnbr_base(42, "01") imprime 101010, y ft_putnbr_base(42, "poneyvif"), una base octal con letras, imprime vn: la v está en la posición 5 y la n en la 2. Ojo con el ejemplo del enunciado en español, "poneyguay": tiene 9 símbolos y la y repetida, así que ni es octal ni es una base válida, y ft_putnbr_base no imprime nada con ella.

Complemento a dos y rango de int

Un int son 32 bits. Para guardar negativos, casi todas las máquinas usan el complemento a dos: el bit más alto pesa −2³¹ en vez de +2³¹. Así, el rango va de −2147483648 a 2147483647: hay un negativo más que positivos, porque el 0 ocupa uno de los «no negativos».

Esa asimetría es la causa de todo el cuidado con el mínimo en ft_putnbr y ft_putnbr_base: el máximo positivo es 2147483647, así que 2147483648 no cabe.

INT_MIN

Es el int más pequeño, −2147483648, definido en <limits.h>. Su opuesto, 2147483648, no cabe en un int, así que -nb con nb = INT_MIN desborda.

Hay dos formas de esquivarlo, y el módulo tiene las dos: pasar a long antes de cambiar el signo (el código de esta página) o tratar ese valor aparte, que es lo que hace el repo: ft_putnbr escribe "-2147483648" tal cual, y ft_putnbr_base calcula la primera parte con -(nbr + b), que sí cabe. Las dos imprimen bien -2147483648 y, en hexadecimal, -80000000.

Desbordamiento (overflow)

Pasa cuando el resultado de una operación no cabe en el tipo donde se guarda. Con enteros con signo, como int, el estándar de C no dice qué pasa: es comportamiento indefinido. En la práctica suele «dar la vuelta» al otro extremo del rango, pero no se puede contar con ello.

En ft_atoi("2147483648"), result * 10 + dígito se pasa del máximo en la última cifra. En esta máquina salió −2147483648, igual que la atoi de glibc, pero es pura casualidad: el man atoi no define qué devuelve cuando el número no cabe.

Comportamiento indefinido

Es lo que el estándar de C llama a las situaciones para las que no promete nada: desbordar un int con signo, leer fuera de un array, leer a través de NULL… El programa puede funcionar, dar basura o morir, y puede cambiar con otro compilador o con otras opciones de optimización. «A mí me funciona» no demuestra nada.

Por eso -INT_MIN no se «arregla» comprobando el resultado después: hay que evitar llegar a calcularlo.

long y pasar a un tipo más ancho

long es un entero que, en Linux y macOS de 64 bits, ocupa 8 bytes y llega hasta 9223372036854775807. (En Windows ocupa 4, como int: no es universal.) Al asignar un int a un long (n = nb;) el valor se conserva y a partir de ahí las cuentas se hacen con el tipo grande.

En ft_putnbr de esta página, con nb = INT_MIN, n = -n da 2147483648, que en un long cabe de sobra.

Técnicas

Recursión

Una función es recursiva cuando se llama a sí misma con un problema más pequeño, y tiene un caso base en el que deja de llamarse. Cada llamada espera a que termine la siguiente antes de seguir con lo que tenía después.

ft_putnbr(423) llama a ft_putnbr(42), que llama a ft_putnbr(4); esta ya no se llama (4 < 10, el caso base), imprime 4 y vuelve. Entonces la de 42 imprime 2 y la de 423, 3. Los dígitos salen de izquierda a derecha aunque se calculen de derecha a izquierda. Para un int hay como mucho 10 niveles en base 10 y 32 en base 2.

Acumular por posición (método de Horner)

Para leer un número cifra a cifra de izquierda a derecha no hace falta saber cuántas cifras tiene: basta con multiplicar lo acumulado por la base y sumar la cifra nueva. Leer "423": 0·10 + 4 = 4, 4·10 + 2 = 42, 42·10 + 3 = 423. Es la regla de Horner, la forma de evaluar un polinomio con el mínimo de multiplicaciones.

ft_atoi lo hace con 10 (result * 10 + dígito) y ft_atoi_base con la longitud de la base. ft_atoi_base("ff", "0123456789abcdef"): 0·16 + 15 = 15, 15·16 + 15 = 255.

Validar la entrada

Comprobar que lo que te pasan tiene sentido antes de usarlo. Una base con símbolos repetidos no sirve (en "0100", ¿el 0 vale 0 o 2?), una de un solo símbolo no puede escribir más que ceros, y una con + o - chocaría con los signos.

Los dos ejercicios en base validan primero y, si la base no vale, no hacen nada: ft_putnbr_base(42, "0+") no imprime nada y ft_atoi_base("12", "0") devuelve 0.

Funciones static

Una función declarada static solo existe dentro de su archivo: el resto del programa no la ve. Sirve para las funciones de ayuda, para que no choquen con otra del mismo nombre en otro archivo.

El código de esta página usa static int ft_base_ok. En el repo, ft_base_ok no es static ni en ex04 ni en ex05, y al enlazar los dos archivos juntos gcc falla con multiple definition of `ft_base_ok'. La Moulinette compila cada ejercicio por separado y no lo nota, pero en un proyecto con varios archivos sí pasaría.

Coste lineal, O(n)

Un algoritmo es O(n) cuando su trabajo crece en proporción al tamaño de la entrada n: el doble de largo, el doble de tiempo. Es el coste de recorrer algo una vez.

ft_strlen es O(n) en la longitud de la cadena, porque la única forma de saberla es contar hasta el \0. Por eso llamarla en la condición de un bucle que recorre la misma cadena convierte un recorrido O(n) en O(n²).

La entrega

Moulinette

El corrector automático de 42. Compila cada ejercicio con cc -Wall -Wextra -Werror junto a su propio main, lo ejecuta y compara el resultado con el esperado. Es muy estricta y no se discute con ella: un warning, una salida distinta, un segfault o un cuelgue y el ejercicio cuenta como fallado. Según el enunciado, primero te corrigen compañeros de la piscine y después la Moulinette.

Como pone su propio main, el tuyo tiene que estar comentado o quitado.

Norma y norminette

La Norma es el estilo obligatorio en 42: funciones de 25 líneas como mucho, 5 funciones por archivo, nada de for ni de switch, declaraciones al principio… norminette la comprueba; si falla, la nota es 0 aunque el código funcione.

Por las 25 líneas, ft_putnbr_base y ft_atoi_base se parten en funciones de ayuda. El enunciado pide pasarla con -R CheckForbiddenSourceHeader; los seis archivos del repo dan OK!.

ex00ft_strlen

Prototipo: int ft_strlen(char *str)

Contar y devolver el número de caracteres de una cadena.

int	ft_strlen(char *str)
{
	int	i;

	i = 0;
	while (str[i])
		i++;
	return (i);
}

Se cuenta avanzando hasta el \0. El índice donde está el terminador coincide con la longitud, porque contamos desde 0. Es la operación más básica sobre cadenas y aparece, explícita o disimulada, en casi todos los demás ejercicios de la piscina.

Concepto — medir cuesta O(n). En C, saber la longitud de una cadena no es gratis: hay que recorrerla entera cada vez. Por eso escribir while (i < strlen(s)) dentro de un bucle es un clásico error de rendimiento (recorre la cadena en cada vuelta). Lenguajes como Python o Rust guardan la longitud aparte justamente para no pagar este peaje.

ex01ft_putstr

Prototipo: void ft_putstr(char *str)Autorizada: write

Imprimir una cadena por la salida estándar.

void	ft_putstr(char *str)
{
	int	i;

	i = 0;
	while (str[i])
	{
		write(1, &str[i], 1);
		i++;
	}
}

Se escribe carácter a carácter con write sobre el descriptor 1 (la salida estándar). Se pasa &str[i] porque write quiere una dirección y un número de bytes; aquí, un byte cada vez.

Concepto — write es la salida de verdad. Sin printf (que no está autorizado), toca hablar directamente con el kernel vía la syscall write. El 1 es stdout; el 2, stderr. Todo lo que imprime tu programa acaba, tarde o temprano, en una llamada como esta: printf no es más que una capa cómoda por encima.

ex02ft_putnbr

Prototipo: void ft_putnbr(int nb)Autorizada: write

Mostrar un entero, cubriendo todo el rango de int (incluido el mínimo).

void	ft_putnbr(int nb)
{
	long	n;
	char	c;

	n = nb;
	if (n < 0)
	{
		write(1, "-", 1);
		n = -n;
	}
	if (n >= 10)
		ft_putnbr(n / 10);
	c = n % 10 + '0';
	write(1, &c, 1);
}

Se copia nb a un long antes de nada. La recursión imprime los dígitos en orden: para 423, la llamada con 42 ocurre antes de imprimir el 3, así que las centenas y decenas salen primero. La conversión dígito→carácter es el + '0' que veíamos en C02, ahora en su uso real.

Concepto — INT_MIN, el número maldito. El rango de un int es asimétrico: de −2147483648 a +2147483647. El mínimo no tiene positivo representable, así que -n con n = INT_MIN se desborda (comportamiento indefinido). El truco de copiar a long —que sí tiene sitio para 2147483648— esquiva la trampa. Reconocer este caso límite es un rito de paso: casi todo el mundo lo suspende la primera vez.

ex03ft_atoi

Prototipo: int ft_atoi(char *str)

Convertir el principio de una cadena en un int: espacios iniciales opcionales, una tanda de signos +/-, y luego dígitos hasta el primer carácter no numérico. Con varios -, el resultado es negativo si su número es impar.

int	ft_atoi(char *str)
{
	int	i;
	int	sign;
	int	result;

	i = 0;
	sign = 1;
	result = 0;
	while (str[i] == ' ' || (str[i] >= 9 && str[i] <= 13))
		i++;
	while (str[i] == '+' || str[i] == '-')
	{
		if (str[i] == '-')
			sign = -sign;
		i++;
	}
	while (str[i] >= '0' && str[i] <= '9')
	{
		result = result * 10 + (str[i] - '0');
		i++;
	}
	return (result * sign);
}

Tres fases claras: saltar blancos (el espacio 32 y los controles 9–13, que es lo que reconoce isspace), procesar los signos acumulando en sign (cada - lo invierte), y acumular dígitos con result = result * 10 + dígito. Con la entrada " ---+--+1234ab567" hay cinco - (impar) → negativo, y la lectura para en la a: sale -1234.

Concepto — acumular por posición. El corazón, result * 10 + dígito, es la notación posicional en base 10: cada dígito nuevo empuja los anteriores una posición a la izquierda (multiplicar por 10) y se suma el actual. Cambia el 10 por otra base y tienes ex05. Este patrón de «desplazar y sumar» es la máquina universal de leer números.

ex04ft_putnbr_base

Prototipo: void ft_putnbr_base(int nbr, char *base)Autorizada: write

Imprimir nbr en la base descrita por la cadena base, que enumera sus símbolos ("01" = binario, "0123456789ABCDEF" = hexadecimal…). Si la base es inválida —menos de 2 símbolos, con repetidos, o con +/-— no se imprime nada.

static int	ft_base_ok(char *base)
{
	int	i;
	int	j;

	i = 0;
	while (base[i])
	{
		if (base[i] == '+' || base[i] == '-')
			return (0);
		j = i + 1;
		while (base[j])
		{
			if (base[i] == base[j])
				return (0);
			j++;
		}
		i++;
	}
	if (i < 2)
		return (0);
	return (1);
}

static void	ft_put_base(long n, char *base, int len)
{
	if (n >= len)
		ft_put_base(n / len, base, len);
	write(1, &base[n % len], 1);
}

void	ft_putnbr_base(int nbr, char *base)
{
	long	n;
	int		len;

	if (!ft_base_ok(base))
		return ;
	len = ft_baselen(base);
	n = nbr;
	if (n < 0)
	{
		write(1, "-", 1);
		n = -n;
	}
	ft_put_base(n, base, len);
}

Primero se valida la base: rechaza signos, duplicados y longitudes menores que 2. La impresión es la misma recursión que ft_putnbr, pero generalizada: en vez de dividir entre 10 se divide entre len (el número de símbolos), y en vez de + '0' se indexa base[n % len]. El paso a long vuelve a estar por INT_MIN. (ft_baselen, omitida aquí, solo cuenta símbolos de la base.)

Concepto — la base es un parámetro, no una constante. Descubrir que imprimir en decimal, binario o hex es el mismo algoritmo con distinto divisor es una pequeña revelación: la base 10 no tiene nada de especial para la máquina, es una elección humana. Validar la entrada (bases con símbolos repetidos no definen una numeración) enseña además a no fiarse jamás de lo que te pasan.

ex05ft_atoi_base

Prototipo: int ft_atoi_base(char *str, char *base)

Como ft_atoi, pero leyendo str en la base dada. Si la base es inválida —menos de 2 símbolos, repetidos, o con +, - o espacios— devuelve 0.

static int	ft_index(char c, char *base)
{
	int	i;

	i = 0;
	while (base[i])
	{
		if (base[i] == c)
			return (i);
		i++;
	}
	return (-1);
}

static int	ft_convert(char *str, char *base, int len)
{
	int	i;
	int	sign;
	int	result;

	i = 0;
	sign = 1;
	result = 0;
	while (str[i] == ' ' || (str[i] >= 9 && str[i] <= 13))
		i++;
	while (str[i] == '+' || str[i] == '-')
	{
		if (str[i] == '-')
			sign = -sign;
		i++;
	}
	while (ft_index(str[i], base) >= 0)
	{
		result = result * len + ft_index(str[i], base);
		i++;
	}
	return (result * sign);
}

int	ft_atoi_base(char *str, char *base)
{
	if (!ft_base_ok(base))
		return (0);
	return (ft_convert(str, base, ft_baselen(base)));
}

La estructura calca a ft_atoi (blancos, signos, dígitos), con dos cambios: el valor de un símbolo ya no es str[i] - '0' sino su posición en la base (ft_index), y la acumulación multiplica por len en vez de por 10. El bucle de dígitos se detiene en cuanto aparece un carácter que no pertenece a la base (ft_index devuelve −1). Aquí la base inválida también incluye espacios, porque un espacio como símbolo chocaría con el salto de blancos. (ft_base_ok y ft_baselen son las del ejercicio anterior, con el añadido del rechazo de espacios.)

Concepto — el símbolo y su valor. En hex, 'F' «vale» 15 porque ocupa la posición 15 de "0123456789ABCDEF". Separar el glifo (lo que se escribe) de su valor (lo que representa) mediante una tabla de posiciones es una idea que reaparece por todas partes: codificaciones, tokenizadores, intérpretes. ft_atoi_base es su forma más pequeña y honesta.

?Preguntas probables de la evaluación

Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección donde está explicado a fondo. Están agrupadas en: defender el código, casos límite, y Moulinette y Norma. Antes de mirar la respuesta, intenta contestar tú.

Defender el código

¿Cómo consigue ft_putnbr imprimir las cifras en orden?

Con recursión: antes de escribir la última cifra (n % 10) se llama a sí misma con el resto del número (n / 10), así que las cifras de la izquierda salen antes. Para cuando n < 10: es el caso base. → recursión, ex02

¿Qué devuelve ft_atoi(" ---+--+1234ab567")?

-1234. Salta el espacio, cuenta cinco - (impar, así que negativo), lee 1234 y para en la a: lo que viene después no se mira. → ex03

¿Qué cambia entre ft_putnbr y ft_putnbr_base?

Solo dos cosas: se divide entre la longitud de la base en vez de entre 10, y el carácter de cada cifra es base[n % len] en vez de n % 10 + '0'. El algoritmo es el mismo. → base, ex04

¿Por qué las funciones de ayuda son static?

Para que solo existan en su archivo. Si no lo son, dos archivos con una función del mismo nombre no se pueden enlazar juntos: con los ft_base_ok de ex04 y ex05 del repo, gcc da multiple definition. → static

Casos límite

¿Qué pasa con ft_putnbr(-2147483648)?

Es el caso que más se prueba. -nb no cabe en un int (el máximo es 2147483647), así que hay que evitarlo: o pasar a long antes de cambiar el signo, como el código de la página, o tratarlo aparte, como el repo. Las dos versiones imprimen -2147483648. → INT_MIN, ex02

¿Y si a ft_atoi le pasas un número que no cabe en un int?

El resultado no está definido, ni en la tuya ni en la de la libc: el man atoi no lo cubre. Con "2147483648" las dos devolvieron -2147483648 en esta máquina, pero es un desbordamiento de int con signo. → overflow

¿Qué bases son inválidas y qué haces con ellas?

Vacía o de un solo símbolo, con símbolos repetidos, o con + o -. En ft_atoi_base, además, con espacios. ft_putnbr_base no imprime nada y ft_atoi_base devuelve 0. → validar, ex04, ex05

¿Por qué en ft_atoi_base la base no puede tener espacios ni signos?

Porque ft_atoi_base salta blancos y lee signos antes de las cifras: si el espacio o el - fueran también cifras, no se sabría qué es cada uno. El repo rechaza también los blancos del 9 al 13, por la misma razón. → blancos, ex05

Moulinette y Norma

¿Por qué no usas printf?

Porque no está autorizada: solo write en ex01, ex02 y ex04, y ninguna en ex00, ex03 y ex05. write escribe bytes, así que cada cifra hay que convertirla antes en carácter. → write, ex01

¿Puedo dejar el main de pruebas?

Solo comentado, como en el ft_putnbr.c del repo. La Moulinette compila con su propio main y dos no enlazan. → Moulinette

¿Por qué ft_atoi_base está partida en varias funciones?

Por la Norma: una función no puede pasar de 25 líneas, y validar la base, buscar el índice de un símbolo y convertir no caben juntos. Con 5 funciones por archivo como máximo, hay sitio de sobra. → Norma, ex05