Ihr Ziel ist es , die unten definierte Operation der XOR- Multiplikation ( Carryless ) in möglichst wenigen Bytes zu implementieren .

Wenn wir uns bitweises XOR ( ^) als binäre Addition ohne Übertragen vorstellen

   101   5
^ 1001   9
  ----  
  1100  12

  5^9=12

Wir können eine XOR-Multiplikation durchführen, @indem wir eine binäre Langmultiplikation durchführen, aber den Addierschritt ausführen, ohne ein bitweises XOR durchzuführen ^.

     1110  14
   @ 1101  13
    -----
     1110
       0
   1110
^ 1110 
  ------
  1000110  70

  14@13=70

(Für Mathematiker ist dies die Multiplikation im Polynomring F_2[x], wobei Polynome mit natürlichen Zahlen identifiziert werden, indem x=2über Z als Polynom ausgewertet wird .)

Die XOR-Multiplikation pendelt a@b=b@a, assoziiert (a@b)@c=a@(b@c)und verteilt sich über bitweises XOR a@(b^c)=(a@b)^(a@c). In der Tat ist es die einzigartige solche Operation , die Multiplikation entspricht , a@b=a*bwann immer aund bBefugnisse sind 2wie 1,2,4,8....

Bedarf

Nehmen Sie zwei nicht negative Ganzzahlen als Eingabe und Ausgabe oder drucken Sie ihr XOR-Produkt. Dies sollte als Zahlen oder deren dezimale Zeichenfolgendarstellung erfolgen, nicht als binäre Erweiterung. Wenigste Bytes gewinnt.

Mach dir keine Sorgen über Integer-Überläufe.

Hier sind einige Testfälle formatiert als a b a@b.

0 1 0
1 2 2
9 0 0
6 1 6
3 3 5
2 5 10
7 9 63
13 11 127
5 17 85
14 13 70
19 1 19
63 63 1365

x86-Maschinencode: 7 Byte

66 0F 3A 44 C1 00 C3  pclmulqdq xmm0, xmm1, 0 \ ret

Nur zwei Anweisungen. pclmulqdqWenn das schwere Heben ausgeführt wird, wird diese Art der Xor-Multiplikation buchstäblich implementiert. retum es zu einer aufrufbaren Funktion zu machen, die hoffentlich die Anforderung erfüllt, das Ergebnis (im Rückgabewert xmm0) "auszugeben" . Ganzzahlige Argumente in xmmargs einzufügen ist etwas ungewöhnlich, aber ich hoffe, Sie werden mir vergeben.

Z80, 11 Bytes

B7 CB 32 30 01 B3 C8 CB 23 18 F6   

Der Code wird als Funktion aufgerufen. aund bsind in Dund E(die Reihenfolge spielt keine Rolle) und die Antwort wird in gespeichert, Awenn der Code zurückkehrt (es gibt keine E / A-Funktionen).

B7      XOR A     //  A^=A (A=0)
CB 32   SRL D     //    CARRY = lsb(D), D>>=1, ZERO = D==0
30 01   JR NC, 1  //    jump 1 byte if not CARRY
B3      XOR E     //      A^=E, ZERO = A==0
C8      RET Z     //    return if ZERO
CB 23   SLA E     //    E<<=1
18 F6   JR -10    //    jump -10 bytes

Es liefert die korrekten Ergebnisse für alle Testeingaben, mit 63@63der Ausnahme , 85dass alle Register 8-Bit und 1365 mod 256 = 85 sind (Integer-Überlauf).

C 44 38 Bytes

Dank nimi verwenden wir jetzt die Rekursion für 6 Bytes weniger!

f(a,b){return b?(b&1)*a^f(a*2,b/2):0;}

Wir definieren eine Funktion , fdie dauert a, b.

Dies kann wie folgt aufgerufen werden:

printf("%d @ %d = %d\n", 13, 14, f(13, 14));

Welche Ausgänge:

13 @ 14 = 70

Probieren Sie die Testfälle online aus !

Pyth, 13 12 Bytes

uxyG*HQjvz2Z

Demonstration.

uxyG*HQjvz2Z
                  Implicit:
                  z = input()
                  Q = eval(input())
                  Z = 0

       jvz2       The first input, written in base 2, like so: [1, 0, 1, ...
u      jvz2Z      Reduce over the binary representation, starting with 0.
 x                XOR of
  yG              Twice the previous number
    *HQ           and the second input times the current bit.

Alte Version, 13 Bytes:

xFm*vz.&Q^2dQ

Demonstration.

CJam, 14 13 Bytes

q~2bf*{\2*^}*

Wie es funktioniert :

Wir erhalten zuerst die langen Multiplikationsergebnisse und arbeiten uns dann von den unteren beiden Paaren nach oben.

q~                e# Eval the input. This puts the two numbers on stack
  2b              e# Convert the second number to binary
    f*            e# Multiply each bit of second number with the first number
                  e# This leaves an array with the candidates to be added in the long
                  e# multiplication step
      {    }*     e# Reduce on these candidates. Starting from the bottom
       \2*        e# Bit shift the lower candidate
          ^       e# XOR each other and continue

Probieren Sie es hier online aus

J, 14 Bytes

*/(~://.@)&.#:

Verwendung:

   5 (*/(~://.@)&.#:) 17     NB. enclosing brackets are optional
85

Erklärung (meistens von rechts nach links lesen; uund vfür beliebige Funktionen stehen):

• u&.#:gilt ufür die Vektoren der binären Darstellungen der eingegebenen Zahlen, dann das Ergebnis zurück zu einer ganzen Zahl ( u&.v == v_inverse(u(v(input_1), v(input_2))))
• */products ( *) von Eingaben im Descartes-Produkt ( /) der beiden binären Vektoren
• v(u@)gelten ufür v(für das Descartes-Produkt)
• u/.gilt ufür jede Antidiagonale des Descartes-Produkts (Antidiagonalen stehen für die Ziffern 1, 2, ... in der Binärdarstellung)
• ~:/Reduzieren ( /) einer Antidiagonale mit XOR-Operation ( ~:)
• Der letzte Schritt ist das Erzeugen einer Ganzzahl aus dem Binärvektor, um den sich der erste Punkt kümmert.

Probieren Sie es hier online aus.

Python 2, 35 Bytes

f=lambda m,n:n and n%2*m^f(2*m,n/2)

Rufen Sie gerne an f(13, 14). Ich denke, dass die meisten Sprachen mit einem ähnlichen Konstrukt auf so etwas konvergieren werden.

Java, 62

(x,y)->{int r=0,i=0;for(;i<32;)r^=x*((y>>i)%2)<<i++;return r;}

Erweitert

class XORMultiplication {
    public static void main(String[] args) {
        IntBinaryOperator f = (x, y) -> {
                    int r = 0, i = 0;
                    for (; i < 32;) {
                        r ^= x * ((y >> i) % 2) << i++;
                    }
                    return r;
                };
        System.out.println(f.applyAsInt(14, 13));
    }
}

Haskell, 50 Bytes

import Data.Bits
_#0=0
a#b=b.&.1*a`xor`2*a#div b 2

Eine Übersetzung von @ BrainSteels C-Antwort. Anwendungsbeispiel:

map (uncurry (#)) [(0,1),(1,2),(9,0),(6,1),(3,3),(2,5),(7,9),(13,11),(5,17),(14,13),(19,1),(63,63)]
[0,2,0,6,5,10,63,127,85,70,19,1365]

Perl - 35 Bytes

#!perl -p
$\^=$`>>$_&1&&$'<<$_ for-/ /..31}{

Zählen der Befehlszeilenoption als eine. Die Eingabe erfolgt STDINgetrennt vom Leerzeichen.

Beispielnutzung:

$ echo 13 11 | perl xormul.pl
127
$ echo 5 17 | perl xormul.pl
85
$ echo 14 13 | perl xormul.pl
70
$ echo 19 1 | perl xormul.pl
19
$ echo 63 63 | perl xormul.pl
1365

Julia, 35 33 30 Bytes

f(a,b)=b%2*a$(b>0&&f(2a,b÷2))

Dadurch wird eine rekursive Funktion erstellt, fdie zwei Ganzzahlen verwendet und das XOR-Produkt der Eingaben zurückgibt.

Ungolfed:

function f(a, b)
    # Bitwise XOR : $
    # Short-circuit AND : &&

    b % 2 * a $ (b > 0 && f(2a, b ÷ 2))
end

Mit Ermutigung von Sp3000 ein paar Bytes gespart!

Python 2, 104 91 78 66 Bytes

def y(a,b,c=0):
 for _ in bin(b)[:1:-1]:c^=int(_)*a;a<<=1
 print c

Nehmen Sie die Bits bin umgekehrter Reihenfolge, bevor Sie '0b'den Anfang der Zeichenfolge treffen . Multiplizieren Sie jedes mit aund xorund verschieben Sie es dann nach links a. Dann drucken Sie die Summe.

Los, 63 Bytes

func f(a,b uint)uint{if a<1{return 0};return a%2*b^f(a/2,b*2)}

Vollständiges Beispiel:

http://play.golang.org/p/-ngNOnJGyM

GAP , 368 Bytes

Für Mathematiker ist dies die Multiplikation im Polynomring F_2 [x], wobei Polynome mit natürlichen Zahlen identifiziert werden, indem bei x = 2 als Polynom über Z ausgewertet wird.

Klar, lass uns das machen! (Dies ist nur locker gespielt, es ging mehr darum, in F ₂ [x] einzusteigen und die Berechnungen durchzuführen, als jeden Versuch, ein Gewinner zu sein.)

Hier ist der Code

f:=function(i,j)R:=PolynomialRing(GF(2));x:=IndeterminatesOfPolynomialRing(R);x:=x[1];a:=function(i)local n,r;r:=0*x;while not i=0 do n:=0;while 2^n<=i do n:=n+1;od;n:=n-1;r:=r+x^n;i:=i-2^n;od;return r;end;b:=function(r)local c,i,n;i:=0;n:=0;for c in CoefficientsOfUnivariatePolynomial(r) do if c=Z(2)^0 then n:=n+2^i;fi;i:=i+1;od;return n;end;return b(a(i)*a(j));end;

Hier ist der ungolfed Code mit Erklärung:

xor_multiplication:=function(i,j)           
    R:=PolynomialRing(GF(2));
    x:=IndeterminatesOfPolynomialRing(R);
    x:=x[1];
    to_ring:=function(i)
        local n,r; 
        r:=0*x;
        while not i=0 do
            n:=0;
            while 2^n<=i do
                n:=n+1;
            od;
            n:=n-1;
            r:=r+x^n;
            i:=i-2^n;
        od;
        return r;
    end;
    to_ints:=function(r)
        local c,i,n;
        i:=0;n:=0;
        for c in CoefficientsOfUnivariatePolynomial(r) do
            if c=Z(2)^0 then
                n:=n+2^i;
            fi;
            i:=i+1;
        od;
        return n;
    end;
    return to_ints( to_ring(i)*to_ring(j));
end;

Okay, also erstellen wir zuerst den univariaten Polynomring über dem Feld F ₂ und nennen ihn R. Beachten Sie, dass in GAP GF(2)F _{2 ist} .

R:=PolynomialRing(GF(2));

Als nächstes werden wir die GAP-Variable xder Unbestimmtheit des Rings zuweisen R. Wenn ich jetzt xin GAP sage , weiß das System, dass ich von der Unbestimmtheit des Rings spreche R.

x:=IndeterminatesOfPolynomialRing(R);
x:=x[1];

Als nächstes haben wir zwei Funktionen, die Inverse Maps voneinander sind. Diese Karten sind beide in, aber sie sind nicht strukturerhaltend, sodass ich mir keinen besseren Weg vorstellen kann, sie in GAP zu implementieren. Es gibt mit ziemlicher Sicherheit einen besseren Weg, wenn Sie es wissen, bitte kommentieren Sie!

Die erste Map to_ringnimmt eine Ganzzahl und ordnet sie dem entsprechenden Ringelement zu. Dies geschieht durch eine Konvertierung in einen Binäralgorithmus, bei dem jedes 1, was in einer Binärzahl erscheint, durch ein ersetzt wird, x^nwo ndie entsprechende Potenz ist, die 2 annehmen würde, wenn die Zahl tatsächlich binär wäre.

    to_ring:=function(i)
        local n,r; 
        r:=0*x;                 # initiate r to the zero element of R
        while not i=0 do        # this is a modified binary algorithm
            n:=0;
            while 2^n<=i do
                n:=n+1;
            od;
            n:=n-1;
            r:=r+x^n;
            i:=i-2^n;
        od;
        return r;
    end;

Die nächste Funktion kehrt dies um. to_intsNimmt ein Ringelement und ordnet es der entsprechenden Ganzzahl zu. Dazu erhalte ich eine Liste der Koeffizienten des Polynoms, und für jeden Koeffizienten ungleich Null wird das Ergebnis um 2 ^ n erhöht, auf dieselbe Weise, wie wir Binär in Dezimal umwandeln würden.

    to_ints:=function(r)
        local c,i,n;
        i:=0;n:=0;
        for c in CoefficientsOfUnivariatePolynomial(r) do
            if c=Z(2)^0 then          

                 # ^-- Right here you'll notice that the Z(2) is basically '1' in GF(2). So Z(2)^0 ~ 1 and Z(2)*0 ~ 0  
                 # effectively, this line checks for nonzero coefficients

                n:=n+2^i;
            fi;
            i:=i+1;
        od;
        return n;
    end;

Im letzten Schritt rufen wir diese Funktionen auf. Wir nehmen die beiden Ganzzahleingaben, konvertieren sie in Elemente im Ring R, multiplizieren diese Elemente dann und senden das Produkt zurück zu den Ganzzahlen.

return to_ints( to_ring(i)*to_ring(j));

Ruby, 76 75 73 Bytes

a,b=$*.map{|x|x.to_i}
o=0
while(b>0)
o^=a&-(b&1)
a<<=1
b>>=1
end
puts(o)

Ruby, 60 Bytes (nur Funktion, keine E / A)

def t(a,b)
o=0
while(b>0)
o^=a&-(b&1)
a<<=1
b>>=1
end
t
end

Mathematica, 40 Bytes

BitXor@@(#2BitAnd[#,2^Range[0,Log2@#]])&

Dart, 34 32 Bytes

m(a,b)=>a<1?0:a%2*b^m(a~/2,b*2);

Einfache rekursive Implementierung.

Gnuplot, 29 Bytes

m(a,b)=a<1?0:a%2*b^m(a/2,b*2)   

genau wie bei Dart (so)

GNU Assembler (x86_64 Mac OS X), 97 Byte

Dies ist eine korrekte Funktion, die von C aus aufgerufen werden kann:

.text
.globl _f
_f:
movq %rdi,%xmm0;movq %rsi,%xmm1;pclmulqdq $0,%xmm1,%xmm0;movq %xmm0,%rax;ret

& kann mit diesem C-Programm getestet werden:

#include <stdio.h>
int f(int a, int b);
#define p(a,b) printf("%d %d %d\n", a, b, f(a, b))
int main(void)
{
    p(0,1);
    p(1,2);
    p(9,0);
    p(6,1);
    p(3,3);
    p(2,5);
    p(7,9);
    p(13,11);
    p(5,17);
    p(14,13);
    p(19,1);
    p(63,63);
}

Beachten Sie, dass Sie unter Mac OS X clang -x cC & nicht C ++ verwenden müssen , um es zu kompilieren.

Für Linux (wenn ich mich recht erinnere) wäre der Code 95 Bytes:

.text
.globl f
f:
movq %rdi,%xmm0;movq %rsi,%xmm1;pclmulqdq $0,%xmm1,%xmm0;movq %xmm0,%rax;ret

Seltsamerweise ist diese Version tatsächlich länger als die Definition der Funktion in der Inline-Assemblierung, aber diese war länger als die reine C-Lösung, die wir bereits haben, und deshalb habe ich mich für die Assemblierung entschieden.

bearbeiten

Wenn es nach der zusammengesetzten Größe (ohne Etiketten usw.) gezählt wird, dann ist es

x86_64-Assembler, 22 Byte:

0:  66 48 0f 6e c7          movq         %rdi,  %xmm0
5:  66 48 0f 6e ce          movq         %rsi,  %xmm1
a:  66 0f 3a 44 c1 00       pclmullqlqdq $0,    %xmm1,%xmm0
10: 66 48 0f 7e c0          movq         %xmm0, %rax
15: c3                      ret

Golflua 68

x,y=I.r("*n","*n")r=0~@i=0,31r=B.x(r,x*B.ls(B.rs(y,i)%2,i+1))$w(r/2)

Entspricht im Prinzip der Java-Antwort von Ypnypn , scheint jedoch die Division durch 2 am Ende erforderlich zu machen, um korrekt zu funktionieren. Nimmt Werte als stdin an, Beispiele unten

> 14 13 
70
> 19 1 
19
> 5 17 
85

Ceylon, 90 Bytes

alias I=>Integer;I x(I a,I b)=>[for(i in 0:64)if(b.get(i))a*2^i].fold(0)((y,z)=>y.xor(z));

Dies ist nur der beschriebene Algorithmus: Multiplizieren Sie amit 2^idem igesetzten Bit bund addieren Sie alle mit xor. Iteriert, 0:64weil Ganzzahlen in Ceylon 64-Bit sind, wenn sie unter JVM ausgeführt werden (niedriger, wenn sie als Javascript ausgeführt werden, aber dannb.get(i) nur false zurückgeben).

Formatiert:

alias I => Integer;

I x(I a, I b) =>
      [
        for (i in 0:64)
            if (b.get(i))
                a * 2^i
      ].fold(0)((y, z) => y.xor(z));

Der Alias ​​speichert hier nur ein einziges Byte.

(nicht konkurrierend) Jelly, 16 Bytes

Ḥ⁴BL’¤Ð¡U×"⁴B¤^/

Probieren Sie es online!