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

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])

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

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.

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.

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.

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