9.1. Subconjunto de una lista¶

Dadas dos listas L1 y L2 se trata de comprobar si L1 es un subconjunto de la lista L2.

def esSubconjunto(L1, L2):
    '''Asume L1, L2 listas
       Devuelve True si todos los elementos de L1 están en L2
       y False en caso contrario'''
    for e in L1:
        if not e in L2:
            return False
    return True

print(esSubconjunto([3,5,7], range(10)))
print(esSubconjunto([3,5,17], range(10)))

True
False

9.2. Intersección de listas¶

Dadas dos listas L1 y L2 se trata de determinar la lista de los elementos que están en las dos listas.

def interseccion(L1,L2):
    '''Asume L1, L2 listas
       Devuelve lista con elementos comunes'''
    l = []
    for e in L1:
        if e in L2:
            l.append(e)
    return l

print(interseccion(range(10), range(8,20)))

[8, 9]

O con list comprehensions.

def interseccion(L1,L2):
    '''Asume L1, L2 listas
       Devuelve lista con elementos comunes'''
    return [ e for e in L1 if e in L2 ]

print(interseccion(range(10), range(8,20)))

[8, 9]

9.3. Powerset¶

Dada una lista L, se define su powerset como el conjunto de todas las posibles combinaciones de elementos que podemos hacer con los elementos de L. Por ejemplo, para la lista [1, 2] su powerset sería [], [1], [2], [1,2].

Una posible forma de modelar el problema es asociando un bit a cada elemento de L. Si el bit está a 0 significa que ese elemento no se toma, si está a 1, significa que sí se toma. Así el ejemplo anterior podría representarse por los números binarios 00, 01, 10, 11 (en decimal 0, 1, 2, 3). Es decir, todos los posibles valores de un número de 2 bits. Y todos los valores posibles de números de n bits son range(2**n).

def genPowerset(L):
    '''Asume L una lista
       Devuelve una lista de listas con todas las posibles
       combinaciones de los elementos de L'''
    powerset = []
    for i in range(0, 2**len(L)):
        subset = []
        for j in range(len(L)):
            if isBitSet(i,j):
                subset.append(L[j])
        powerset.append(subset)
    return powerset

Ya solo queda la función isBitSet(n, bit), que determina si determinado bit está a 0 o a 1 en un número n. Para ello podemos crear un número que solo tiene el bit deseado a 1 (1<<bit) y hacer una operación and bit a bit con n. El resultado será 0 si el bit es 0 o bien 1<<bit si el bit es 1.

def isBitSet(n, bit):
    return 0 != n & (1<<bit)

Si te resulta complicado el uso de las operaciones de bits lee en detalle la segunda parte de este documento.

10.1. Sistemas de numeración posicionales¶

El ordenador trabaja con números almacenados en bits. Cada bit solo puede almacenar un 0 o un 1. Por tanto si queremos almacenar un número más grande tenemos que guardar más de un bit. Al guardarlos de esta forma se dice que son codificados en binario. Así, por ejemplo, un 2 se almacenaría como un 1 en un bit y un 0 en otro. Éstos son todos los números que podemos representar con 2 bits:

Es fácil calcular lo que vale cada valor representado en un conjunto de n bits, siendo \(b_0\) el valor del bit más a la derecha y \(b_{n-1}\) el valor del bit más a la izquierda.

$ v = :raw-latex:`\sum`:raw-latex:`\limits`_{i=0}^{n-1} b_i :raw-latex:`cdot `2^i $

Puede apreciarse que ésto es completamente análogo al valor de un número cualquiera a partir de sus dígitos decimales \(d_i\):

$ v = :raw-latex:`\sum`:raw-latex:`\limits`_{i=0}^{n-1} d_i :raw-latex:`cdot `10^i $

Es decir, que la codificación binaria no es más que otra posible representación del mismo número, pero que utiliza la base 2 en lugar de la base 10. Cada cifra puede vales 0 o 1, en lugar de 0 a 9.

En ambos casos se trata de un sistema de representación posicional, y cuando hay duda suele representarse poniendo la base como sufijo:

$ 1011_2 = 11_{10} $

Por ejemplo:

Las propiedades de un número binario son análogas a la de un número decimal, pero usando la base 2 en lugar de la 10. Por ejemplo, dividir por 2 equivale a quitar el dígito binario menos significativo, multiplicar por 2 equivale a añadir un cero a la derecha.

10.2. Conversiones de base¶

Pasar de un número binario a su valor decimal se puede hacer directamente con la fórmula mencionada anteriormente:

$ v = :raw-latex:`\sum`:raw-latex:`\limits`_{i=0}^{n-1} b_i :raw-latex:`cdot `2^i $

Cada dígito tiene un peso de \(2^i\) y simplemente hay que sumar los pesos de los dígitos que son 1. El peso del bit más a la derecha (bit menos significativo) es 1, el que está inmediatemente a la izquierda de éste es 2, el siguiente 4, el siguiente 8, etc. Por ejemplo \(0101_2\) sería \(1 + 4 = 5\). Sumamos los pesos del bit 0 o bit menos significativo y el bit 2.

Pasar de un número decimal a su correspondiente representación binaria se puede hacer dividiendo sucesivamente por 2 y tomando los restos en orden inverso. Por ejemplo:

Y tomando los restos en orden inverso obtenemos \(1111000_2\).

10.3. Números con signo¶

Recuerda que la memoria de un ordenador solo puede guardar 0 o 1 en cada una de sus celdas elementales (bits). Entonces ¿cómo almacenamos el signo de los números negativos? Está claro que tenemos que guardarlo como un 0 o como un 1. Hay varias formas de hacerlo, veamos las más frecuentes.

10.4. Operadores de bits¶

Para manipular bits de forma independiente en Python se utilizan una serie de operadores que realizan operaciones lógicas bit a bit. Se realiza la operación lógica con el bit 0 de ambos argumentos y su resultado se representa en el bit 0 del resultado, en paralelo se realiza la misma operación con el bit 1 de ambos argumentos y su resultado se representa en el bit 1 del resultado, etc.

Además existe un par de operadores que permiten multiplicar o dividir por 2 desplazando un bit a la derecha o a la izquierda, igual que haríamos para multiplicar o dividir por 10 en un número expresado en decimal.

Es muy habitual que el programador primerizo no sepa cuándo debe emplear cada uno de estos operadores. Para intentar paliar el problema vamos a dar algunos consejos generales.

Los operadores lógicos de bits (&, | y ^) pueden entenderse como funciones que alteran un valor (el primer parámetro) de acuerdo a un parámetro de ajuste (el segundo parámetro).

Así el operador & (se lee AND) sirve para poner ceros, el operador | (se lee OR) sirve para poner unos, y el operador ^ (se lee XOR) sirve para invertir bits. El operador ~ (se lee NOT) es un caso especial del operador ^ en el que se invierten todos los bits (~0 es un valor con todo unos, y ~x equivale a x ^ ~0). Veamos algunos ejemplos.

Supongamos que tenemos una variable v con un valor arbitrario.

v = 85

En ocasiones tendremos necesidad de quedarnos solo con algunos bits y poner el resto a cero. Por ejemplo, supongamos que queremos quedarnos con los 4 bits menos significativos. En ese caso tendremos que poner ceros en el resto de los bits de v, es decir, tenemos que usar un & con un valor que tenga a cero todos los bits que queramos poner a cero y a uno todos los bits que queramos mantener como estaban. En nuestro caso:

print(v & 0b1111)

5

Nótese que para escribir un número en binario en Python se utiliza el prefijo 0b. También podemos imprimir su representación binaria usando la función bin.

print(bin(v), bin(v & 0b1111))

0b1010101 0b101

Supongamos ahora que queremos poner a uno los tres bits menos significativos, independientemente del valor que tenga v en un caso concreto. Para poner unos se utiliza el operador | con un valor que tenga a uno todos los bits que queremos dejar a uno, y a cero todos los bits que no queremos que cambien.

print(bin(v), bin(v | 0b111))

0b1010101 0b1010111

Supongamos ahora que queremos invertir los bits 3 a 6, ambos incluidos. Para invertir bits se utiliza el operador ^ con un valor que tenga a uno todos los bits que se desean invertir, y a cero los que no se quieren tocar.

print(bin(v), bin(v ^ 0b1111000))

0b1010101 0b101101

Las operaciones de desplazamiento también merecen la pena detenerse un poco. El desplazamiento a la izquierda es añadir ceros a la derecha en la representación binaria. Es decir, equivale a multiplicar por 2 tantas veces como diga el segundo argumento.

print(bin(v), bin(v << 3))

0b1010101 0b1010101000

El desplazamiento a la derecha es más interesante. Como cabe esperar hace la operación complementaria al desplazamiento a la izquierda. Es decir, divide por 2 tantas veces como diga el segundo argumento. En números positivos es equivalente a eliminar los bits menos significativos y rellenar con ceros a la izquierda.

print(bin(v), bin(v >> 3))

0b1010101 0b1010

Con números negativos en complemento a 2 la división por 2 funciona de forma similar, con la única salvedad de que en lugar de introducir un cero a la izquierda habría que introducir un 1 para mantener el signo del número. Prueba con algún ejemplo para comprobarlo.

Lo interesante de ésto es que puede generalizarse, la operación de desplazamiento a la derecha consiste en eliminar los bits menos significativos y reemplazarlos por el valor del bit de signo en la izquierda. Sin embargo si lo intentamos imprimir directamente no encontraremos la solución esperada.

v = -52
print(bin(v), bin(v >> 3))

-0b110100 -0b111

El tamaño de los enteros en Python no es fijo, por lo que el bit de signo se trata de forma especial. Sin embargo en complemento a 2 el bit de signo se repite en todos los bits más significativos mientras el resto del número quepa en los restantes bits. Por tanto podemos obtener la representación seleccionando exclusivamente una cantidad razonable de bits menos significativos. Por ejemplo, los 32 bits menos significativos. Para seleccionar estos bits tenemos que poner ceros en los restantes bits. Para poner ceros se usa un AND con un valor que corresponda a 32 unos. Los 32 unos pueden obtenerse como 2**32 - 1 o como (1<<32) - 1.

v = -52
unos = 2**32 - 1
print(bin(unos))
print(bin(v & unos), bin((v >> 3) & unos))

0b11111111111111111111111111111111
0b11111111111111111111111111001100 0b11111111111111111111111111111001

10.5. Seleccionar bits de un número¶

Un ejercicio interesante es el siguiente. Hacer una función getbits que extrae un rango de bits de un valor que se pasa como argumento.

def getbits(x, primero, n):
    '''Asume x, primero, n enteros, primero >= n - 1
       Devuelve n bits de x a partir de la posición primero'''
    return (x >> (primero + 1 - n)) & ~(~0 << n)

print(bin(getbits(v, 6, 3)))

0b100

Para ver cómo funciona nada mejor que un ejemplo. Veamos qué pasaría si queremos 9 bits a partir del bit 18 del número x.

El valor de primero sería 18, y el valor de n sería 9. El valor de x es irrelevante para entender la función.

Lo primero que tenemos que hacer es desplazar x a la derecha de manera que los bits que queremos se queden en los bits más bajos. Es fácil comprobar que el número de bits a desplazar es primero - n + 1.

A continuación hay que seleccionar los n bits más bajos. Es decir, hay que poner a cero todos los bits del resultado que no sean los n más bajos. Para poner ceros hay que usar el operador & con un valor que tiene n unos en los n bits más bajos (que son los que queremos conservar) y a cero todos los demás.

Hacer un número con n en una expresión simple no es inmediato. Lo más fácil es hacer un número con n ceros en los bits menos significativos y unos en el resto. Eso es tan simple como ~0 << n. Ese número es justo el contrario al que queremos, así que solo tenemos que negarlo otra vez: ~(~0 << n). Ese es el número con el que tenemos que hacer el and bit a bit.