1.4: Representación binaria de enteros positivos

Agrupación por dos

Recordemos que el conjunto de enteros positivos,\(\mathbb{P}\text{,}\) es Los enteros\(\{1, 2, 3, . . . \}\text{.}\) positivos se utilizan naturalmente para contar las cosas. Hay muchas formas de contar y muchas formas de registrar, o representar, los resultados del conteo. Por ejemplo, si quisiéramos contar quinientas veintitrés manzanas, podríamos agrupar las manzanas por decenas. Habría cincuenta y dos grupos de diez con tres manzanas solas sobrantes. Los cincuenta y dos grupos de diez podrían ser puestos en cinco grupos de diez decenas (cientos), con dos decenas sobrantes. Los cinco cientos, dos decenas, y tres unidades se registra como 523. Este sistema de conteo se llama sistema posicional base diez, o sistema decimal. Es bastante natural que hagamos agrupamientos por decenas, cientos, miles,\(\dots\) ya que es el método que todos usamos en la vida cotidiana.

El término posicional se refiere al hecho de que cada dígito en la representación decimal de un número tiene una significación basada en su posición. Por supuesto esto significa que la reordenación de los dígitos cambiará el número que se está describiendo. Es posible que hayas aprendido de los sistemas de numeración en los que la posición de los símbolos no tiene ningún significado (por ejemplo, el antiguo sistema egipcio). La mayoría de estos sistemas son simplemente curiosidades para nosotros ahora.

El sistema de números binarios difiere del sistema numérico decimal en que las unidades se agrupan por dos, cuatro, ochos, etc. Es decir, los tamaños de grupo son potencias de dos en lugar de potencias de diez. Por ejemplo, veintitrés se pueden agrupar en once grupos de dos con uno sobrante. Los once dos pueden agruparse en cinco grupos de cuatro con un grupo de dos sobrantes. Continuando en la misma línea, encontramos que veintitrés se puede describir como uno dieciséis, cero ochos, uno cuatro, uno dos, y uno uno, que se abrevia\(10111_{\textrm{two}}\text{,}\) o simplemente\(10111\) si el contexto es claro.

algoritmo de conversión

El proceso que usamos para determinar la representación binaria de\(23\) puede describirse en términos generales para determinar la representación binaria de cualquier entero\(n\text{.}\) positivo Una descripción general de un proceso como este se llama algoritmo. Dado que este es el primer algoritmo del libro, primero lo escribiremos usando un lenguaje menos formal de lo habitual, y luego introduciremos alguna “notación algorítmica”. Si no está familiarizado con los algoritmos, le remitimos a la Sección 17.1

1. Comienza con una lista vacía de bits.
2. Asignar a la variable\(k\) el valor\(n\text{.}\)
3. Mientras que\(k\) el valor es positivo, continúe realizando los siguientes tres pasos hasta que\(k\) se convierta en cero y luego deténgase.
   1. dividir\(k\) por 2, obteniendo un cociente\(q\) (a menudo denotado\(k \textrm{ div } 2\)) y un resto\(r\) (denotado\((k \bmod 2)\)).
   2. adjuntar\(r\) al lado izquierdo de la lista de bits.
   3. asignar a la variable\(k\) el valor\(q\text{.}\)

Ejemplo\(\PageIndex{1}\): An Example of Conversion to Binary

Para determinar la representación binaria de 41 tomamos los siguientes pasos:

• \(\displaystyle 41 = 2 \times 20+ 1 \quad List = 1 \)
• \(\displaystyle 20 = 2 \times 10+0 \quad List = 01 \)
• \(\displaystyle 10 = 2\times 5 + 0 \quad List = 001 \)
• \(\displaystyle 5 =\text2\times 2+ 1 \quad List =1001\)
• \(\displaystyle 2 =2\times 1+ 0 \quad List = 01001 \)
• \(\displaystyle 1 =\text2 \times 0\text+1 \quad List = 101001\)

Por lo tanto,\(41=101001_{\textrm{two}}\)

La notación que usaremos para describir este algoritmo y todos los demás se llama pseudocódigo, una variación informal de las instrucciones que se utilizan comúnmente en muchos lenguajes informáticos. Lea atentamente la siguiente descripción, comparándola con la descripción informal anterior. El apéndice B, que contiene una discusión general de los componentes de los algoritmos en este libro, debería aclarar cualquier duda persistente. Cualquier cosa después//son comentarios.

Algorithm \(\PageIndex{1}\): Binary Conversion Algorithm

Un algoritmo para determinar la representación binaria de un entero positivo.

Entrada: un entero positivo n.

Salida: la representación binaria de n en forma de lista de bits, con unidades bit last, twos bit next to last, etc.

1. k: = n\(\qquad \) //inicializar k
2. L: = {}\(\qquad \) //inicializar L a una lista vacía
3. Mientras k > 0 hacer
   1. q: = k div 2\(\qquad \) //dividir k por 2
   2. r: = k mod 2
   3. L: = anteponer r a L\(\qquad \) //añadir r al frente de L
   4. k: = q\(\qquad \) //reasignar k

Aquí hay una versión Sage del algoritmo con dos alteraciones. Da salida a la representación binaria como una cadena, y maneja todos los enteros, no solo los positivos.

def binary_rep(n):
    if n==0:
        return '0'
    else:
        k=abs(n)
        s=''
        while k>0:
            s=str(k%2)+s
            k=k//2
        if n < 0:
            s='-'+s
        return s
 
binary_rep(41)

Ahora que has leído esta sección, deberías conseguir esta broma.

Figura\(\PageIndex{1}\): Con permiso de Randall Munroe, http://xkcd.com.

Ejercicios

Ejercicio\(\PageIndex{1}\)

Encuentra la representación binaria de cada uno de los siguientes enteros positivos trabajando a mano a través del algoritmo. Puedes verificar tu respuesta usando la celda de salvia anterior.

1. \(31\)
2. \(32\)
3. \(10\)
4. \(100\)

Contestar

1. \(\displaystyle 11111\)
2. \(\displaystyle 100000\)
3. \(\displaystyle 1010\)
4. \(\displaystyle 1100100\)

Ejercicio\(\PageIndex{2}\)

Encuentra la representación binaria de cada uno de los siguientes enteros positivos trabajando a mano a través del algoritmo. Puedes verificar tu respuesta usando la celda de salvia anterior.

1. \(64\)
2. \(67\)
3. \(28\)
4. \(256\)

Ejercicio\(\PageIndex{3}\)

¿Qué enteros positivos tienen las siguientes representaciones binarias?

1. \(10010\)
2. \(10011\)
3. \(101010\)
4. \(10011110000\)

Contestar

1. \(\displaystyle 18\)
2. \(\displaystyle 19\)
3. \(\displaystyle 42\)
4. \(\displaystyle 1264\)

Ejercicio\(\PageIndex{4}\)

¿Qué enteros positivos tienen las siguientes representaciones binarias?

1. \(100001\)
2. \(1001001\)
3. \(1000000000\)
4. \(1001110000\)

Ejercicio\(\PageIndex{5}\)

El número de bits en las representaciones binarias de números enteros aumenta en uno a medida que los números se duplican. Usando este hecho, determine cuántos bits tienen las representaciones binarias de los siguientes números decimales sin hacer realmente la conversión completa.

1. \(2017\)
2. \(4000\)
3. \(4500\)
4. \(\displaystyle 2^{50}\)

Contestar

1. Hay un bit por cada potencia de 2 hasta la más grande necesaria para representar un entero, y comienzas a contar con la potencia cero. Por ejemplo, 2017 es entre\(2^{10}=1024\) y\(2^{11}=2048\text{,}\) y así la mayor potencia necesaria es\(2^{10}\text{.}\) Por lo tanto hay\(11\) bits en binario 2017.
2. \(\displaystyle 11\)
3. \(\displaystyle 12\)
4. \(\displaystyle 13\)
5. \(51\)

Ejercicio\(\PageIndex{6}\)

Dejar\(m\) ser un entero positivo con representación binaria\(n\) -bit:\(a_{n-1}a_{n-2}\cdots a_1a_0\) con\(a_{n-1}=1\) ¿Cuáles son los valores más pequeños y mayores que\(m\) podrían tener?

Ejercicio\(\PageIndex{7}\)

Si un entero positivo es un múltiplo de 100, podemos identificar este hecho a partir de su representación decimal, ya que terminará con dos ceros. ¿Qué se puede decir de un entero positivo si su representación binaria termina con dos ceros? ¿Y si termina en\(k\) ceros?

Contestar

Un número debe ser un múltiplo de cuatro si su representación binaria termina en dos ceros. Si termina en\(k\) ceros, debe ser un múltiplo de\(2^k\text{.}\)

Ejercicio\(\PageIndex{8}\)

¿Se puede identificar fácilmente un múltiplo de diez a partir de su representación binaria?