Zaimplementuj 8-bitowy sumator

12

Wyzwanie

Zaimplementuj funkcję, która akceptuje dwie liczby całkowite, których wartości mieszczą się w zakresie od 0 do 255 i zwraca sumę tych liczb całkowitych mod 256. Możesz używać tylko negacji bitowej (~), bitowej lub (|), operatorów przesunięcia bitów (>>, <<) i przypisanie (=).

Do rzeczy, których nie można użyć, należą (ale nie wyłącznie)

  • Dodawanie, odejmowanie, mnożenie i dzielenie
  • Pętle
  • Instrukcje warunkowe
  • Wywołania funkcji

Wygrywa niewiele zastosowań binarnych lub binarnych negacji i operacji przesunięcia bitów . W przypadku remisu wygrywa najpopularniejsze rozwiązanie. Jak zawsze obowiązują standardowe luki .

Oto przykład prostego 2-bitowego sumatora. Wykorzystuje 77 binarnych negacji, 28 binarnych orów i 2 przesunięcia bitów, co daje łączny wynik 107 (można to zobaczyć po uruchomieniu preprocesora C gcc -E). Można to uczynić znacznie bardziej wydajnym, usuwając #defines i upraszczając powstałe wyrażenia, ale zostawiłem je dla jasności.

#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));
            }
        }
    }
}

Aktualizacja: Dodano przykład i zmieniono kryteria punktacji

Lub przez
źródło
2
dlaczego nie bitowe ”i„?
rdans
@ Ryan Większość ludzi jest bardziej zaznajomionych z bramkami NAND niż bramkami NOR :)
Orby
1
czy rekurencja liczy się jako pętla?
rdans
@Ryan Recursion jest liczony jako pętla, choć nie jestem pewien, jak zaimplementowałbyś go bez instrukcji warunkowej.
Orby
Czy przepełnienie jest zdefiniowane, czy mogę po prostu cokolwiek wypisać, jeśli się przepełni?
Comintern

Odpowiedzi:

8

Python, 36 operacji

Metody logarytmiczne w parametrze „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

Chodzi o to, aby dowiedzieć się, które wskaźniki przepełniają się i powodują przeniesienie. Początkowo jest to po prostu miejsca, gdzie obie aandd bmają 1. Ale ponieważ przenoszone bity mogą powodować dalsze przelania, należy to ustalić iteracyjnie.

Zamiast przepełniać każdy indeks do następnego, przyspieszamy ten proces, przesuwając 1 indeks, następnie 2 indeksy, a następnie 4 indeksy, pamiętając o miejscach, w których nastąpiło przepełnienie (H) i gdzie przepełnienie nie może się już zdarzyć (K ).


Prostsze iteracyjne rozwiązanie z 47 operacjami:

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

Stanowisko testowe dla każdego, kto chce go skopiować.

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
źródło
9

C - 0

Używa operatorów spoza ~, |, >>, << i =, ale widzę rozwiązania wykorzystujące operatory rzutowania i przecinków, więc myślę, że reguła nie jest zbyt surowa, pod warunkiem, że nie używa zabronionych operatorów.

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];
}

źródło
Jest to oczywiście luka, ale +1 za wskazanie tego.
Orby
7

python, wynik = 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)

Rozwiń pętlę. To 10 operacji na pętlę razy 7 pętli, 7 dla ostatniego xora i 3, aby zgnieść 9. bit na końcu.

Realizuje równanie x+y = x^y + 2*(x&y), powtarzając je 8 razy. Za każdym razem na dole jest jeszcze jeden bit zero y.

Keith Randall
źródło
7

C, wynik: 77 60

Grał w golfa na cholerę, 206 169 131 bajtów:

#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);}

Rozszerzony:

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));
}

Zasadniczo to samo rozwiązanie (matematycznie), które wymyślił @KeithRandall @JuanICarrano, ale korzysta ze zdolności C do szybkiego i swobodnego grania ze zmiennymi typami i wskaźnikami, aby wyczyścić wszystko po pierwszych 8 bitach bez użycia więcej operatorów.

Zależy od endianowości maszyny oraz sizeof () int i char, ale powinien być w stanie być przeniesiony do większości aplikacji specyficznych dla maszyny z odpowiednią matematyką wskaźnika.

EDYCJA: Jest to wyzwanie, w którym C (lub inne języki niskiego poziomu) będą miały wyraźną przewagę - chyba że ktoś wymyśli algorytm, którego nie trzeba nosić.

Komintern
źródło
Jeśli masz zamiar poradzić sobie z owinięciem w ten sposób, możesz po prostu rzucić na unsigned char. Jest czystszy i bardziej przenośny.
Orby
@Orby - Wydaje mi się, że wpisywanie unsignednie przychodzi mi naturalnie w golfie kodowym. Oczywiście masz rację - zaktualizowano.
Comintern
4

Python - wynik 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

Jest to równanie sumatora tętnienia. C jest nosicielem. Jest obliczany jeden bit na raz: w każdej iteracji przeniesienie jest propagowane w lewo. Jak wskazał @Orby, oryginalna wersja nie zawierała dodatku modułowego. Naprawiłem to i zapisałem cykl w iteracji, ponieważ pierwsze przeniesienie jest zawsze równe zero.

Juan I Carrano
źródło
3
Dobra robota, ale twój kod nie zawija się poprawnie (tzn. s(255,2)Zwraca 257raczej niż 1). Możesz to poprawić, zmieniając ostatnią linię, do return ~(~xxor(axb,C)|256) której dodaje się 3 punkty.
Orby
2

C ++ - wynik: 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
źródło
add(1, 255)zwraca 128 dla mnie, @Ryan.
Orby
@Orby jest już naprawiony
rdans
%nie znajduje się na liście dozwolonych operatorów, a mianowicie ~, |, >>, i <<. Może zastąpisz to ands(x8|y8, 255)>>1?
Orby
Właściwie ~(~x8 | y8 | 0xFFFFFF00)zrobiłby to dobrze, mając tylko 4+ swojego wyniku.
Orby
2
Ale czy zrobienie tego typu bytenie intspowodowałoby automatycznego przepełnienia?
dumny haskeller