Implementieren Sie einen 8-Bit-Addierer

12

Die Herausforderung

Implementieren Sie eine Funktion, die zwei Ganzzahlen akzeptiert, deren Werte von 0 bis 255 reichen, und die Summe dieser Ganzzahlen (Mod 256) zurückgibt. Sie können nur bitweise Negation (~), bitweise oder (|), Bitverschiebungsoperatoren (>>, <<) verwenden. und Zuweisung (=).

Zu den Dingen, die Sie nicht verwenden können, gehören (ohne darauf beschränkt zu sein)

  • Addition, Subtraktion, Multiplikation und Division
  • Schleifen
  • Bedingte Anweisungen
  • Funktionsaufrufe

Die wenigsten Verwendungen von binären oder binären Negations- und Bitverschiebungsoperationen gewinnen . Bei einem Gleichstand gewinnt die beliebteste Lösung. Wie immer gelten Standardlücken .

Hier ist ein Beispiel eines einfachen 2-Bit-Addierers. Es verwendet 77 binäre Negationen, 28 binäre Ors und 2 Bitverschiebungen für eine Gesamtpunktzahl von 107 (dies kann durch Ausführen des C-Präprozessors mit angezeigt werden gcc -E). Es könnte viel effizienter gemacht werden, indem man die #defines entfernt und die resultierenden Ausdrücke vereinfacht, aber ich habe sie der Klarheit halber belassen.

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

Update: Beispiel hinzugefügt und Bewertungskriterien geändert

Oder von
quelle
2
warum nicht bitweise "und"?
rdans
@ Ryan Die meisten Menschen sind eher mit NAND-Toren als mit NOR-Toren vertraut :)
Orby
1
zählt die Rekursion als Schleife?
rdans
@ Ryan Recursion zählt als Schleife, obwohl ich nicht sicher bin, wie Sie es ohne eine bedingte Anweisung implementieren würden.
Orby
Ist ein Überlauf definiert oder kann ich nur etwas ausgeben, wenn es überläuft?
Comintern

Antworten:

8

Python, 36 Operationen

Eine Methode, die im Parameter "8" logarithmisch ist!

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

Die Idee ist herauszufinden, welche Indizes Überlauf und Ursache tragen. Anfänglich sind dies nur die Orte, an denen beide und aeine bhaben 1. Da übertragene Bits jedoch weitere Überlappungen verursachen können, muss dies iterativ bestimmt werden.

Anstatt jeden Index in den nächsten zu überfließen, beschleunigen wir den Prozess, indem wir 1 Index, dann 2 Indizes und dann 4 Indizes verschieben. Dabei müssen wir uns die Stellen merken, an denen ein Überlauf aufgetreten ist (H) und an denen kein Überlauf mehr auftreten kann (K) ).


Eine einfachere iterative Lösung mit 47 Operationen:

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

Prüfstand für alle, die ihn kopieren wollen.

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
quelle
8

C - 0

Es werden zwar Operatoren außerhalb von ~, |, >>, << und = verwendet, es werden jedoch Lösungen mit Casting- und Komma-Operatoren angezeigt, sodass die Regel vermutlich nicht zu streng ist, sofern die verbotenen Operatoren nicht verwendet werden.

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

quelle
Dies ist offensichtlich eine Lücke, aber +1, um darauf hinzuweisen.
Orby
7

Python, Score = 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)

Wickeln Sie die Schleife ab. Es sind 10 Operationen pro Schleife mal 7 Schleifen, 7 für das letzte xor und 3, um das 9. Bit am Ende zu quetschen.

Implementiert die Gleichung x+y = x^y + 2*(x&y)durch achtmaliges Wiederholen. Jedes Mal befindet sich ein weiteres Nullbit am Ende von y.

Keith Randall
quelle
7

C, Punktzahl: 77 60

Golfen nur zum Teufel, 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);}

Erweitert:

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

Im Wesentlichen die gleiche Lösung (mathematisch) wie @KeithRandall @JuanICarrano, nutzt jedoch die Fähigkeit von C, schnell und locker mit variablen Typen und Zeigern zu spielen, um nach den ersten 8 Bits alles zu löschen, ohne weitere Operatoren zu verwenden.

Hängt vom Endian der Maschine und der Größe von (), einem int und einem char ab, sollte aber mit der richtigen Zeigermathematik für die meisten maschinenspezifischen Anwendungen portiert werden können.

BEARBEITEN: Dies ist eine Herausforderung, bei der C (oder andere Sprachen mit niedrigem Sprachniveau) eine ausgeprägte Oberhand haben wird - es sei denn, jemand hat einen Algorithmus gefunden, der nicht mithalten muss.

Komintern
quelle
Wenn Sie mit dem Umwickeln auf diese Weise umgehen, können Sie es einfach tun unsigned char. Es ist sauberer und tragbarer.
Orby
@Orby - Beim Codegolf ist unsignedes für mich nicht selbstverständlich, etwas zu tippen . Sie haben natürlich Recht - aktualisiert.
Comintern
4

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

Dies ist die Gleichung für einen Ripple-Addierer. C ist der Carry. Es wird bitweise berechnet: In jeder Iteration wird der Übertrag nach links weitergegeben. Wie von @Orby hervorgehoben, wurde die ursprüngliche Version nicht modular erweitert. Ich habe es behoben und auch einen Zyklus in der Iteration gespeichert, da der erste Übertrag immer Null ist.

Juan I Carrano
quelle
3
Gute Arbeit, aber Ihr Code wird nicht richtig umgebrochen (dh s(255,2)kehrt 257eher zurück als 1). Sie können dies korrigieren, indem Sie Ihre letzte Zeile ändern, zu return ~(~xxor(axb,C)|256) der 3 Punkte hinzugefügt werden.
Orby
2

C ++ - Punktzahl: 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
quelle
add(1, 255)gibt für mich 128 zurück, @Ryan.
Orby
@Orby seine jetzt behoben
rdans
%ist nicht auf der Liste der zugelassenen Betreiber, nämlich ~,| , >>, und <<. Vielleicht durch ersetzen ands(x8|y8, 255)>>1?
Orby
Eigentlich ~(~x8 | y8 | 0xFFFFFF00)würde man den Trick mit nur 4+ schön zu Ihrem Ergebnis machen.
Orby
2
Aber würde der Typ nicht automatisch überlaufen, byteanstatt intihn zu erstellen?
stolzer Haskeller