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
  • 13
    This is better known as "carry-less multiplication", which you might want to add the the question title, and with high probability the smallest entry is the 6-byte x86 instruction PCLMULQDQ from the CLMUL extension. Unfortunately I got downvoted for my knowledge of the x86 instruction set before (Related to PEXT/PDEP), so I'm going to just leave this as a comment here. – Iwillnotexist Idonotexist May 16 '15 at 16:14
  • @IwillnotexistIdonotexist Thanks for the note, it's nice to have a name to Google. – xnor May 16 '15 at 21:04
  • If that above is not "xor" you have to call in a different way as xorc or xornc ... It is not xor – RosLuP Dec 4 '16 at 9:33
  • 1
    @RosLuP It's not xor, it's xor multiplication. – xnor Dec 4 '16 at 9:39
  • @boboquack Actually, I believe nimber multiplication is different. For instance, it has 2*2==3. Both of these distribute over nim addition, but the one in this challenge matches multiplication on powers of 2, whereas the nimber on matches only on 2^(2^n). – xnor Dec 4 '16 at 23:39

22 Answers 22

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.

  • 1
    Using a built in operation sounds like cheating... – CJ Dennis May 17 '15 at 12:59
  • 4
    @CJDennis On the Standard Loopholes meta post, there is no consensus on whether it should be banned or not. There are 44 votes for banning, 31 votes against. – isaacg May 18 '15 at 4:45
  • 1
    @isaacg I'm really not trying to be nit-picky but the wording of the question is: Your goal is to implement the operation of XOR (carryless) multiplication. Does this answer "implement" the operation itself or simply call someone else's function? All the other answers do the hard work themselves, often within a few bytes of this answer. I think they're all a lot cleverer and deserve upvoting more than this one. – CJ Dennis May 18 '15 at 5:22
  • 8
    I don't really feel able to blame an answer if the question is so trivial it is implemented directly by a common CPU, one can hardly get any lower level than that. It isn't particularly interesting or memorable but does seem a valid answer, so +1. – Vality May 18 '15 at 9:03
  • 9
    I have no problem with a built-in being used to solve this -- otherwise, I wouldn't have know such a built-in exists. – xnor May 21 '15 at 4:12

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

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!

  • 1
    Why not a recursive version f(a,b)={return(b)?(b&1)*a^f(2*a,b/2):0;}? – nimi May 15 '15 at 22:40
  • @nimi Ah, clever! I knew there was a way to get rid of that dumb parameter. I've got 38 bytes now. Thanks! – BrainSteel May 16 '15 at 0:14
  • 1
    Struck out 44 is still regular 44. :( – Alex A. May 16 '15 at 1:35
  • The inputs are non-negative so you can replace (b&1) with b%2 to save a further two bytes since % has the same left-to-right precedence level as *. – CL- May 16 '15 at 8:23

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.

  • I guess then there isn't a good way to avoid vz in taking two integer inputs. – xnor May 15 '15 at 20:51
  • @xnor No, unfortunately. – isaacg May 15 '15 at 20:54

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

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.

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.

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));
    }
}
  • 1
    Is there a reason you prefer for(;i<32;) to while(i<32)? They're the same length, but the second seems like a more natural way to write it. – JohnE May 15 '15 at 23:18
  • 1
    @JohnE I would guess that i++ was originally in the for loop and got golfed to its present position. Since while isn't any smaller there's no reason to change it. – CJ Dennis May 16 '15 at 13:10

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]

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

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!

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

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 F2[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 F2 and call it R. Note that GF(2) is F2 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));

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

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
  • I'd think you'd measure assembly languages by their compiled form though. – Stephen Leppik Jun 6 at 16:21

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!

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.