¿Es posible definir todos los operadores bit a bit utilizando un 'bitwise nand' similar a cómo se puede construir toda la lógica booleana usando solo 'boolean nand'?

9

Nand se conoce como puerta lógica 'universal', porque le permite definir todas las demás puertas lógicas booleanas:

not(x) = nand(x,x)
and(x, y) = not(nand(x, y))
or(x, y) = nand(not(x), not(y))
nor(x, y) = not(or(x, y))
xor(x, y) = nand(nand(a, nand(a, b)), nand(b, nand(a, b)))

Esto se conoce como lógica nand , y se usa comúnmente en las computadoras modernas porque se puede hacer que un transistor se comporte como una compuerta nand.

Me pregunto si es posible hacer algo similar con las operaciones bit a bit. Puede un ejemplo a nivel de bit NAND (bnand) utilizarse para definir bnot, bor, band, bnor, bxor? ¿Existe una operación universal a nivel de bits?

bitwise-operators boolean Qqwy
fuente

Respuestas:

13

A nivel de hardware no hay diferencia entre bit a bit y lógico. Entonces sí. Una operación lógica es solo una operación bit a bit en un solo bit.

Martin Maat
fuente
2

En la mayoría de los microprocesadores modernos, las operaciones bit a bit se implementan de forma nativa, por lo que no es beneficioso tener una operación NAND.

Por ejemplo, el conjunto de instrucciones x86 tiene: AND , OR , XOR , NOT . Todo esto se realiza en un solo ciclo hasta donde yo sé, por lo que no sería beneficioso reemplazarlos con varias operaciones NAND. También tiene ANDN, que es un equivalente ((NOT x) AND y)que podría generar un compilador de optimización inteligente para ganar un ciclo.

El movimiento RISC trató de promover un conjunto de instrucciones reducido para una arquitectura más simple y con mejor rendimiento. La idea era que los compiladores tendrían que combinar instrucciones más simples y rápidas. Sin embargo, parece que, aparte de algunos procesadores experimentales o de enseñanza, la mayoría proporciona NAND de forma nativa, así como las operaciones bit a bit habituales (por ejemplo, PowerPC o ARM ).

Christophe
fuente
Realmente no estoy seguro de cómo se implementan los operadores booleanos en las CPU en estos días, pero solía ser bastante común usar un mux de 4 a 1, introduciendo "la tabla de verdad" como las 4 entradas, luego use los dos bits para operar como el selector para la salida. Le ofrece un solo circuito que puede usarse para las 16 funciones booleanas de dos operandos.
Vatine
2
El hecho de que OR, XOR y NOT se implementen "nativamente" y no tomen más de un solo ciclo de reloj no dice nada acerca de si se construyen utilizando solo circuitos NAND o no. Sospecho que se construyen utilizando solo NAND en estos días porque los transistores son realmente baratos y muy rápidos. El método 4 a 1 de Vatine está optimizado para usar una pequeña cantidad de transistores, lo cual no tiene sentido en la era de los nanómetros.
Martin Maat
RISC ha quedado sin sentido por el tiempo. Cuando surgió, las instrucciones complejas típicas tomaron múltiples ciclos de reloj, como 10 más o menos. Y esto no se trataba de OR / AND / NOT, estos ya eran rápidos y se consideraban "simples" y esenciales para cualquier CPU, por lo que ciertamente no serían descartados por un procesador RISC. Hoy en día, las instrucciones complejas toman menos de un ciclo de reloj (debido a la interconexión y el enhebrado múltiple / núcleo múltiple.)
Martin Maat