Votre objectif est d’implémenter l’opération de multiplication XOR ( carryless ), définie ci-dessous, avec le moins d’octets possible.

Si nous pensons que XOR ( ^) au niveau des bits est une addition binaire sans porter

   101   5
^ 1001   9
  ----  
  1100  12

  5^9=12

nous pouvons effectuer la multiplication XOR @en effectuant une multiplication binaire longue mais en effectuant l'étape d'ajout sans effectuer de traitement XOR au niveau du bit ^.

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

  14@13=70

(Pour les mathématiciens, il s'agit d'une multiplication dans l'anneau polynomial F_2[x], identifiant des polynômes avec des nombres naturels en évaluant at x=2comme polynôme sur Z.)

La multiplication XOR commute a@b=b@a, associe (a@b)@c=a@(b@c)et distribue sur XOR au niveau du bit a@(b^c)=(a@b)^(a@c). En fait, c’est l’unique opération de ce type qui correspond à la multiplication à tout a@b=a*bmoment aet qui bsont des pouvoirs 2similaires 1,2,4,8....

Exigences

Prenez deux entiers non négatifs en entrée et en sortie ou imprimez leur produit XOR. Cela devrait être sous forme de nombres ou leurs représentations en chaîne décimale, pas leurs développements binaires. Le moins d'octets gagne.

Ne vous inquiétez pas des débordements d'entiers.

Voici quelques cas de test au format 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

Code machine x86: 7 octets

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

Seulement deux instructions. pclmulqdqfait le gros du travail, il met littéralement en œuvre ce type de multiplication xor. retpour en faire une fonction appelable, satisfaisant, nous l'espérons, l'exigence de "sortie" du résultat (dans la valeur de retour, xmm0). Mettre des arguments entiers dans xmmargs est un peu inhabituel, mais j'espère que vous me pardonnerez.

Z80, 11 octets

B7 CB 32 30 01 B3 C8 CB 23 18 F6   

Le code est appelé en tant que fonction. aet bsont dans Det E(l'ordre n'a pas d'importance) et la réponse est stockée Alorsque le code est retourné (il n'y a pas de fonctions d'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

Il produit les résultats corrects pour toutes les entrées de test, à l'exception de celles 63@63renvoyées, 85car tous les registres sont à 8 bits et 1365 mod 256 = 85 (débordement d'entier).

C, 44 38 octets

Grâce à nimi, nous utilisons maintenant la récursion pour 6 octets de moins!

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

On définit une fonction fqui prend a, b.

Cela peut s'appeler comme:

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

Quelles sorties:

13 @ 14 = 70

Essayez les cas de test en ligne !

Pyth, 13 à 12 octets

uxyG*HQjvz2Z

Manifestation.

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.

Ancienne version, 13 octets:

xFm*vz.&Q^2dQ

Manifestation.

CJam, 14 à 13 octets

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

Comment ça marche :

Nous obtenons d’abord les résultats de multiplication longs, puis progressons à partir des deux paires inférieures.

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

Essayez-le en ligne ici

J, 14 octets

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

Usage:

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

Explication (lisant principalement de droite à gauche; uet vreprésenter des fonctions arbitraires):

• u&.#:s'applique uaux vecteurs des représentations binaires des nombres en entrée puis retourne le résultat à un entier ( u&.v == v_inverse(u(v(input_1), v(input_2))))
• */produits ( *) d'entrées dans le produit Descartes ( /) des deux vecteurs binaires
• v(u@)appliquer uà v(au produit Descartes)
• u/.s'applique uà chaque anti-diagonale du produit Descartes (les anti-diagonales représentent les 1er, 2ème, ... chiffres de la représentation binaire)
• ~:/réduire ( /) un anti-diagonal avec opération XOR ( ~:)
• La dernière étape consiste à générer un entier à partir du vecteur binaire pris en charge par le premier point.

Essayez-le en ligne ici.

Python 2, 35 octets

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

Appelle comme f(13, 14). Je pense que la plupart des langues avec une construction similaire vont converger vers quelque chose comme ça.

Java, 62

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

Étendu

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 octets

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

Une traduction de la réponse C de @ BrainSteel. Exemple d'utilisation:

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 octets

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

Compter l'option de ligne de commande comme un. L'entrée est prise à partir d' STDINespaces séparés.

Exemple d'utilisation:

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

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

Cela crée une fonction récursive fqui prend deux entiers et retourne le produit XOR des entrées.

Ungolfed:

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

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

Enregistré quelques octets avec les encouragements de Sp3000!

Python 2, 104 91 78 66 octets

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

Prenez les bits bdans l'ordre inverse, en terminant avant de frapper '0b'au début de la chaîne. Multipliez chaque par aet xoravec le total, puis tournez à gauche a. Puis imprimez le total.

Go, 63 octets

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

Exemple complet:

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

GAP , 368 octets

Pour les mathématiciens, il s'agit d'une multiplication dans l'anneau polynomial F_2 [x], identifiant les polynômes avec des nombres naturels en évaluant à x = 2 en tant que polynôme sur Z.

Bien sûr, faisons ça! (Ce n'est que vaguement joué au golf, le but était plutôt de passer à F ₂ [x] et de faire les calculs plus que toute tentative d'être une entrée gagnante)

Voici le code

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;

Voici le code non-golfé avec explication:

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;

D'abord, nous créons l'anneau polynomial univarié sur le corps F ₂ et l'appelons R. Notez que GF(2)c'est F ₂ dans GAP.

R:=PolynomialRing(GF(2));

Ensuite, nous allons affecter la variable GAP xà l'indéterminé de l'anneau R. Maintenant, chaque fois que je dis xdans GAP, le système saura que je parle de l'indétermination de la bague R.

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

Ensuite, nous avons deux fonctions, qui sont des cartes inverses l’une de l’autre. Ces cartes sont sur les deux, mais elles ne préservent pas la structure, donc je ne pouvais pas trouver un meilleur moyen de les implémenter dans GAP. Il y a presque certainement une meilleure solution. Si vous le savez, veuillez commenter!

La première carte, to_ringprend un entier et le mappe à l'élément anneau correspondant. Pour ce faire, il utilise un algorithme de conversion en binaire, où tout 1ce qui apparaît en binaire est remplacé par un x^noù nest la puissance appropriée que 2 prendrait si le nombre était effectivement binaire.

    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 fonction suivante inverse cela. to_intsprend un élément en anneau et le mappe sur son entier correspondant. Je le fais en obtenant une liste des coefficients du polynôme et, pour chaque coefficient non nul, le résultat est augmenté de 2 ^ n, de la même manière que nous convertirions les valeurs binaires en valeurs décimales.

    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;

Pour la dernière étape, nous appelons ces fonctions. Nous prenons les deux entrées entières, les convertissons en éléments dans l'anneau R, puis multiplions ces éléments ensemble et renvoyons le produit aux entiers.

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

Ruby, 76 75 73 octets

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 octets (fonction uniquement, pas d'E / S)

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

Mathematica, 40 octets

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

Dart, 34 32 octets

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

Implémentation récursive simple.

gnuplot, 29 octets

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

comme dans Dart (voir ci-dessus)

Assembleur GNU (x86_64 Mac OS X), 97 octets

C'est une fonction appropriée qui peut être appelée à partir de C:

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

& peut être testé avec ce programme 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);
}

Notez que sur Mac OS X, vous devez l’utiliser clang -x cpour le compiler en tant que C & non C ++.

Pour Linux (si je me souviens bien), le code serait de 95 octets:

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

Curieusement, cette version est en réalité plus longue que la définition de la fonction dans l'assemblage en ligne, mais celle-ci était plus longue que la solution en C pure que nous avons déjà, alors j'ai décidé d'essayer l'assemblage.

modifier

S'il est compté par la taille assemblée (à l'exclusion des étiquettes, etc.), alors c'est

Assembleur x86_64, 22 octets:

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)

Fait fondamentalement le même changement de bits que la réponse Java de Ypnypn , mais semble exiger que la division par 2 à la fin fonctionne correctement. Prend des valeurs en tant que stdin, exemples ci-dessous

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

Ceylan, 90 octets

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

C'est juste l'algorithme tel que décrit: multipliez apar 2^ioù que le ith soit placé b, et additionnez-les tous en utilisant xor. Itère 0:64parce que les entiers sont à 64 bits dans Ceylan lorsqu'ils sont exécutés sur la machine virtuelle Java (inférieur lors de l'exécution en tant que Javascript, mais b.get(i)ne renvoie ensuite que la valeur false).

Formaté:

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

L'alias coffres ici juste un seul octet.

(non-concurrent) Jelly, 16 octets

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

Essayez-le en ligne!