Seu objetivo é implementar a operação de multiplicação XOR (sem carga ), definida abaixo, no menor número possível de bytes.

Se pensarmos no XOR bit a bit ( ^) como adição binária sem carregar

   101   5
^ 1001   9
  ----  
  1100  12

  5^9=12

podemos realizar a multiplicação de XOR @fazendo uma multiplicação longa binária , mas executando a etapa de adição sem carregar o XOR em bits ^.

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

  14@13=70

(Para matemáticos, isso é multiplicação no anel polinomial F_2[x], identificando polinômios com números naturais, avaliando x=2como um polinômio sobre Z.)

A multiplicação de XOR alterna a@b=b@a, associa (a@b)@c=a@(b@c)e distribui em XOR bit a bit a@(b^c)=(a@b)^(a@c). Na verdade, ele é o único tal operação que corresponde a multiplicação a@b=a*bsempre ae bsão potências de 2como 1,2,4,8....

Exigências

Tome dois números inteiros não negativos como entrada e saída ou imprima seu produto XOR. Devem ser números ou representações de cadeias decimais, não expansões binárias. Menos bytes ganha.

Não se preocupe com estouros de número inteiro.

Aqui estão alguns casos de teste formatados como 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

código de máquina x86: 7 bytes

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

Apenas duas instruções. pclmulqdqfaz o trabalho pesado, literalmente implementa esse tipo de multiplicação xor. retpara torná-lo uma função que pode ser chamada, atendendo, esperançosamente, o requisito de "gerar" o resultado (no valor de retorno xmm0). Colocar argumentos inteiros em xmmargs é um pouco incomum, mas espero que você me perdoe.

Z80, 11 bytes

B7 CB 32 30 01 B3 C8 CB 23 18 F6   

O código é chamado como uma função. ae bestão dentro De E(a ordem não importa) e a resposta é armazenada Aquando o código retorna (não há funções de E / S).

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

Produz os resultados corretos para todas as entradas de teste, exceto 63@63 que retornam 85porque todos os registros são de 8 bits e 1365 mod 256 = 85 (excesso de número inteiro).

C, 44 38 bytes

Graças a nimi, agora usamos recursão para 6 bytes a menos!

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

Nós definimos uma função f que leva a, b.

Isso pode ser chamado como:

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

Quais saídas:

13 @ 14 = 70

Experimente os casos de teste online !

Pitão, 13 12 bytes

uxyG*HQjvz2Z

Demonstração.

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.

Versão antiga, 13 bytes:

xFm*vz.&Q^2dQ

Demonstração.

CJam, 14 13 bytes

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

Como funciona :

Primeiro obtemos os longos resultados de multiplicação e depois avançamos a partir dos dois pares inferiores.

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

Experimente online aqui

J, 14 bytes

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

Uso:

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

Explicação (lendo principalmente da direita para a esquerda; ue vsignifica funções arbitrárias):

• u&.#:aplica u- se aos vetores das representações binárias dos números de entrada e, em seguida, retorne o resultado a um número inteiro ( u&.v == v_inverse(u(v(input_1), v(input_2))))
• */produtos ( *) de entradas no produto Descartes ( /) do vetor binário dois
• v(u@)aplicar ua v(para o produto Descartes)
• u/.aplicam u- se a todas as antiasgonais do produto Descartes (as antiagonais representam os 1º, 2º, ... dígitos na representação binária)
• ~:/reduzir ( /) uma anti-diagonal com a operação XOR (~: )
• O último passo é gerar um número inteiro a partir do vetor binário do qual o primeiro ponto trata.

Experimente online aqui.

Python 2, 35 bytes

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

Ligue como f(13, 14). Eu acho que a maioria das linguagens com uma construção semelhante irá convergir para algo assim.

Java, 62

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

Expandido

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

Uma tradução da resposta C do @ BrainSteel. Exemplo de uso:

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

Contando a opção de linha de comando como uma. A entrada é retirada deSTDIN , espaço separado.

Uso da amostra:

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

Isso cria uma função recursiva fque pega dois números inteiros e retorna o produto XOR das entradas.

Ungolfed:

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

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

Economizou alguns bytes com o incentivo do Sp3000!

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

Take the bits of b in reverse order, ending before you hit the '0b' at the start of the string. Multiply each one by a and xor with the total, then left-shift a. Then print the total.

Go, 63 bytes

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

Complete example:

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

GAP, 368 Bytes

Para os matemáticos, isso é multiplicação no anel polinomial F_2 [x], identificando polinômios com números naturais, avaliando x = 2 como um polinômio sobre Z.

Claro, vamos fazer isso! (isso é apenas pouco jogado, o objetivo era passar para F ₂ [x] e fazer os cálculos mais do que qualquer tentativa de ser uma entrada vencedora)

Aqui está o código

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;

Aqui está o código não destruído com explicação:

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;

Ok, então, primeiro, criamos o anel polinomial univariado sobre o campo F ₂ e o chamamos R. Observe que GF(2)é F ₂ no GAP.

R:=PolynomialRing(GF(2));

Em seguida, vamos atribuir a variável GAP xao indeterminado do anel R. Agora, sempre que eu disser xno GAP, o sistema saberá que estou falando sobre o indeterminado do anel R.

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

Next, we have two functions, which are inverse maps of each other. These maps are both onto, but they are not structure preserving, so I couldn't figure out a better way to implement them in GAP. There almost certainly is a better way, if you know it, please comment!

O primeiro mapa, to_ringpega um número inteiro e mapeia para o seu elemento de anel correspondente. Isso é feito usando um algoritmo de conversão em binário, onde todo o 1que apareceria em binário é substituído por um x^nonde né a potência apropriada que 2 seria necessária se o número fosse realmente binário.

    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;

A próxima função reverte isso. to_intspega um elemento de anel e mapeia para seu número inteiro correspondente. Faço isso obtendo uma lista dos coeficientes do polinômio e, para cada coeficiente diferente de zero, o resultado é aumentado em 2 ^ n, da mesma forma que converteríamos binário em decimal.

    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;

Para a etapa final, chamamos essas funções. Pegamos as duas entradas inteiras, as convertemos em elementos no anel R, depois multiplicamos esses elementos e enviamos o produto de volta aos números inteiros.

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 (somente função, sem E / S)

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

Straight-forward recursive implementation.

gnuplot, 29 bytes

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

just like in Dart (see above)

GNU Assembler(x86_64 Mac OS X), 97 bytes

This is a proper function that can be called from C:

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

& can be tested with this C program:

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

Note that on Mac OS X, you have to use clang -x c to compile it as C & not C++.

For linux(if I remember right), the code would be 95 bytes:

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

Strangely enough, this version is actually longer than defining the function in inline assembly, but that one was longer than the pure C solution we already have, so I decided to try assembly.

edit

If it's counted by the assembled size(excluding any labels &c.), then it's

x86_64 Assembler, 22 bytes:

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)

Does basically the same bitshifting as Ypnypn's Java answer, but seems to require the divide by 2 at the end to work correctly. Takes in values as stdin, examples below

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

This is just the algorithm as described: multiply a by 2^i wherever the ith bit is set in b, and add them all together using xor. Iterates over 0:64 because Integers are 64-bit in Ceylon when running on JVM (lower when running as Javascript, but then b.get(i) just returns false).

Formatted:

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

The alias safes here just a single byte.

(non-competing) Jelly, 16 bytes

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

Try it online!