XOR multiplication

Question

You goal is to implement the operation of XOR (carryless) multiplication, defined below, in as few bytes as possible.

If we think of bitwise XOR (^) as binary addition without carrying

   101   5
^ 1001   9
  ----  
  1100  12

  5^9=12

we can perform XOR multiplication @ by doing binary long-multiplication but doing the adding step without carrying as bitwise XOR ^.

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

  14@13=70

(For mathematicians, this is multiplication in the polynomial ring F_2[x], identifying polynomials with natural numbers by evaluating at x=2 as a polynomial over Z.)

XOR multiplication commutes a@b=b@a, associates (a@b)@c=a@(b@c), and distributes over bitwise XOR a@(b^c)=(a@b)^(a@c). In fact, it is the unique such operation that matches multiplication a@b=a*b whenever a and b are powers of 2 like 1,2,4,8....

Requirements

Take two non-negative integers as input and output or print their XOR-product. This should be as numbers or their decimal string representations, not their binary expansions. Fewest bytes wins.

Don't worry about integer overflows.

Here are some test cases formatted as 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

Answer 1

x86 machine code: 7 bytes

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

Only two instructions. pclmulqdq does the heavy lifting, it literally implements that type of xor-multiplication. ret to make it a callable function, hopefully satisfying the requirement of "outputting" the result (in the return value, xmm0). Putting integer arguments in xmm args is a bit unusual, but I hope you'll forgive me.

Answer 2

Z80, 11 bytes

B7 CB 32 30 01 B3 C8 CB 23 18 F6   

The code is called as a function. a and b are in D and E (the order doesn't matter) and the answer is stored in A when the code returns (there are no I/O functions).

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

It produces the correct results for all test input except 63@63 which returns 85 because all the registers are 8-bit and 1365 mod 256 = 85 (integer overflow).

Answer 3

C, 44 38 bytes

Thanks to nimi, we now use recursion for 6 fewer bytes!

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

We define a function f which takes a, b.

This can be called like:

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

Which outputs:

13 @ 14 = 70

Try the test cases online!

Answer 4

Pyth, 13 12 bytes

uxyG*HQjvz2Z

Demonstration.

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.

---

Old version, 13 bytes:

xFm*vz.&Q^2dQ

Demonstration.

Answer 5

CJam, 14 13 bytes

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

How it works:

We first get the long multiplication results and then work our way up starting from the bottom two pairs.

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

Try it online here

Answer 6

J, 14 bytes

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

Usage:

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

Explanation (reading mostly from right to left; u and v stand for arbitrary functions):

• u&.#: applies u to the vectors of the binary representations of the input numbers then turn the result back to an integer (u&.v == v_inverse(u(v(input_1), v(input_2))))
• */ products (*) of inputs in the Descartes product (/) of the two binary vector
• v(u@) apply u to v (to the Descartes product)
• u/. apply u to every anti-diagonal of the Descartes product (anti-diagonals represent the 1st, 2nd, ... digits in the binary representation)
• ~:/ reduce (/) an anti-diagonal with XOR operation (~:)
• The last step is generating an integer from the binary vector which the first point takes care of.

Try it online here.

Answer 7

Python 2, 35 bytes

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

Call like f(13, 14). I think most languages with a similar construct will converge on something like this.

Answer 8

Java, 62

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

Expanded

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

Answer 9

Haskell, 50 bytes

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

A translation of @BrainSteel's C answer. Usage example:

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]

Answer 10

Julia, 35 33 30 bytes

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

This creates a recursive function f which takes two integers and returns the XOR product of the inputs.

Ungolfed:

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

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

Saved a couple bytes with encouragement from Sp3000!

Answer 11

Perl - 35 Bytes

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

Counting the command line option as one. Input is taken from STDIN, space separated.

Sample usage:

$ 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

Answer 12

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.

Answer 13

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

Answer 14

GAP, 368 Bytes

For mathematicians, this is multiplication in the polynomial ring F_2[x], identifying polynomials with natural numbers by evaluating at x=2 as a polynomial over Z.

Sure, let's do that! (this is only loosly golfed, the point was more to move into F₂[x] and do the calculations more than any attempt at being a winning entry)

Here's the 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;

Here's the ungolfed code with explanation:

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;

Okay, so first off, we create the univariate polynomial ring over the field F₂ and call it R. Note that GF(2) is F₂ in GAP.

R:=PolynomialRing(GF(2));

Next, we are going to assign the GAP variable x to the indeterminate of the ring R. Now, whenever I say x in GAP, the system will know I am talking about the indeterminate of the ring 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!

The first map, to_ring takes an integer and maps it to its corresponding ring element. It does this by using a conversion to binary algorithm, where every 1 that would appear in binary is replaced by an x^n where n is the appropriate power that 2 would take if the number was indeed binary.

    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;

The next function reverses this. to_ints takes a ring element and maps it to its corresponding integer. I do this by getting a list of the coefficients of the polynomial and for each nonzero coefficient, the result is increased by 2^n, in the same way that we would convert binary to 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;

For the final step, we call these functions. We take the two integer inputs, convert them into elements in the ring R, then multiply these elements together, and send the product back to the integers.

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

Answer 15

gnuplot, 29 bytes

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

just like in Dart (see above)

Answer 16

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

Answer 17

Dart, 34 32 bytes

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

Straight-forward recursive implementation.

Answer 18

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 (function only, no I/O)

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

Answer 19

Mathematica, 40 bytes

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

Answer 20

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

Answer 21

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.

Answer 22

(non-competing) Jelly, 16 bytes

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

Try it online!