Su objetivo es implementar la operación de multiplicación XOR (sin acarreo ), definida a continuación, en la menor cantidad de bytes posible.

Si pensamos en XOR bit a bit ( ^) como suma binaria sin llevar

   101   5
^ 1001   9
  ----  
  1100  12

  5^9=12

podemos realizar la multiplicación XOR @haciendo una multiplicación larga binaria pero realizando el paso de adición sin llevar como XOR bit a bit ^.

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

  14@13=70

(Para los matemáticos, esto es multiplicación en el anillo polinomial F_2[x], identificando polinomios con números naturales mediante la evaluación de x=2como un polinomio sobre Z.)

La multiplicación XOR conmuta a@b=b@a, asocia (a@b)@c=a@(b@c)y distribuye sobre XOR bit a bit a@(b^c)=(a@b)^(a@c). De hecho, es la única operación de este tipo que coincide con la multiplicación a@b=a*bcuando sea ay bson poderes 2similares 1,2,4,8....

Requisitos

Tome dos enteros no negativos como entrada y salida o imprima su producto XOR. Esto debería ser como números o sus representaciones de cadena decimal, no sus expansiones binarias. Pocos bytes ganan.

No se preocupe por los desbordamientos de enteros.

Aquí hay algunos casos de prueba formateados 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

Solo dos instrucciones. pclmulqdqhace el trabajo pesado, literalmente implementa ese tipo de multiplicación xor. retpara que sea una función invocable, ojalá satisfaga el requisito de "generar" el resultado (en el valor de retorno xmm0). Poner argumentos enteros en argumentos xmmes un poco inusual, pero espero que me perdones.

Z80, 11 bytes

B7 CB 32 30 01 B3 C8 CB 23 18 F6   

El código se llama como una función. ay bestán en Dy E(el orden no importa) y la respuesta se almacena Acuando el código regresa (no hay funciones 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

Produce los resultados correctos para todas las entradas de prueba, excepto la 63@63que se devuelve 85porque todos los registros son de 8 bits y 1365 mod 256 = 85 (desbordamiento de enteros).

C, 44 38 bytes

Gracias a nimi, ¡ahora usamos recursión por 6 bytes menos!

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

Definimos una función fque toma a,b .

Esto se puede llamar así:

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

Qué salidas:

13 @ 14 = 70

¡Pruebe los casos de prueba en línea !

Pyth, 13 12 bytes

uxyG*HQjvz2Z

Demostración.

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ón anterior, 13 bytes:

xFm*vz.&Q^2dQ

Demostración.

CJam, 14 13 bytes

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

Cómo funciona :

Primero obtenemos los resultados de la multiplicación larga y luego avanzamos desde los dos 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

Pruébalo en línea aquí

J, 14 bytes

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

Uso:

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

Explicación (leer principalmente de derecha a izquierda; uy vrepresentar funciones arbitrarias):

• u&.#:se aplica ua los vectores de las representaciones binarias de los números de entrada y luego vuelve el resultado a un entero ( u&.v == v_inverse(u(v(input_1), v(input_2))))
• */productos ( *) de entradas en el producto Descartes ( /) de los dos vectores binarios
• v(u@)aplicar uav (para el producto Descartes)
• u/. aplicar u a todos los anti-diagonales del producto Descartes (los anti-diagonales representan los dígitos primero, segundo, ... en la representación binaria)
• ~:/reduce ( /) un anti-diagonal con operación XOR (~: )
• El último paso es generar un número entero a partir del vector binario del que se ocupa el primer punto.

Pruébelo en línea aquí.

Python 2, 35 bytes

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

Llama como f(13, 14). Creo que la mayoría de los idiomas con una construcción similar convergerán en algo como esto.

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

Una traducción de la respuesta C de @ BrainSteel. Ejemplo 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 la opción de línea de comando como una. La entrada se toma desde un STDINespacio separado.

Uso de la muestra:

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

Esto crea una función recursiva f que toma dos enteros y devuelve el producto XOR de las entradas.

Sin golf:

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

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

¡Ahorré un par de bytes con ánimo de 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

Tome los bits ben orden inverso, terminando antes de presionar '0b'al comienzo de la cadena. Multiplica cada uno por ay xorcon el total, luego desplaza a la izquierda a. Luego imprima el total.

Go, 63 bytes

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

Ejemplo completo:

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

GAP , 368 bytes

Para los matemáticos, esto es multiplicación en el anillo polinomial F_2 [x], identificando polinomios con números naturales mediante la evaluación de x = 2 como un polinomio sobre Z.

Claro, hagámoslo! (esto no se juega con precisión, lo importante era pasar a F ₂ [x] y hacer los cálculos más que cualquier intento de ser una entrada ganadora)

Aquí está el 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;

Aquí está el código no codificado con explicación:

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;

Bien, primero, creamos el anillo polinómico univariante sobre el campo F ₂ y lo llamamos R. Tenga en cuenta que GF(2)es F ₂ en GAP.

R:=PolynomialRing(GF(2));

A continuación, vamos a asignar la variable GAP xa lo indeterminado del anillo R. Ahora, cada vez que digo xen GAP, el sistema sabrá que estoy hablando de lo indeterminado del anillo R.

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

A continuación, tenemos dos funciones, que son mapas inversos entre sí. Estos mapas están en ambos, pero no conservan la estructura, por lo que no pude encontrar una mejor manera de implementarlos en GAP. Es casi seguro que hay una mejor manera, si lo sabes, ¡por favor comenta!

El primer mapa, to_ringtoma un número entero y lo asigna a su elemento de anillo correspondiente. Lo hace mediante el uso de una conversión a algoritmo binario, donde cada1 que aparezca en binario se reemplaza por un x^ndónde nes la potencia adecuada que tomaría 2 si el número fuera realmente binario.

    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;

La siguiente función invierte esto. to_intstoma un elemento de anillo y lo asigna a su número entero correspondiente. Hago esto obteniendo una lista de los coeficientes del polinomio y para cada coeficiente distinto de cero, el resultado aumenta en 2 ^ n, de la misma manera que convertiríamos binario a 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 el paso final, llamamos a estas funciones. Tomamos las dos entradas enteras, las convertimos en elementos en el anillo R, luego multiplicamos estos elementos y enviamos el producto a los enteros.

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 (solo función, sin 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);

Implementación recursiva directa.

gnuplot, 29 bytes

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

al igual que en Dart (ver arriba)

Ensamblador GNU (x86_64 Mac OS X), 97 bytes

Esta es una función adecuada que se puede llamar desde C:

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

& puede ser probado con este programa 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);
}

Tenga en cuenta que en Mac OS X, debe usar clang -x c para compilarlo como C y no como C ++.

Para Linux (si no recuerdo mal), el código sería de 95 bytes:

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

Curiosamente, esta versión es en realidad más larga que la definición de la función en el ensamblaje en línea, pero esa era más larga que la solución C pura que ya tenemos, así que decidí probar el ensamblaje.

editar

Si se cuenta por el tamaño ensamblado (excluyendo las etiquetas, etc.), entonces es

Ensamblador x86_64, 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)

Básicamente realiza el mismo desplazamiento de bits que la respuesta Java de Ypnypn , pero parece requerir la división entre 2 al final para funcionar correctamente. Toma valores como stdin, ejemplos a continuación

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

Ceilán, 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));

Este es solo el algoritmo como se describe: multiplique apor 2^idonde sea que iesté instalado el bit th by agréguelos todos juntos usando xor. Se repite 0:64porque los enteros son de 64 bits en Ceilán cuando se ejecuta en JVM (más bajo cuando se ejecuta como Javascript, pero luego b.get(i)solo devuelve falso).

Formateado:

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

El alias es seguro aquí solo un byte.

(no competitiva) Jelly, 16 bytes

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

Pruébalo en línea!