Implemente un sumador de 8 bits

12

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 #definesy 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

O por
fuente
2
¿Por qué no bitwise "y"?
rdans
@Ryan La mayoría de las personas están más familiarizadas con las puertas NAND que con las puertas NOR :)
Orby
1
Qué recuento cuenta como un bucle?
rdans
@Ryan Recursion cuenta como un bucle, aunque no estoy seguro de cómo lo implementaría sin una declaración condicional.
Orby
¿Está definido el desbordamiento o puedo generar algo si se desborda?
Comintern

Respuestas:

8

Python, 36 operaciones

¡Un método logarítmico en el parámetro "8"!

def add(a,b):
    H = a&b   #4 for AND
    L = a|b   #1 
    NX = H | (~L) #2
    K = NX 

    H = H | ~(K | ~(H<<1)) #5
    K = K | (K<<1) #2

    H = H | ~(K | ~(H<<2)) #5
    K = K | (K<<2) #2

    H = H | ~(K | ~(H<<4)) #5

    carry = H<<1 #1

    neg_res = NX ^ carry  #7 for XOR
    res_mod_256 = ~(neg_res|-256) #2
    return res_mod_256

La idea es averiguar qué índices se desbordan y causan acarreos. Inicialmente, esto es sólo los lugares en los que ambos aandá btienen una 1. 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:

def add(a,b):
    H = a&b   #4 for AND
    L = a|b   #1 
    NX = H | (~L) #2

    c=H<<1  #1

    for _ in range(6): #6*5
        d = (~c)|NX
        e = ~d
        c = c|(e<<1)

    res = c ^ NX  #7 for XOR

    res_mod_256 = ~(res|-256) #2
    return res_mod_256

Equipo de prueba, para cualquiera que quiera copiarlo.

errors=[]
for a in range(256):
    for b in range(256):
        res = add(a,b)
        if res!=(a+b)%256: errors+=[(a,b,res)]

print(len(errors),errors[:10])
xnor
fuente
8

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.

unsigned char sum(unsigned char x, unsigned char y)
{
    static unsigned char z[] = {
        0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
        16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
        32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
        48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
        64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
        80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
        96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
        112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
        128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
        144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
        160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
        176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
        192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
        208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
        224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
        240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
        0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
        16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
        32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
        48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
        64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
        80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
        96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
        112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
        128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
        144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
        160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
        176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
        192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
        208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
        224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
        240,241,242,243,244,245,246,247,248,249,250,251,252,253,254
    };

    return (&z[x])[y];
}

fuente
Esto es obviamente un vacío legal, pero +1 para señalarlo.
Orby
7

pitón, puntuación = 83 80

def g(x,y):
    for i in xrange(7):
        nx = ~x
        ny = ~y
        x,y = ~(x|ny)|~(nx|y), (~(nx|ny))<<1
    x = ~(x|~y)|~(~x|y)
    return ~(~x|256)

Desenrolla 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 de y.

Keith Randall
fuente
7

C, Puntuación: 77 60

Golfé por el placer de hacerlo, 206 169 131 bytes:

#define F c=((~(~c|~m))|n)<<1;
a(x,y){int m=(~(x|~y))|~(~x|y),n=~(~x|~y),c;F F F F F F F return (unsigned char)(~(m|~c))|~(~m|c);}

Expandido:

int add(x,y)
{
    int m=(~(x|~y))|~(~x|y);
    int n=~(~x|~y);
    int c = 0;
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1;    
    c=((~(~c|~m))|n)<<1; 
    c=((~(~c|~m))|n)<<1; 
    return (int)((unsigned char)(~(m|~c))|~(~m|c));
}

Esencialmente, la misma solución (matemáticamente) que se le ocurrió 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.

Comintern
fuente
Si vas a manejar la envoltura de esa manera, simplemente podrías enviarlo unsigned char. Es más limpio y más portátil.
Orby
@Orby - Supongo que escribir unsignedno es algo natural para mí en el código de golf. Tienes razón, por supuesto, actualizado.
Comintern
4

Python - Puntuación 66 64

def xand(a,b):
    return ~(~a|~b) #4

def xxor(a,b):
    return (~(a|~b))|~(~a|b) #7

def s(a,b):
    axb = xxor(a,b)   #7
    ayb = xand(a,b)   #4

    C = 0
    for i in range(1,8):
        C = ((xand(C,axb))|ayb)<<1    #(1+1+4)x7=6x7=42

    return xxor(axb,xand(C,255))    #7 + 4 = 11
    #total: 7+4+42+11 = 64

Es 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.

Juan I Carrano
fuente
3
Buen trabajo, pero su código no se ajusta correctamente (es decir, s(255,2)devuelve en 257lugar de 1). Puede corregir esto cambiando su última línea a la return ~(~xxor(axb,C)|256) que agrega 3 puntos.
Orby
2

C ++ - puntaje: 113

#define ands(x, y) ~(~x | ~y) << 1
#define xorm(x, y) ~(y | ~(x | y)) | ~(x | ~(x | y))

int add(int x, int y)
{
int x1 = xorm(x, y);
int y1 = ands(x, y);

int x2 = xorm(x1, y1);
int y2 = ands(x1, y1);

int x3 = xorm(x2, y2);
int y3 = ands(x2, y2);

int x4 = xorm(x3, y3);
int y4 = ands(x3, y3);

int x5 = xorm(x4, y4);
int y5 = ands(x4, y4);

int x6 = xorm(x5, y5);
int y6 = ands(x5, y5);

int x7 = xorm(x6, y6);
int y7 = ands(x6, y6);

int x8 = xorm(x7, y7);
int y8 = ands(x7, y7);

return (x8 | y8) % 256;
}
rdans
fuente
add(1, 255)me devuelve 128, @Ryan.
Orby
@Orby ya está arreglado
rdans
%no está en la lista de operadores autorizados, a saber ~, |, >>, y <<. Tal vez reemplazarlo con ands(x8|y8, 255)>>1?
Orby
En realidad, ~(~x8 | y8 | 0xFFFFFF00)sería un buen truco con solo 4+ para tu puntaje.
Orby
2
¿Pero no hacer el tipo en bytelugar de inthacerlo desbordarlo automáticamente?
orgulloso Haskeller