CP-UPV Bootcamp - Capítulo 2

Capítulo 2: Aritmética entera, binaria y bases numéricas

PROBLEMAS DEL CAPÍTULO

Para acceder a los problemas de este capítulo, accede con tu usuario y contraseña a cpupv.contest.codeforces.com. Si no tienes usuario y contraseña, inscríbete aquí.

Introducción

En este capítulo del Bootcamp nos enfocaremos principalmente en las operaciones aritméticas que podemos realizar con los diferentes tipos de datos que hemos explicado previamente.

Contenidos del capítulo

Operaciones básicas
- Suma
- Resta
- Multiplicación
- División
- Módulo
Bases numéricas
- Decimal
- Binario
- Octal
- Hexadecimal
Overflows y underflows
Sistema binario
Otras Operaciones
- pow()
- sqrt()
- log()

Operaciones básicas

Suma

Podemos realizar sumas de cualquier tipo de dato numérico, e incluso mezclando estos tipos de datos:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    int a = 3;
    int b = 9;
    float c = 30.3;
    
    cout << a + b << " es suma de enteros" << endl;
    // 12
    
    cout << a + c << " es una suma de entero y número de coma flotante" << endl;
    // 33.3

    double doblePrecision = 2878.1235;
    long long numLargo = 182391872;
    a = -12234;

    cout << doblePrecision + numLargo + a << " no importa que sumandos escojamos" << endl;
    // 1.82383e+08

    int num1 = 2147483647;
    int num2 = 2147483647;

    cout << num1 + num2 << " aquí hay un problema de overflow" << endl;
    // -2

    long long num3 = 9223372036854775807;
    long long num4 = 9223372036854775807;

    cout << num3 + num4 << " otro problema" << endl;
    // -2

    return 0;
}

Debemos tener en cuenta que se pueden dar overflows, un problema que en muchos casos puede causar más de un dolor de cabeza cuando estamos programando, lo explicaremos más adelante.

Resta

Con la resta ocurre lo mismo que con la suma, podemos mezclar los tipos de datos, siempre y cuando tengamos en cuenta los posibles overflows.

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    long long a = 9223372036854775807;
    int b = 1237123;

    cout << "resta de a - b " << a - b << endl;
    // 9223372036853538684

    b = -b;
    
    cout << "también podemos sumar restando uno de los sumandos pero con el signo cambiado " << a + b << endl;
    // 9223372036853538684

    int c = -2147483647;
    int d = -2147483647;
    
    cout << "resta de c y d " << c + d << " ... something is sus";
    // 2

    return 0;
}

Multiplicación

Podemos realizar la operación de multiplicación con el símbolo *, y también podemos mezclar los tipos de los operandos, como con las operaciones anteriores.

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    int a = 3;
    float b = 3.1415;

    cout << "a * b es: " << a * b << endl;
    // 9.4245

    return 0;
}

Una curiosidad que nos podemos encontrar es que, si por ejemplo necesitamos multiplicar/dividir por potencias de 2, estas operaciones son optimizadas por el compilador para transformarlas en shiftings, cuando es posible, ya que es una operación más rápida que la multiplicación.

División

La división se realiza con el operando /, y también nos podemos encontrar un caso especial, como es el de la división por 0: cuando dividimos entre 0, nos devuelve un valor undefined, ya que no podemos obtener una solución para esta operación.

Además, otro aspecto importante a tener en cuenta es la precisión de las operaciones, ya que podemos obtener un resultado más preciso si usamos un double en vez de un float, pero perdiendo un poco de velocidad.

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {

    int a = 33;
    int b = 30;
    int cociente = a / b;  // La división nos devuelve el cociente de la operación
    
    cout << "a/b = " << cociente << endl;
    // 1

    cout << "a/0 = " << a / 0 << endl; // ERROR!!

    double num1 = 1.0, num2 = 3.0;
    
    // setprecision especifica las cifras decimales que queremos en el resultado
    cout << setprecision(17) << num1 / num2 << endl; 
    // 0.33333333333333331

    return 0;
}

Módulo

Representado con el símbolo % este nos devuelve el resto de una división, o siendo más precisos, el resultado de la operación \(a\ mod\ b = n\), esto último está relacionado con la aritmética modular (haz click aquí para saber más)

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    
    // Muchas veces pedirán que demos un resultado modulo 1000000007, podemos usar:
    const int MOD = 1e9 + 7;  // 1000000007
    
    int a = 1231234;
    int b = 3231876;
    
    cout << (a + b) % MOD << endl;
    // 4463110
    
    return 0;
}

La aritmética modular tiene muchos usos en Programación Competitiva, como por ejemplo prevenir overflows, manejar números o potencias grandes y realizar algoritmos de manera eficiente. Es por ello que dominar la aritmética modular puede ser muy útil a la hora de resolver problemas.

Bases numéricas

Un sistema numérico es el conjunto ordenado de símbolos que se combina para representar cantidades numéricas. Y una base de un sistema numérico es el número de dígitos o símbolos diferentes usados en ese sistema.

Las 4 bases que se explican aquí debajo funcionan de la misma manera: Todos tienen en común el 0, cuando se incrementa en uno este número, ese dígito incrementa en uno hasta que los símbolos se acaban, entonces el dígito a la izquierda (que inicialmente es 0 y no se muestra) se incrementa en uno y el dígito a la derecha de este vuelve a 0.

Decimal (Base 10)

El sistema decimal es el tradicional y el que se nos ha enseñado desde pequeños a todos. Es el más utilizado en todos los lenguajes de alto nivel para representar los números de una forma que podamos entender fácilmente. Se utilizan 10 dígitos para representar todos los números (del 0 al 9)

Los primeros doce números en este sistema son (empezando por 0): \(0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow 9 \rightarrow 10 \rightarrow 11 \rightarrow 12\)

Fíjate como cuando el dígito de la derecha llega a 9, ese dígito se resetea a 0 y el dígito a la izquierda que inicialmente no se muestra pasa a ser 1. Con el resto de bases pasará lo mismo, la única diferencia es el número de símbolos \(n\) que existen antes de resetear un dígito a 0. En el caso de esta base, 10 dígitos.

Binario (Base 2)

El sistema binario es un sistema numérico que representa los números utilizando únicamente dos símbolos, el 0 y el 1. Este sistema es fundamental en los ordenadores, ya que es así como representan no solo los números, sino también toda la información que manejan, todo esta representado internamente en sistema binario.

A la hora de representar números en binario, se hace como una suma de potencias de 2, donde un '1' indica que la correspondiente potencia de 2 se suma y un '0' si esa potencia de 2 no se usa. Podemos ver en el ejemplo:

\(\bf{1}\)	\(\bf{1}\)	\(\bf{0}\)	\(\bf{1}\)
\(2^3\)	\(2^2\)	\(2^1\)	\(2^0\)

\(\bf{1101}\ \)\( = 2^3 + 2^2 + 2^0 = 8 + 4 + 1 = 13\)

También podemos realizar operaciones en binario como la suma, la resta, la multiplicación y la división, pero aparte, podemos realizar operaciones lógicas, como pueden ser el AND, OR, NOT y XOR, que veremos más adelante.

Suma
 (Binario)       (Decimal)
1 + 1  = 10   -> 1 + 1 = 2
0 + 1  = 1    -> 0 + 1 = 1
11 + 1 = 100  -> 3 + 1 = 4

Resta
  (Binario)        (Decimal)
10  - 1   = 1   -> 2 - 1 = 1
110 - 1   = 101 -> 6 - 1 = 5
101 - 100 = 1   -> 5 - 4 = 1

Multiplicación
    101
  x  11
------
    101   (101 * 1)
+  1010   (101 * 1, desplazado una posición a la izquierda)
------
   1111

División
1101 ÷ 10
= 1101 (13 en decimal) ÷ 10 (2 en decimal)
= 110 (6 en decimal) con un resto de 1

Los primeros doce números en este sistema son (empezando por 0): \(0 \rightarrow 1 \rightarrow 10 \rightarrow 11 \rightarrow 100 \rightarrow 101 \rightarrow 110 \rightarrow 111 \rightarrow 1000 \rightarrow 1001 \rightarrow 1010 \rightarrow 1011 \rightarrow 1100\)

Octal (Base 8)

El octal es otro sistema numérico, que en vez de representar los números en base 2 o en base 10, lo hace en base 8. Esto se puede conseguir simplemente usando la representación binaria y agrupando los bits de tres en tres, ya que 2³ es 8, la base de este sistema.

128 en decimal -> 10000000 en binario -> 010 000 000 = 200 en octal
                                                                                    2   0   0
Conversión octal-decimal
135 en octal
1 * 8^2 + 3 * 8^1 + 5 * 8^0
= 64 + 24 + 5
= 93 (en decimal)

Conversión decimal-octal
Se consigue dividiendo entre 8 y poniendo los restos según se van obteniendo
93 en decimal
93 / 8 = 11 resto 5
11 / 8 = 1  resto 3
 1 / 8 = 0  resto 1
Result: 135 (in octal)

Este sistema es conveniente de usar cuando queremos manejar ciertos datos que no están compuestos de tanta información como ocurre con el hexadecimal

Los primeros doce números en este sistema son (empezando por 0): \(0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 10 \rightarrow 11 \rightarrow 12 \rightarrow 13 \rightarrow 14\)

Hexadecimal (Base 16)

El sistema hexadecimal. o de base 16, utiliza, a diferencia del octal, agrupaciones de 4 bits, llegando así a representar 16 valores diferentes. Los símbolos que se utilizan son las cifras del 0 al 9, y a continuación, las letras desde la A hasta la F(inclusive).

(Hexadecimal)    (Decimal)
9 + 9 = 12   -> 9 + 9   = 18
F + 1 = 10   -> 15 + 1  = 16

(Hexadecimal)    (Decimal)
13 - F = 04  -> 19 - 15 = 4
F  - F = 0   -> 15 - 15 = 0

8AF en hexadecimal -> 1000 1010 1111 en binario
8 = 1000 | A = 10(decimal) = 1010(binario) | F = 15(decimal) = 1111(binario)

Decimal a hexadecimal
Se obtiene dividiendo entre 16 y poniendo los restos en orden
255 / 16 = 15 resto 15 (F en hexadecimal)
15 / 16  = 0  resto 15 (F en hexadecimal)
Result: FF (en hexadecimal)

Hexadecimal a decimal
Se consigue multiplicando el valor de cada cifra hexadecimal por la potencia correspondiente de 16
F * 16^1 + F * 16^0
= 15 * 16 + 15 * 1
= 240 + 15
= 255 (en decimal)

El hexadecimal es uno de los sistemas de representación más usados, principalmente en los componentes electrónicos para representar información, debido a que, basándose en la simplicidad del binario, podemos obtener un mayor rango de valores para representar, sin recurrir a un sistema más complejo de implementar como podría ser el decimal. Por ejemplo, la tabla ASCII puede representarse con la notación hexadecimal y de esta forma representar los caracteres.

Para la Conversión entre los sistemas numéricos mencionados, podemos realizar cualquier Conversión intermedia, por ejemplo, para pasar de hexadecimal a binario, podemos convertir los valores directamente, o convertir primero a binario y después a decimal.

Los primeros 18 números en este sistema son (empezando por 0): \(0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow 9 \rightarrow A \rightarrow B \rightarrow C \rightarrow D \rightarrow E \rightarrow F \rightarrow 10 \rightarrow 11\)

Overflows y underflows

Los overflows y underflows en las operaciones ocurren debido a que, debido a la operación que se realiza y los operandos que se utilizan, se supera el límite superior o inferior del tipo de dato resultado de la operación, por lo que el resultado de esta no tendrá nada que ver con lo que esperábamos.

Uno de los casos que más nos suele ocurrir al empezar en programación competitiva es que no verificamos si nuestras operaciones producirán un overflow/underflow, y en general, esto se puede resolver simplemente cambiando el tipo de dato a uno de 64 bits, como por ejemplo, de int a long long.

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    int a = 2147483647;
    int b = 2147483647;
    cout << a + b << endl; // El resultado es -2

    long long num1 = 2147483647;
    long long num2 = 2147483647;
    cout << num1 + num2 << endl; // Ahora da 4294967294

    return 0;
}

Sistema binario y operaciones lógicas

Como hemos mencionado previamente, el sistema binario nos da mucho juego para realizar diferentes operaciones, por ejemplo, operaciones lógicas con los bits como pueden ser las siguientes:

AND

La operación AND( & ) es 1 si ambos operandos son 1.

\(A\)	\(B\)	\(A \& B\)
0	0	0
0	1	0
1	0	0
1	1	1

Podemos aplicar la operación AND a más de un bit, y esto nos puede servir, por ejemplo, para enmascarar bits específicos de estas cadenas y comprobar que ciertas condiciones se cumplen, o incluso, en la generación de subsets mediante una máscara.

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    
    int n = 12489;
    int bitActivadoMasBajo = n & -n;
    // Devuelve el bit activo menos significativo, en este caso, el primero
    
    // Si es mayor que cero, y solamente haya un bit puesto a 1
    bool esPotenciaDeDos = x > 0 && (x & (x - 1)) == 0;
    
    // Si el bit de la derecha del todo está puesto a 0
    bool esPar = (x & 1) == 0;

    return 0;
}

OR

De la misma forma, la operación lógica OR( | ) devuelve 1 cuando cualquiera de los dos operandos sea 1.

\(A\)	\(B\)	\(A \| B\)
0	0	0
0	1	1
1	0	1
1	1	1

Esta operación también puede ser bastante útil, y entre sus aplicaciones podemos encontrar el activar bits específicos de una secuencia de bits, o la generación de todas las combinaciones de un conjunto.

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    int num = 33 ;    //100001
    num |= (1 << 2);  //100101

    int n = 23;
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = i + 1; j < (1 << n); ++j) {
            int combinacion = i | j;
            // Proceso de combinacion
        }
    }

    char c = 'A';
    char mayusculaAMinuscula = c | ox20;
    // Al cambiar el sexto bit a 1, añadimos 32 al valor numérico, y si nos fijamos
    // en la tabla ASCII, la diferencia entre una mayúscula y su minúscula son 32

    return 0;
}

NOT

La operación NOT( ~ ) invierte todos los bits del operando introducido, y podemos utilizarlo para encontrar el complemento de una cadena de bits, o poner ciertos bits a 0.

\(A\)	\(\sim A\)
0	1
1	0

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    int a = 37; // 100101
    int b = ~a;
    cout << "El complemento de a es: " << b; // 011010 = 26

    int num = 0xFF;  // Binario: 11111111
    int mascara = ~((1 << 4) - 1);  // Binario: 11110000
    int result = num & mascara;  // Resultado: 11110000
    
    return 0;
}

XOR

Aunque menos usada en general, la operación XOR( ^ ) también tiene sus funciones. Esta se basa en que, si los dos operandos son diferentes, devuelve 1, mientras que si son iguales, devuelve 0.

\(A\)	\(B\)	\(A ^\wedge B\)
0	0	0
0	1	1
1	0	1
1	1	0

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    int a = 37; // 100101
    int b = 32; // 100000
    int c = a ^ b; // 000101

    // También puede usarse para hacer el swap entre dos variables sin usar auxiliares
    int a = 5, b = 7; // a = 101, b = 111
    a = a ^ b;  // Paso 1 a = 010
    b = a ^ b;  // Paso 2 b = 101
    a = a ^ b;  // Paso 3 a = 111

    return 0;
}

Shifting

El shifting lógico se basa en el desplazamiento de todos los bits de una cadena hacia la izquierda o la derecha una cantidad de x bits, siempre y cuando tengamos en cuenta que no es cíclico. Por un lado se introducirán siempre 0 y por el otro se pierden los bits. Se puede utilizar para realizar multiplicaciones/divisiones por potencias de dos, proveer un bit específico para aplicarlo en alguna función…

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const *argv[]) {
    int a = 9;      //001001
    int b = a << 2; //100100 = 36
    cout << a == (b >> 2) << endl;   // true 

    int mascara = 1 << 30; // 0100 0000 0000 0000 0000 0000 0000 0000
    int c = 32;            // 0010 0000
    cout << (c << mascara) << endl;   // 0

    return 0;
}

Hemos de tener en cuenta que el shifting en números signed y unsigned es diferente, ya que si desplazamos los bits de un número negativo perderíamos el signo.

Consideraciones

A la hora de realizar operaciones, podemos utilizar estos operadores para operar y asignar el resultado en variables.

Expresion	Resultado
y += x	y = y + x
y -= x	y = y - x
y *= x	y = y * x
y /= x	y = y / x
y %= x	y = y % x
y >>= x	y = y >> x
y <<= x	y = y << x
y &= x	y = y & x
y \|= x	y = y \| x
y ^= x	y = y ^ x

Otras operaciones

Existen funciones en C++ que nos permiten hacer operaciones más complejas, como pueden ser las siguientes:

pow()

pow(base, exponente), provista por la librería <cmath> nos permite calcular potencias de los números que le proporcionemos. Pudiendo devolver double, float o long double.

#include <math.h>

cout << pow(3, 4) << endl;
// 81

cout << pow(32.01, 1.54) << endl;
// 208.036691

Para ciertos valores, esta función dará lugar a errores, por eso debemos tener en cuenta que:

Base < 0, exponente ≠ entero → Error de dominio
Base == 0, exponente < 0 → Error de dominio
Puede darse range error si el resultado es demasiado grande/pequeño para ser representado por el tipo de dato utilizado.

sqrt()

Aceptando también como argumentos double, float o long double, la función sqrt(num) no tiene mucho misterio, calcula la raíz cuadrada del tipo de dato que le proporcionemos, y, como es obvio, nos dará errores si tratamos de buscar la raíz cuadrada de un número negativo.

#include <math.h>

cout << srqt(23) << endl;
// 4.79583

cout << sqrt(-1) << endl;
// -nan

log()

Para calcular logaritmos, nos encontramos con dos funciones que se diferencian por la base del logaritmo: log(), y log10().

log() calcula logaritmos naturales, mientras que log10() calcula logaritmos en base 10.

Debemos tener en cuenta que ambas funciones darán lugar a error si utilizamos números negativos, ya que con esas bases es imposible obtener números negativos.

#include <math.h>

cout << log(5.5) << endl;
// 1.704748

RECUERDA: Todas estas funciones no pueden ser precisas al 100% en todos los casos, ya que tenemos una cantidad limitada de bits para la representación de números.