# XOR multiplication

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.

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

• 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. 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
– user58988
Dec 4 '16 at 9:33
• @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

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

• Using a built in operation sounds like cheating... May 17 '15 at 12:59
• @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. May 18 '15 at 4:45
• @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. May 18 '15 at 5:22
• 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. May 18 '15 at 9:03
• 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!

• 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! May 16 '15 at 0:14
• Struck out 44 is still regular 44. :( 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
• Suggest b%2 instead of (b&1) Sep 21 '20 at 22:04

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

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

• 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. May 15 '15 at 23:18
• @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. May 16 '15 at 13:10

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

## 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


import Data.Bits
_#0=0
a#b=b.&.1*axor2*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]


# Julia, 3533 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! # 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));  # Jelly, 12 bytes BJ’2*U×B{×^/  Try it online! ## How it works BJ’2*U×B{×^/ - Main link. Takes a on the left, b on the right B - Binary representation of a J - Replace each element with its index ’ - Decrement 2* - Raise each to the power 2 U - Reverse B{ - Yield the binary representation of a × - Multiply the bits by the powers × - Multiply b by the results ^/ - Reduce by XOR  # ARM Thumb-2 (NEON), 6 bytes Eat my Thumb, pclmullqlqdqdqdqdq. ARM has boring builtins, too! ef80 0e01 4770  Assembly code:  .syntax unified .arch armv7-a .fpu neon .thumb .globl xormul_boring_neon .thumb_func xormul_boring_neon: // q0[0-8] = d0[0-8] @ d1[0-8] vmull.p8 q0, d0, d1 bx lr  Input: two 8-bit values in d0 and d1 Output: the 16-bit product in q0 This actually multiplies 8 packed bytes together. # ARM Thumb-2, manual, 14 bytes Ok, to make up for it, here is a fully scalar version which does a 32x32 multiply with a 32-bit result. 2300 0849 bf28 4043 0040 d1fa 4770  Assembly code:  .syntax unified .arch armv6t2 .thumb .globl xormul_scalar .thumb_func // r3 <- r0 @ r1 xormul_scalar: // acc <- 0 movs r3, #0 .Lloop: // test each bit in y by using lsrs carry-out lsrs r1, r1, #1 // was the bit set? it cs // if so, acc ^= x eorcs r3, r0 // shift x left lsls r0, r0, #1 // loop while x is non zero bne .Lloop .Lend: // return in r3 bx lr  Equivalent C code: uint32_t xormul_scalar(uint32_t x, uint32_t y) { uint32_t acc = 0; do { if (y & 1) acc ^= x; y >>= 1; } while ((x <<= 1)); return acc; }  The numbers to be multiplied are in r0 and r1, and the result is in r3. It is a fairly basic shift and xor loop. Yet another case of lsls and lsrs being far too useful than they deserve to be. Try it online! (sorta): demo in Travis # Python 2, 1049178 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 ## Ruby, 7675 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@#]])&

• What does mathematica do when you have two@signs in a row? Dec 4 '16 at 9:37
• @Pavel f@@{a,b,c,d} = f[a,b,c,d]. reference.wolfram.com/language/ref/Apply.html Dec 4 '16 at 11:10

## Dart, 34 32 bytes

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


Straight-forward recursive implementation.

# (non-competing) Jelly, 16 bytes

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


Try it online!

# 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. Jun 6 '18 at 16:21 # R, 53 bytes f=function(x,y)if(y,bitwXor(x*y%%2,2*f(x,y%/%2)),0)  Try it online! # JavaScript (Node.js), 29 bytes f=(x,y)=>x&&f(x>>1,y)*2^x%2*y  Try it online! # MMIX, 28 bytes (7 instrs) (jelly xxd) 00000000: e3020000 7aff0001 c60202ff 3f000001 ẉ£¡¡z”¡¢İ££”?¡¡¢ 00000010: 37010101 5b00fffc f8030000 7¢¢¢[¡”‘ẏ¤¡¡  Disassembly: clmul SETL$2,0       // r = 0
0H      ZSOD $255,$0,$1 // loop: t = a odd? b : 0 XOR$2,$2,$255 // r ^= t
SRU  $0,$0,1    // a >>= 1
SLU  $1,$1,1    // b <<= 1
PBNZ $0,0B // iflikely(a) goto loop POP 3,0 // return r  You could get a 128-bit answer out of this with about three more instructions, I think. # 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.

# JavaScript (Node.js), 42 bytes

Port of the Java answer. Go upvote that!

x=>y=>(g=i=>i&&g(--i)^x*((y>>i)%2)<<i)(32)
`

Try it online!