Multiplicação XOR

33

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
xnor
fonte
13
Isso é mais conhecido como "multiplicação sem transporte", que você pode adicionar ao título da pergunta e, com alta probabilidade, a menor entrada é a instrução x86 de 6 bytes PCLMULQDQda extensão CLMUL. Infelizmente, obtive voto negativo pelo meu conhecimento das instruções x86 definidas anteriormente (relacionadas a PEXT/PDEP), então vou deixar isso como um comentário aqui.
Iwillnotexist Idonotexist
@IwillnotexistIdonotexist Obrigado pela observação, é bom ter um nome para o Google.
Xnor 16/05
Se isso acima não é "xor" você tem que chamar de uma maneira diferente como Xorc ou xornc ... Não é xor
RosLuP
1
@RosLuP Não é xor, é multiplicação xor.
Xnor
@boboquack Na verdade, acredito que a multiplicação de nimber é diferente. Por exemplo, possui 2 * 2 == 3. Ambos distribuem sobre a adição de nim, mas o que está neste desafio corresponde à multiplicação em potências de 2, enquanto o nimber em corresponde apenas a 2 ^ (2 ^ n).
Xnor

Respostas:

36

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.

harold
fonte
1
Usando um construído em sons de funcionamento como fazer batota ...
CJ Dennis
4
@CJDennis No meta post Standard Loopholes, não há consenso sobre se deve ou não ser banido. Há 44 votos para banir, 31 votos contra.
Isaacg
1
@isaacg Eu realmente não estou tentando ser exigente, mas a redação da pergunta é: Seu objetivo é implementar a operação de multiplicação XOR (sem transporte) . Essa resposta "implementa" a operação em si ou simplesmente chama a função de outra pessoa? Todas as outras respostas fazem o trabalho duro, muitas vezes dentro de alguns bytes desta resposta. Eu acho que todos eles são muito mais inteligentes e merecem votar mais do que este.
CJ Dennis
8
Eu realmente não me sinto capaz de culpar uma resposta se a pergunta é tão trivial que é implementada diretamente por uma CPU comum, dificilmente se pode obter um nível mais baixo do que isso. Não é particularmente interessante ou memorável, mas parece uma resposta válida, então +1.
Vality
9
Não tenho nenhum problema em usar um built-in para resolver isso - caso contrário, eu não saberia que esse recurso existe.
xnor 21/05
14

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

CJ Dennis
fonte
10

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 !

BrainSteel
fonte
1
Por que não uma versão recursiva f(a,b)={return(b)?(b&1)*a^f(2*a,b/2):0;}?
nimi
@nimi Ah, inteligente! Eu sabia que havia uma maneira de se livrar desse parâmetro idiota. Eu tenho 38 bytes agora. Obrigado!
BrainSteel
1
Bateu para fora 44 ainda é regular 44. :(
Alex A.
As entradas não são negativas, portanto, você pode substituir (b&1)por b%2para salvar mais dois bytes, pois %possui o mesmo nível de precedência da esquerda para a direita que *.
CL-
9

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.

isaacg
fonte
Eu acho que então não há uma boa maneira de evitar vzduas entradas inteiras.
Xnor 15/05
@ xnor Não, infelizmente.
Isaacg
8

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

Optimizer
fonte
7

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.

randomra
fonte
5

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.

Sp3000
fonte
4

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));
    }
}
Ypnypn
fonte
1
Existe uma razão que você prefere for(;i<32;)para while(i<32)? Eles têm o mesmo comprimento, mas o segundo parece ser uma maneira mais natural de escrevê-lo.
Johne
1
@ JohnE Eu acho que isso i++foi originalmente no forloop e foi jogado para a sua posição atual. Como whilenão é menor, não há razão para alterá-lo.
CJ Dennis
3

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]
nimi
fonte
3

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
primo
fonte
3

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!

Alex A.
fonte
2

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.

sirpercival
fonte
2

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 2 [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 2 e o chamamos R. Observe que GF(2)é F 2 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));
Liam
fonte
1

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
Atsby
fonte
1

Mathematica, 40 bytes

BitXor@@(#2BitAnd[#,2^Range[0,Log2@#]])&
alephalpha
fonte
What does mathematica do when you have two@signs in a row?
Pavel
@Pavel f@@{a,b,c,d} = f[a,b,c,d]. reference.wolfram.com/language/ref/Apply.html
alephalpha
1

Dart, 34 32 bytes

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

Straight-forward recursive implementation.

lrn
fonte
1

gnuplot, 29 bytes

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

just like in Dart (see above)

Serge Boisse
fonte
1

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
JustinCB
fonte
I'd think you'd measure assembly languages by their compiled form though.
Nissa
0

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
Kyle Kanos
fonte
0

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.

Paŭlo Ebermann
fonte
0

(non-competing) Jelly, 16 bytes

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

Try it online!

Leaky Nun
fonte