Twoim celem jest zaimplementowanie operacji mnożenia XOR (bez nośnika ), zdefiniowanej poniżej, w jak najmniejszej liczbie bajtów.

Jeśli myślimy o bitowej XOR ( ^) jako dodatku binarnym bez przenoszenia

   101   5
^ 1001   9
  ----  
  1100  12

  5^9=12

możemy wykonać mnożenie XOR @, wykonując binarne długie mnożenie, ale wykonując krok dodawania bez przenoszenia bitowego XOR ^.

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

  14@13=70

(Dla matematyków jest to mnożenie w pierścieniu wielomianowym F_2[x], identyfikującym wielomiany liczbami naturalnymi, oceniając x=2jako wielomian nad Z.)

Mnożenie XOR dojeżdża a@b=b@a, kojarzy (a@b)@c=a@(b@c)i dystrybuuje w bitowym XOR a@(b^c)=(a@b)^(a@c). W rzeczywistości, jest to wyjątkowa taka operacja, która odpowiada mnożenie a@b=a*bilekroć ai bsą uprawnienia 2jak 1,2,4,8....

Wymagania

Weź dwie nieujemne liczby całkowite jako dane wejściowe i wyjściowe lub wydrukuj ich produkt XOR. Powinny to być liczby lub ich dziesiętne ciągi znaków, a nie ich rozwinięcia binarne. Wygrywa najmniej bajtów.

Nie przejmuj się przepełnieniami liczb całkowitych.

Oto kilka przypadków testowych sformatowanych jako 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

Kod maszynowy x86: 7 bajtów

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

Tylko dwie instrukcje. pclmulqdqwykonuje ciężkie podnoszenie, dosłownie wdraża ten rodzaj mnożenia xor. retaby uczynić ją funkcją wywoływalną, miejmy nadzieję spełniającą wymóg „generowania” wyniku (w wartości zwracanej xmm0). Umieszczanie argumentów w xmmliczbach całkowitych w args jest trochę niezwykłe, ale mam nadzieję, że mi wybaczysz.

Z80, 11 bajtów

B7 CB 32 30 01 B3 C8 CB 23 18 F6   

Kod jest wywoływany jako funkcja. ai bsą w Di E(kolejność nie ma znaczenia), a odpowiedź jest przechowywany w Achwili powrotu kod (istnieją żadne funkcje I / O).

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

Daje prawidłowe wyniki dla wszystkich danych wejściowych testu, z wyjątkiem 63@63tych zwracanych, 85ponieważ wszystkie rejestry są 8-bitowe i 1365 mod 256 = 85 (przepełnienie liczb całkowitych).

C, 44 38 bajtów

Dzięki nim używamy teraz rekurencji dla 6 mniej bajtów!

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

Możemy zdefiniować funkcję f, która trwa a, b.

Można to nazwać tak:

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

Które wyjścia:

13 @ 14 = 70

Wypróbuj przypadki testowe online !

Pyth, 13 12 bajtów

uxyG*HQjvz2Z

Demonstracja.

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.

Stara wersja, 13 bajtów:

xFm*vz.&Q^2dQ

Demonstracja.

CJam, 14 13 bajtów

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

Jak to działa :

Najpierw otrzymujemy długie wyniki mnożenia, a następnie pracujemy w górę, zaczynając od dwóch najniższych par.

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

Wypróbuj online tutaj

J, 14 bajtów

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

Stosowanie:

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

Objaśnienie (czytanie głównie od prawej do lewej; ui voznaczają dowolne funkcje):

• u&.#:stosuje usię do wektorów reprezentacji binarnych liczb wejściowych, a następnie zamień wynik z powrotem na liczbę całkowitą ( u&.v == v_inverse(u(v(input_1), v(input_2))))
• */produkty ( *) danych wejściowych w produkcie Descartesa ( /) dwóch wektorów binarnych
• v(u@)stosuje się udo v(do produktu Descartes)
• u/.stosuje się udo każdej anty-przekątnej produktu Descartes (anty-przekątne oznaczają pierwszą, drugą, ... cyfrę w reprezentacji binarnej)
• ~:/zmniejsz ( /) anty-przekątną z operacją XOR ( ~:)
• Ostatnim krokiem jest wygenerowanie liczby całkowitej z wektora binarnego, którą zajmuje się pierwszy punkt.

Wypróbuj online tutaj.

Python 2, 35 bajtów

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

Zadzwoń jak f(13, 14). Myślę, że większość języków o podobnej konstrukcji zbiega się z czymś takim.

Java, 62

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

Rozszerzony

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 bajtów

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

Tłumaczenie odpowiedzi C @ BrainSteel. Przykład użycia:

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 bajtów

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

Liczenie opcji wiersza poleceń jako jednej. Dane wejściowe są pobierane STDIN, oddzielone spacją.

Przykładowe użycie:

$ 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 bajtów

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

Tworzy to funkcję rekurencyjną, fktóra przyjmuje dwie liczby całkowite i zwraca iloczyn XOR wejść.

Nie golfowany:

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

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

Zapisano kilka bajtów dzięki zachęcie ze Sp3000!

Python 2, 104 91 78 66 bajtów

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

Weź bity bw odwrotnej kolejności, kończąc przed trafieniem '0b'na początku łańcucha. Pomnóż każdy przez ai xorprzez sumę, a następnie przesuń w lewo a. Następnie wydrukuj sumę.

Idź, 63 bajty

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

Kompletny przykład:

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

GAP , 368 bajtów

Dla matematyków jest to mnożenie w pierścieniu wielomianowym F_2 [x], identyfikującym wielomiany liczbami naturalnymi, oceniając przy x = 2 jako wielomian nad Z.

Jasne, zróbmy to! (jest to tylko luźna gra w golfa, chodziło raczej o przejście do F ₂ [x] i wykonanie obliczeń bardziej niż jakakolwiek próba bycia zwycięzcą)

Oto kod

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;

Oto niepoznany kod z wyjaśnieniem:

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;

Dobra, więc po pierwsze, tworzymy pierścień wielomianowy jednowymiarowy nad polem F ₂ i nazywamy go R. Należy pamiętać, że GF(2)jest F ₂ w Gap.

R:=PolynomialRing(GF(2));

Następnie przypiszemy zmienną GAP xdo nieokreślonego pierścienia R. Teraz, ilekroć mówię xw GAP, system będzie wiedział, że mówię o nieokreślonym pierścieniu R.

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

Następnie mamy dwie funkcje, które są odwrotnymi mapami. Obie mapy są włączone, ale nie zachowują struktury, więc nie mogłem znaleźć lepszego sposobu na ich wdrożenie w GAP. Jest prawie na pewno lepszy sposób, jeśli go znasz, proszę o komentarz!

Pierwsza mapa to_ringpobiera liczbę całkowitą i odwzorowuje ją na odpowiadający jej element pierścieniowy. Robi to poprzez użycie algorytmu konwersji do binarnego, w którym każdy, 1który pojawiłby się w binarnym, jest zastępowany przez x^ngdzie njest odpowiednia moc, którą 2 by wziął, gdyby liczba rzeczywiście była binarna.

    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;

Następna funkcja odwraca to. to_intsbierze element pierścienia i mapuje go na odpowiednią liczbę całkowitą. Robię to, uzyskując listę współczynników wielomianu i dla każdego niezerowego współczynnika wynik jest zwiększany o 2 ^ n, w taki sam sposób, w jaki konwertujemy wartość binarną na dziesiętną.

    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;

W ostatnim kroku nazywamy te funkcje. Bierzemy dwa wejścia całkowite, przekształcamy je w elementy w pierścieniu R, a następnie mnożymy te elementy razem i wysyłamy produkt z powrotem do liczb całkowitych.

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

Rubinowy, 76 75 73 bajtów

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 bajtów (tylko funkcja, brak we / wy)

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

Mathematica, 40 bajtów

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

Dart, 34 32 bajty

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

Prosta implementacja rekurencyjna.

gnuplot, 29 bajtów

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

tak jak w Dart (patrz wyżej)

GNU Assembler (x86_64 Mac OS X), 97 bajtów

Jest to właściwa funkcja, którą można wywołać z C:

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

i można przetestować za pomocą tego programu C:

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

Zauważ, że w Mac OS X musisz użyć, clang -x caby skompilować go jako C, a nie C ++.

W przypadku linuxa (o ile dobrze pamiętam) kod będzie miał 95 bajtów:

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

O dziwo, ta wersja jest w rzeczywistości dłuższa niż definiowanie funkcji w asemblerze wbudowanym, ale ta była dłuższa niż rozwiązanie czystego C, które już mamy, więc postanowiłem spróbować asemblera.

edytować

Jeśli jest liczony według złożonego rozmiaru (bez etykiet i innych), to jest

Asembler x86_64, 22 bajty:

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)

Zasadniczo robi to samo przesunięcie bitów, co odpowiedź Java Ypnypna , ale wydaje się, że wymaga dzielenia przez 2 na końcu, aby działać poprawnie. Przyjmuje wartości jako standardowe, przykłady poniżej

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

Cejlon, 90 bajtów

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

To jest po prostu algorytm opisany: pomnożyć aprzez 2^igdziekolwiek ity bit jest ustawiony w b, i dodać je razem za pomocą xor. Iteruje się, 0:64ponieważ liczby całkowite są 64-bitowe na Cejlonie, gdy są uruchomione na JVM (niższe, gdy działają jako JavaScript, ale po b.get(i)prostu zwracają fałsz).

Sformatowany:

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

Alias ​​skrywa tutaj tylko jeden bajt.

(niekonkurujące) galaretka, 16 bajtów

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

Wypróbuj online!