¿Es posible escribir lógica usando solo los operadores AND, OR y NOT para comparar 2 operandos y devolver verdadero/falso (-1, 0) sin el uso de saltos? Si es así, ¿puede darme algunas pistas, ya que me parece imposible? Estoy tratando de implementar eq, lt y gt en el lenguaje ensamblador del libro "The Elements of Computing Systems".implementar eq, lt gt en ensamblado sin saltos
Obtener un resultado de -1 o 0 (o de 1 o 0, para el caso) de sus operaciones de comparación es imposible si solo está utilizando operadores lógicos bit a bit. y añadir/restar, donde se pierde el equipaje:
Para los operadores bit a bit, el bit n del resultado depende sólo de poco n de los dos operandos.
Por otra parte, consideremos cómo funciona una adición binaria: poco n del resultado puede estar influido por poco n y bits a la derecha del bit n (a través de acarreos), de cada una de las operandos; pero no puede ser influenciado por ningún bit a la izquierda del bit n en los operandos. (Se podría considerar que esto es una generalización de la observación de que la adición de dos números pares no pueden dar un resultado extraño.)
Como una sola adición o bit a bit op no se puede propagar cualquier información de la izquierda de bits n de la operandos en el bit n del resultado, tampoco puede ninguna composición de adiciones u operaciones bit a bit; y una sustracción (asumiendo el complemento de 2 aquí) puede considerarse como tal composición: x-y = x + (NOT y) +1.
Así no se puede obtener un resultado de 0 para 2 == 2, pero -1 (o 1) para 2 == 4, por ejemplo: bit 0 del resultado deseado es diferente en cada caso , pero el resultado puede depender solo del bit 0 de los dos operandos, que son los mismos en cada caso.
Si sus valores verdaderos y falsos sólo se diferencian en el bit superior (es decir, más a la izquierda), se puede hacerse.
Por ejemplo, con valores de 8 bits: use 0x80 para verdadero y 0 para falso; entonces x == y podría implementarse como (NOT((x - y) OR (y - x))) AND 0x80.
El problema tal como se estableció originalmente se puede resolver si las operaciones disponibles se extienden para incluir un desplazamiento a la derecha, o si la operación ADD puede producir un acarreo que se puede volver a agregar al final del resultado.
Gracias, creo que esta es una gran respuesta, muy clara y comprensible. – culchie
Puede hacerlo con turnos, que también es en modo bit. Desafortunadamente no está permitido en la pregunta –
XOR a, b
dará como resultado 0 si a y b son iguales, y algo distinto de cero de lo contrario.
SUB a, b
AND a, SIGN_BIT
(donde SIGN_BIT es una máscara para eliminar todo excepto ... el bit de signo)
resultará en cero si a es mayor que b, y distinto de cero si a es menor o igual que b (suponiendo que 2 es completo).
Gracias. el problema que tuve fue que la salida tiene que ser -1 o 0, pude producir -1 donde las pruebas fueron verdaderas, pero si el resultado fue falso, la salida sería como 'algo'. Quería poder forzar este algo a 0, si no fuera un -1 – culchie
Tenga en cuenta que su comparación no hace lo correcto si los restros se desbordan =/ –
Se generará un desplazamiento aritmético hacia la derecha de la cantidad máxima en -1 si la entrada es negativa, y 0 de lo contrario –
Por si acaso esta es una pregunta puramente teórica: ya que está operando en un conjunto finito de operandos, todas las funciones posibles se pueden expresar utilizando solo O, Y y NO.
Consulte Disjunctive normal form para obtener más información.
A efectos prácticos, Anon respuesta es más útil :-) ...
EDITAR: Incluso mi respuesta teórica podría no ser cierto: Aplicación de forma normal disyuntiva a este problema requeriría operaciones de desplazamiento, ya cada bit de la palabra de salida depende de todos los bits de los bits de entrada. Todavía no he descubierto cómo implementar turnos usando AND, O, NOT y aritmética (y no estoy seguro de si eso es posible ...)
Dejo la publicación como un ejemplo negativo de respuesta prematura. ..
x86 Las CPU de algún punto en la historia en adelante han tenido operaciones de "movimiento condicional".
A igual B se puede expresar en términos de XOR:
(A AND (NOT B)) OR (A AND (NOT B))
Esta voluntad de salida 0 si A == B y algo = 0 si no es
para un menor que B sea posible utilizar (a - B y SIGN_MASK)
, donde las máscaras de distancia SIGN_MASK todo excepto el bit de signo, se le dará un cierto valor de MAX_NEGATIVE_INTEGER y un valor de 0. falsa
Mayor que puede construirse trivialmente a partir de menos de
Gracias, ¿cómo puedo convertir el! = 0 a un valor definido (digamos 1) para todos los casos donde! = 0 no es 0. Ese es el obstáculo para mí – culchie
todas las operaciones aritméticas en el lenguaje de ensamblaje de las que está hablando vienen con la posibilidad de saltos condicionales basados en el resultado de la operación (= 0? Y> 0?), Que pueden usarse para obtener el booleano deseado resultado.
Estamos revisando el mismo libro y simplemente solucionamos este problema.
La mejor solución que pudimos encontrar fue generar etiquetas únicas, y luego usar el comando JEQ para saltar a la esperada, y luego saltar a una etiqueta más abajo cuando terminamos.
Pseudocódigo:
if they're equal, jump to EQUAL
// not equal section
push constant false
jump to DONE
// equal section
(EQUAL)
push constant true
// done section
(DONE)
Here es cómo hemos implementado específicamente a esta (en Ruby).
¿es realmente necesario usar solo y, o no? porque generalmente necesitarás algo como sub (que es técnicamente expresable a través de los operadores mencionados, pero sería un poco fastidioso atravesar manualmente el carry. Si permites que los operadores sub y shift se vuelvan relativamente fáciles, – Grizzly
Do necesita lidiar con números negativos también? – petantik
lo siento, sí, sí puede sumar, restar y asignar valores a los registros, los cálculos ALU de conjunto son 0, 1 -1, x, y, no x, no y, -x, -y, x + 1, y + 1, x-1, y-1, x + y, xy, yx, xYy, x OR y – culchie