Tujuan Anda adalah untuk mengimplementasikan operasi perkalian XOR ( carryless ), didefinisikan di bawah ini, sesedikit mungkin byte.

Jika kita menganggap bitor XOR ( ^) sebagai penambahan biner tanpa membawa

   101   5
^ 1001   9
  ----  
  1100  12

  5^9=12

kita dapat melakukan perkalian XOR @dengan melakukan perkalian panjang biner tetapi melakukan langkah penambahan tanpa membawa bitor XOR ^.

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

  14@13=70

(Untuk matematikawan, ini adalah perkalian dalam cincin polinomial F_2[x], mengidentifikasi polinomial dengan bilangan alami dengan mengevaluasi pada x=2sebagai polinomial atas Z.)

Perkalian XOR mengubah a@b=b@a, mengasosiasikan (a@b)@c=a@(b@c), dan mendistribusikan melalui bitor XOR a@(b^c)=(a@b)^(a@c). Bahkan, itu adalah operasi unik yang cocok dengan perkalian a@b=a*bkapanpun adan bmerupakan kekuatan 2suka 1,2,4,8....

Persyaratan

Ambil dua bilangan bulat non-negatif sebagai input dan output atau cetak produk-XOR mereka. Ini harus berupa angka atau representasi string desimalnya, bukan ekspansi binernya. Bytes paling sedikit menang.

Jangan khawatir tentang bilangan bulat bilangan bulat.

Berikut adalah beberapa kasus uji yang diformat sebagai 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

kode mesin x86: 7 byte

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

Hanya dua instruksi. pclmulqdqmelakukan pengangkatan berat, itu benar-benar menerapkan jenis xor-multiplikasi. retuntuk membuatnya menjadi fungsi yang bisa dipanggil, mudah-mudahan memenuhi persyaratan "keluaran" hasilnya (dalam nilai pengembalian, xmm0). Menempatkan argumen integer dalam xmmargs agak tidak biasa, tapi saya harap Anda akan memaafkan saya.

Z80, 11 byte

B7 CB 32 30 01 B3 C8 CB 23 18 F6   

Kode ini disebut sebagai fungsi. adan bberada dalam Ddan E(urutan tidak masalah) dan jawabannya disimpan Aketika kode kembali (tidak ada fungsi 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

Ini menghasilkan hasil yang benar untuk semua input pengujian kecuali 63@63yang kembali 85karena semua register adalah 8-bit dan 1365 mod 256 = 85 (integer overflow).

C, 44 38 byte

Berkat nimi, kami sekarang menggunakan rekursi untuk 6 byte lebih sedikit!

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

Kita mendefinisikan fungsi fyang mengambil a, b.

Ini bisa disebut seperti:

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

Output yang mana:

13 @ 14 = 70

Coba test case online !

Pyth, 13 12 byte

uxyG*HQjvz2Z

Demonstrasi.

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.

Versi lama, 13 byte:

xFm*vz.&Q^2dQ

Demonstrasi.

CJam, 14 13 byte

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

Bagaimana itu bekerja :

Pertama-tama kita mendapatkan hasil perkalian panjang dan kemudian bekerja naik mulai dari dua pasangan terbawah.

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

Cobalah online di sini

J, 14 byte

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

Pemakaian:

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

Penjelasan (kebanyakan membaca dari kanan ke kiri; udan vberdiri untuk fungsi sewenang-wenang):

• u&.#:berlaku uuntuk vektor representasi biner dari angka-angka input kemudian putar hasilnya kembali ke integer ( u&.v == v_inverse(u(v(input_1), v(input_2))))
• */produk ( *) dari input dalam produk Descartes ( /) dari dua vektor biner
• v(u@)berlaku uuntuk v(untuk produk Descartes)
• u/.berlaku uuntuk setiap anti-diagonal produk Descartes (anti-diagonals mewakili digit 1, 2, ... dalam representasi biner)
• ~:/mengurangi ( /) anti-diagonal dengan operasi XOR (~: )
• Langkah terakhir adalah menghasilkan bilangan bulat dari vektor biner yang ditangani titik pertama.

Cobalah online di sini.

Python 2, 35 byte

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

Sebut seperti f(13, 14). Saya pikir sebagian besar bahasa dengan konstruksi yang sama akan bertemu pada sesuatu seperti ini.

Jawa, 62

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

Diperluas

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 byte

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

Terjemahan dari jawaban C @ BrainSteel. Contoh penggunaan:

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

Menghitung opsi baris perintah sebagai satu. Input diambil dariSTDIN , dipisahkan ruang.

Penggunaan sampel:

$ 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 byte

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

Ini menciptakan fungsi rekursif f yang mengambil dua bilangan bulat dan mengembalikan produk XOR dari input.

Tidak Disatukan:

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

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

Menyimpan beberapa byte dengan dorongan dari Sp3000!

Python 2, 104 91 78 66 byte

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

Ambil bit bdalam urutan terbalik, berakhir sebelum Anda menekan '0b'pada awal string. Lipat gandakan masing-masing dengan adan xordengan total, lalu bergeser ke kiri a. Kemudian cetak total.

Pergi, 63 byte

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

Contoh lengkap:

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

CELAH , 368 Bytes

Untuk matematikawan, ini adalah perkalian dalam cincin polinom F_2 [x], mengidentifikasi polinomial dengan bilangan asli dengan mengevaluasi pada x = 2 sebagai polinomial lebih dari Z.

Tentu, mari kita lakukan itu! (ini hanya golf longgar, intinya lebih ke pindah ke F ₂ [x] dan melakukan perhitungan lebih dari upaya untuk menjadi entri yang menang)

Ini kodenya

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;

Berikut adalah kode yang tidak dipisahkan dengan penjelasan:

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;

Oke, jadi pertama-tama, kita buat cincin polinomial univariat di atas bidang F ₂ dan sebut saja R. Perhatikan bahwa GF(2)F ₂ dalam GAP.

R:=PolynomialRing(GF(2));

Selanjutnya, kita akan menetapkan variabel GAP xke tak tentu cincin R. Sekarang, setiap kali saya mengatakan xdalam GAP, sistem akan tahu saya berbicara tentang tak tentu cincin R.

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

Selanjutnya, kami memiliki dua fungsi, yang merupakan peta terbalik satu sama lain. Peta-peta ini sama-sama masuk, tetapi tidak melestarikan struktur, jadi saya tidak tahu cara yang lebih baik untuk mengimplementasikannya dalam GAP. Hampir pasti ada cara yang lebih baik, jika Anda mengetahuinya, silakan komentar!

Peta pertama, to_ringmengambil bilangan bulat dan memetakannya ke elemen cincin yang sesuai. Ia melakukan ini dengan menggunakan konversi ke algoritma biner, di mana setiap 1yang akan muncul dalam biner digantikan oleh di x^nmana nadalah kekuatan yang tepat yang akan diambil 2 jika angka itu memang biner.

    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;

Fungsi selanjutnya membalikkan ini. to_intsmengambil elemen cincin dan memetakannya ke integer yang sesuai. Saya melakukan ini dengan mendapatkan daftar koefisien polinomial dan untuk setiap koefisien bukan nol, hasilnya meningkat 2 ^ n, dengan cara yang sama kita akan mengkonversi biner ke desimal.

    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;

Untuk langkah terakhir, kami memanggil fungsi-fungsi ini. Kami mengambil dua input bilangan bulat, mengubahnya menjadi elemen-elemen di dalam cincin R, kemudian mengalikan elemen-elemen ini bersama-sama, dan mengirimkan produk kembali ke bilangan bulat.

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

Ruby, 76 75 73 byte

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 byte (hanya fungsi, tanpa I / O)

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

Mathematica, 40 byte

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

Dart, 34 32 byte

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

Implementasi rekursif langsung ke depan.

gnuplot, 29 byte

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

seperti di Dart (lihat di atas)

GNU Assembler (x86_64 Mac OS X), 97 byte

Ini adalah fungsi yang tepat yang dapat dipanggil dari C:

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

& dapat diuji dengan program C ini:

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

Perhatikan bahwa pada Mac OS X, Anda harus menggunakan clang -x c untuk mengompilasinya sebagai C & bukan C ++.

Untuk linux (jika saya ingat benar), kodenya akan menjadi 95 byte:

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

Anehnya, versi ini sebenarnya lebih panjang daripada mendefinisikan fungsi dalam inline assembly, tetapi yang satu itu lebih panjang dari solusi C murni yang sudah kita miliki, jadi saya memutuskan untuk mencoba assembly.

sunting

Jika dihitung berdasarkan ukuran rakitan (tidak termasuk label & c.), Maka itu adalah

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)

Apakah pada dasarnya bithifting yang sama dengan jawaban Java Ypnypn , tetapi tampaknya membutuhkan pembagian dengan 2 pada akhirnya untuk bekerja dengan benar. Mengambil nilai sebagai stdin, contoh di bawah ini

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

Ceylon, 90 byte

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

Ini hanya algoritma seperti yang dijelaskan: kalikan adengan2^ii bit mana saja yang diatur b, dan tambahkan semuanya bersama-sama menggunakan xor. Iterate over 0:64karena Integer 64-bit di Ceylon ketika berjalan di JVM (lebih rendah saat berjalan sebagai Javascript, tapi kemudianb.get(i) hanya mengembalikan false).

Diformat:

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

Brankas alias di sini hanya satu byte.

(non-bersaing) Jelly, 16 byte

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

Cobalah online!