El reto
Implemente una función que acepte dos enteros cuyos valores oscilen entre 0 y 255 y devuelva la suma de esos enteros mod 256. Solo puede usar la negación a nivel de bit (~), a nivel de bit o (|), operadores de desplazamiento de bit (>>, <<) y asignación (=).
Las cosas que no puede usar incluyen (pero no están limitadas a)
- Suma, resta, multiplicación y división.
- Bucles
- Declaraciones condicionales
- Llamadas a funciones
Pocos usos de operaciones binarias o de negación binaria, y bit shift ganan . En caso de empate, gana la solución más popular. Como siempre, se aplican las lagunas estándar .
Aquí hay un ejemplo de un simple sumador de 2 bits. Utiliza 77 negaciones binarias, 28 or binarias y 2 cambios de bits para una puntuación total de 107 (esto se puede ver ejecutando el preprocesador C con gcc -E
). Podría hacerse mucho más eficiente eliminando los #define
sy simplificando las expresiones resultantes, pero los dejé para mayor claridad.
#include <stdio.h>
#define and(a, b) (~((~a)|(~b)))
#define xor(a, b) (and(~a,b) | and(a,~b))
int adder(int a, int b)
{
int x, carry;
x = xor(and(a, 1), and(b, 1));
carry = and(and(a, 1), and(b, 1));
carry = xor(xor(and(a, 2), and(b, 2)), (carry << 1));
x = x | carry;
return x;
}
int main(int argc, char **argv)
{
int i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
if (adder(i, j) != (i + j) % 4) {
printf("Failed on %d + %d = %d\n", i, j, adder(i, j));
}
}
}
}
Actualización: ejemplo agregado y criterios de puntuación cambiados
Respuestas:
Python, 36 operaciones
¡Un método logarítmico en el parámetro "8"!
La idea es averiguar qué índices se desbordan y causan acarreos. Inicialmente, esto es sólo los lugares en los que ambos
a
andáb
tienen una1
. Pero dado que los bits transportados pueden causar desbordamientos adicionales, esto debe determinarse de forma iterativa.En lugar de desbordar cada índice en el siguiente, aceleramos el proceso moviendo 1 índice, luego 2 índices, luego 4 índices, asegurándonos de recordar los lugares donde ocurrió un desbordamiento (H) y donde ya no puede ocurrir un desbordamiento (K )
Una solución iterativa más simple con 47 operaciones:
Equipo de prueba, para cualquiera que quiera copiarlo.
fuente
C - 0
Utiliza operadores fuera de ~, |, >>, <<, y =, pero veo soluciones que utilizan operadores de conversión y coma, así que supongo que la regla no es demasiado estricta siempre que no esté utilizando los operadores prohibidos.
fuente
pitón, puntuación =
8380Desenrolla el bucle. Son 10 operaciones por ciclo multiplicadas por 7 ciclos, 7 para el último xor y 3 para aplastar el noveno bit al final.
Implementa la ecuación
x+y = x^y + 2*(x&y)
repitiéndola 8 veces. Cada vez hay un bit cero más en la parte inferior dey
.fuente
C, Puntuación:
7760Golfé por el placer de hacerlo,
206169131 bytes:Expandido:
Esencialmente, la misma solución (matemáticamente) que se
leocurrió a@KeithRandall@JuanICarrano, pero aprovecha la capacidad de C para jugar rápido y suelto con tipos variables y punteros para borrar todo después de los primeros 8 bits sin usar más operadores.Depende del endian-ness de la máquina y el tamaño de () un int y un char, pero debería poder ser portado a la mayoría de las aplicaciones específicas de la máquina con la matemática de puntero adecuada.
EDITAR: Este es un desafío que C (u otros lenguajes de bajo nivel) tendrán una ventaja distintiva, a menos que alguien presente un algoritmo que no tenga que llevar.
fuente
unsigned char
. Es más limpio y más portátil.unsigned
no es algo natural para mí en el código de golf. Tienes razón, por supuesto, actualizado.Python - Puntuación
6664Es la ecuación para un sumador de ondas. C es el llevar. Se calcula un bit a la vez: en cada iteración, el carry se propaga a la izquierda. Como señaló @Orby, la versión original no hizo una adición modular. Lo arreglé y también guardé un ciclo en la iteración, ya que el primer arrastre siempre es cero.
fuente
s(255,2)
devuelve en257
lugar de1
). Puede corregir esto cambiando su última línea a lareturn ~(~xxor(axb,C)|256)
que agrega 3 puntos.C ++ - puntaje: 113
fuente
add(1, 255)
me devuelve 128, @Ryan.%
no está en la lista de operadores autorizados, a saber~
,|
,>>
, y<<
. Tal vez reemplazarlo conands(x8|y8, 255)>>1
?~(~x8 | y8 | 0xFFFFFF00)
sería un buen truco con solo 4+ para tu puntaje.byte
lugar deint
hacerlo desbordarlo automáticamente?