# Produce an XOR table

### Introduction

XOR is a digital logic gate that implements an exclusive or. Most of the times, this is shown as ^. The four possible outcomes in binary:

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0


This can also be seen as addition modulo 2 in binary. In decimal, we need to convert the decimal to binary, 35 = 100011 and 25 = 11001.To compute the XOR value, we place them on top of each other:

100011
11001 ^
--------
111010  = 58 in decimal


The task: When given an integer value N greater than 1, output an XOR table with the size N + 1. For example, N = 5:

 0 1 2 3 4 5
1 0 3 2 5 4
2 3 0 1 6 7
3 2 1 0 7 6
4 5 6 7 0 1
5 4 7 6 1 0


You can see that there is one space in front of each number, because the highest amount in the table has length 1. However, if we take N = 9, we get the following grid:

  0  1  2  3  4  5  6  7  8  9
1  0  3  2  5  4  7  6  9  8
2  3  0  1  6  7  4  5 10 11
3  2  1  0  7  6  5  4 11 10
4  5  6  7  0  1  2  3 12 13
5  4  7  6  1  0  3  2 13 12
6  7  4  5  2  3  0  1 14 15
7  6  5  4  3  2  1  0 15 14
8  9 10 11 12 13 14 15  0  1
9  8 11 10 13 12 15 14  1  0


The highest value has length 2, so the value is right-aligned to length 3 (highest length + 1).

Rules:

• Leading whitespace is not mandatory, only if used (or not) consistently
• You must output a table in the form shown above.
• The padding between columns should be as small as possible
• This is , so the submission with the least amount of bytes wins!
• How much padding is allowed between columns? Only the minimal possible amount? – Martin Ender Dec 27 '15 at 16:01
• @MartinBüttner Yes, the minimal possible amount. I'll add that to the description. – Adnan Dec 27 '15 at 16:02
• – edc65 Dec 27 '15 at 16:13
• Looking at the examples output an XOR table with the size N+1 – edc65 Dec 27 '15 at 16:38
• What is the max value for N? ... (for N==1000000 the size of the table would be near 10 Terabyte) – edc65 Dec 27 '15 at 17:52

# MATL, 10 bytes

0i2$:tXgZ~  The compiler (and in particular this program) now seems to work in Octave, although it still needs some refinement. You can provisionally use this GitHub commit. Edit (Mar 30 '16): Try it online! ### Example >> matl 0i2$:tXgZ~
> 9
0  1  2  3  4  5  6  7  8  9
1  0  3  2  5  4  7  6  9  8
2  3  0  1  6  7  4  5 10 11
3  2  1  0  7  6  5  4 11 10
4  5  6  7  0  1  2  3 12 13
5  4  7  6  1  0  3  2 13 12
6  7  4  5  2  3  0  1 14 15
7  6  5  4  3  2  1  0 15 14
8  9 10 11 12 13 14 15  0  1
9  8 11 10 13 12 15 14  1  0


0i2$: % vector 0, 1, 2, ... up to input number t % duplicate Xg % nd-grid Z~ % bitxor  • Compiler working in Octave coming soon... – Luis Mendo Dec 27 '15 at 18:20 • ... well, hopefully. Any idea about this, anyone? – Luis Mendo Dec 27 '15 at 19:24 • Definitely the right tool for the job. +1 – a spaghetto Dec 27 '15 at 21:55 • After some tweaking, the compiler seems to work in Octave (4.0.0). I need to do more testing, but all the programs I've tried, including this one, work. While I post a new release, here's a link to the current GitHub commit to run this code in Octave. The language hasn't changed (it's still release 5.0.0), so it's earlier than this challenge – Luis Mendo Dec 28 '15 at 1:44 # Bash + BSD utils, 45 eval echo $[{0..1}^{0..1}]|rs -jg1 [1+1]  I've been waiting a long time to find a use for rs. This seems to be a good one. rs may need to be installed on Linux systems. But it runs right out of the box on OS X. • 1 expands to N, and thus echo$[{0..$1}^{0..$1}] expands to echo$[{0..N}^{0..N}]
• This is then evaled:
• The brace expansion expands to $[0^0]$[0^1] $[0^2] ...$[0^N] ... $[N^N] • This is a series of xor arithmetic expansions which expand to one line of terms • rs (reshape) reshapes this line to N+1 rows. -j right justifies, and -g1 gives a gutter-width of 1. This ensures the final output table has minimal width between columns. I've tested up to N=1000, which took 3.8 seconds. Large N is theoretically possible, though bash will run out of memory at some point with the (N+1)² memory usage of the brace expansion. # C, 114 128 152 Edit Simplified space counting, inspired by the work of Khaled A Khunaifer A C function that follows the specs. T(n){int i=0,j,x=1,d=0;while(x<=n)x+=x,++d;for(;i<=n;i++)for(j=0;j<=n;j++)printf("%*d%c",d*3/10+1,i^j,j<n?32:10);}  Try it insert n as input, default 9 Less golfed T(n) { int i=0, j, x=1,d=0; while(x<=n) x+=x,++d; // count the digits // each binary digit is approximately 0.3 decimal digit // this approximation is accurate enough for the task for(;i<=n;i++) for(j=0;j<=n;j++) printf("%*d%c",d*3/10+1, i^j, j < n ? 32:10); // space between columns, newline at end }  • 91 bytes – ceilingcat Jan 8 at 19:06 • @ceilingcat nice. Post it as an answer. – edc65 Jan 9 at 13:31 # JavaScript (ES6) 120 122 Edit 2 bytes saved thx ETHproductions An anonymous function. Note: the number in the table are limited to 7 digits, that is more than reasonable given the overall size of a table allowing for bigger numbers Now I should find a shorter way to get the max columns size, avoiding logarithms n=>(a=Array(n+1).fill(-~Math.log10(2<<Math.log2(n)))).map((m,i)=>a.map((z,j)=>${i^j}.slice(~m)).join).join



Test

f=n=>(a=Array(n+1).fill(-~Math.log10(2<<Math.log2(n)))).map((m,i)=>a.map((z,j)=>       ${i^j}.slice(~m)).join).join\n function update() { var v=+I.value O.textContent = f(v) } update() N: <input id=I type=number value=9 oninput='update()'> <pre id=O></pre> • Awesome, love the use of ~m to capture an extra space. Using a template string can save two bytes: (z,j)=>(7 spaces)${i^j}.slice(~m) – ETHproductions Dec 27 '15 at 20:17
• @ETHproductions 1) good suggestion, thanks 2) how did you manage to put a ... (I cannot even ask it) ... a char(96) inside 2 char(96)? – edc65 Dec 27 '15 at 20:44
• Aha, you just use multiple backticks, like so: (ignore this padding) abcdef (ignore this too) Shows up like this: abcdef – ETHproductions Dec 27 '15 at 21:11

# C, 149 bytes

int i=0,j,n,k=2;char b[256];scanf("%d",&n);while((k*=2)<=n);k^=k-1;while(i++<=n&&putchar(10))for(j=0;j<=n;j++)printf(" %*d",sprintf(b,"%d",k),i-1^j);
---------


Detailed

#include <stdio.h>

int main()
{
int i=0, j, n, k=2;
char b[256] = { 0 };

scanf("%d", &n);

// find max xor value in the table
while((k*=2)<=n); k^=k-1;

printf("> %d ~ %d", k, sprintf(b,"%d",k));

while(i++ <= n && putchar(10))
{
for(j = 0; j <= n;j++)
{
printf(" %*d", sprintf(b,"%d",k), (i-1)^j);
}
}

return 0;
}

• Just like your java post, there is no attempt to align correctly the columns. That's the only difficult part of this challenge. This code gives wrong output when input < 8 or > 64. – edc65 Dec 28 '15 at 9:16
• @edc65 I found out how to align, the max xor value is binary 11..1 to the significant one in the input value n, can be done by first finding the nearest power of 2, then xor it with the previous number, 0001 xor 1110 = 1111 – Khaled.K Dec 29 '15 at 7:43
• Good, you are on the right track now. Still, you should test more: the loop with k gives wrong result for n=8 (and your short answer does not initialize the local variable i to 0) – edc65 Dec 29 '15 at 8:12
• This simpler loop should do: for(k=1;k<=n;)k*=2;k--;. Now I see that is much shorter than my C attempt to the same (mine is better for performance, but performance does not matter in this challenge) – edc65 Dec 29 '15 at 8:16
• @edc65 you need to do 2^k xor 2^k -1 for max{2^k<=n} or 2^k -1 for min{2^k>=n}. to get all 11..1 in there – Khaled.K Dec 29 '15 at 8:30

# C, 103 bytes

Y(n){int i,j=n++;char*f="%2u";while(j/=8)++f[1];for(;j<n;++j,puts(""))for(i=0;i<n;++i)printf(f,i^j);}

• Welcome to Programming Puzzles & Code Golf! For what I can see, your answer, as unfortunately many others here, completey miss the column alignment point. – edc65 Dec 28 '15 at 19:01
• Try it with input 5 (too much space between columns) or 65 (too few) – edc65 Dec 28 '15 at 19:05
• this would be ok at last until 512, at last here... – Ros Dec 29 '15 at 6:26

# Jelly, non-competing

7 bytes This answer is non-competing, since it uses features that postdate the challenge.

0r©^'®G


Try it online!

### How it works

0r©^'®G  Main link. Input: n (integer)

0r       Range; yield [0, ..., n].
©      Save the range in the register.

®   Yield the range from the register.
^'    XOR each integer in the left argument with each integer in the right one.
G  Grid; separate rows by newlines, columns by spaces, with a fixed width for
all columns. Since the entries are numeric, align columns to the right.


# Python 3, 133 131 bytes

import math
n=int(input())
r,p=range(n+1),print
for y in r:[p(end='%%%dd '%len(str(2**int(math.log2(n)+1)-1))%(x^y))for x in r];p()


## R, 38 bytes

Usually R requires a lot of bytes just to format the output. In this case it's quite the opposite. outer which is usually refers to the outer product of two arrays, can when supplied a function perform this across the margins of the vectors. In this case, we apply the bitwise XOR function bitwXor.

names(x)=x=1:scan();outer(x,x,bitwXor)


## CJam, 29 27 bytes

ri:X),_ff{^s2X2b,#s,)Se[}N*


Test it here.

## Explanation

ri      e# Read input and convert to integer.
:X      e# Store in X.
),      e# Get range [0 1 ... X].
_ff{    e# Nested map over all repeated pairs from that range...
^     e#   XOR.
s     e#   Convert to string.
2     e#   Push 2.
X2b,  e#   Get the length of the base-2 representation of X. This is the same as getting
e#   getting the base-2 integer logarithm and incrementing it.
#     e#   Raise 2 to that power. This rounds X up to the next power of 2.
s,    e#   Convert to string and get length to determine column width.
Se[   e#   Pad string of current cell from the left with spaces.
}
N*      e# Join with linefeeds.

• Well, that was quick haha – Adnan Dec 27 '15 at 16:06

MathCAD handles built in tables easily - but has absolutely no bitwise Xor, nor decimal to binary or binary to decimal converters. The for functions iterate through the possible values. The i, a2, Xa and Xb place hold. The while loop actively converts to binary, and while converting to binary also performs the xor function (the little cross with the circle around it). It stores the binary number in a base-10 number consisting of 0's and 1's. This is then converted before being stored in the M matrix via the summation function.

This can easily be golfed down (if only by swapping out the placeholders for shorter ones), but I figured I'd post it and see if anyone can golf down the binary to decimal converter more than anything else.

## k4, 50 bytes

{-1@" "/:'(-|//#:''x)$x:$2/:''~x=/:\:x:0b\:'!1+x;}


E.g.:

  {-1@" "/:'(-|//#:''x)$x:$2/:''~x=/:\:x:0b\:'!1+x;}9
0  1  2  3  4  5  6  7  8  9
1  0  3  2  5  4  7  6  9  8
2  3  0  1  6  7  4  5 10 11
3  2  1  0  7  6  5  4 11 10
4  5  6  7  0  1  2  3 12 13
5  4  7  6  1  0  3  2 13 12
6  7  4  5  2  3  0  1 14 15
7  6  5  4  3  2  1  0 15 14
8  9 10 11 12 13 14 15  0  1
9  8 11 10 13 12 15 14  1  0


## Mathematica, 108 bytes

StringRiffle[Thread[Map[ToString,a=Array[BitXor,{#,#}+1,0],{2}]~StringPadLeft~IntegerLength@Max@a],"
"," "]&


Disregard the error, it's just Thread not knowing what it's doing.

# Emacs Lisp, 193 bytes

(defun x(n)(set'a 0)(set'n(1+ n))(while(< a n)(set'b 0)(while(< b n)(princ(format(format"%%%ss "(ceiling(log(expt 2(ceiling(log n 2)))10)))(logxor a b)))(set'b(1+ b)))(set'a(1+ a))(message"")))


Ungolfed:

(defun x(n)
(set'a 0)
(set'n(1+ n))
(while(< a n)
(set'b 0)
(while(< b n)
(princ
(format
;; some format string magic to get the length of the longest
;; possible string as a format string
(format "%%%ss " (ceiling(log(expt 2(ceiling(log n 2)))10)))
(logxor a b)))
(set'b(1+ b)))
(set'a(1+ a))
;; new line
(message"")))


The output is sent to the *Message* buffer, which would be stdout if x were to be used inside a script.

(x 9)
0  1  2  3  4  5  6  7  8  9
1  0  3  2  5  4  7  6  9  8
2  3  0  1  6  7  4  5 10 11
3  2  1  0  7  6  5  4 11 10
4  5  6  7  0  1  2  3 12 13
5  4  7  6  1  0  3  2 13 12
6  7  4  5  2  3  0  1 14 15
7  6  5  4  3  2  1  0 15 14
8  9 10 11 12 13 14 15  0  1
9  8 11 10 13 12 15 14  1  0


# Python 2, 114 bytes

It took some looking to find a way to do variable-width padding in .format() (some, not a lot) and get it right-adjusted, but I think I've got it all to spec now. Could use more golfing in that width calculation though.

N=input()+1
for i in range(N):print''.join(' {n:>{w}}'.format(w=len(2**(len(bin(N))-2)),n=i^r)for r in range(N))


## Caché ObjectScript, 127 bytes

x(n)s w=$L(2**$bitfind($factor(n),1,100,-1))+1 f i=0:1:n { w$j(i,w) } f i=1:1:n { w !,$j(i,w) f j=1:1:n { w$j($zb(i,j,6),w) } }  Detailed: x(n) set w=$Length(2**$bitfind($factor(n),1,100,-1))+1
for i=0:1:n {
write $justify(i,w) } for i=1:1:n { write !,$justify(i,w)
for j=1:1:n {
write $justify($zboolean(i,j,6),w)
}

}


## Pyke, 8 bytes (non-competing)

hD]UA.&P


Explanation:

         - auto-add eval_or_not_input() to the stack
h        - increment the input
D]      - Create a list containing [inp+1, inp+1]
U     - Create a 2d range
A.^  - Deeply apply the XOR function to the range
P - print it out prettily


Try it here

# Python 2, 77 bytes

n=input()+1
t=range(n)
for i in t: print "%3d"*n % tuple([x^i for x in t])

• Welcome to Programming Puzzles & Code Golf! For what I can see, your answer, as unfortunately many others here, completey misses the column alignment point. – cat Mar 30 '16 at 14:11

# J, 10 bytes

XOR/~@,~i.


Try it online!

# Excel VBA, 95 bytes

Anonymous VBE immediate window function that takes input from range [A1] and outputs to the console.

For y=0To[A1]:For x=0To[A1]:z=x Xor y:?Spc([Len(2^-Int(-Log(A1,2)))]-Len(z))Str(z);:Next:?:Next


# Small Basic, 499 bytes

A script that takes input from the TextWindow object and outputs to the same

a=TextWindow.Read()
For y=0To a
For x=0To a
n=x
b()
z1=z
n=y
b()
l=Math.Max(Array.GetItemCount(z),Array.GetItemCount(z1))
o=0
For i=1To l
If z1[i]<>z[i]And(z[i]=1Or z1[i]=1)Then
z2=1
Else
z2=0
EndIf
o=o+z2*Math.Power(2,i-1)
EndFor
TextWindow.Write(Text.GetSubText("      ",1,Text.GetLength(Math.Power(2,Math.Ceiling(Math.Log(a)/Math.Log(2))))-Text.GetLength(o))+o+" ")
EndFor
TextWindow.WriteLine("")
EndFor
Sub b
z=0
c=0
While n>0
c=c+1
z[c]=Math.Remainder(n,2)
n=Math.Floor(n/2)
EndWhile
EndSub


Try it at SmallBasic.com Uses Silverlight and thus must be run in IE or Edge

Select the black console, then type input integer and press Enter.

# APL(NARS), 57 chars, 114 bytes

{∘.{⍺=0:⍵⋄k←⌈/{⌊1+2⍟⍵}¨⍺⍵⋄(2⍴⍨≢m)⊥m←↑≠/{⍵⊤⍨k⍴2}¨⍺⍵}⍨0..⍵}


(NARS2000 0.5.13) test:

  q←{∘.{⍺=0:⍵⋄k←⌈/{⌊1+2⍟⍵}¨⍺⍵⋄(2⍴⍨≢m)⊥m←↑≠/{⍵⊤⍨k⍴2}¨⍺⍵}⍨0..⍵}
q 5
0 1 2 3 4 5
1 0 3 2 5 4
2 3 0 1 6 7
3 2 1 0 7 6
4 5 6 7 0 1
5 4 7 6 1 0
q 1
0 1
1 0
q 9
0 1  2  3  4  5  6  7  8  9
1 0  3  2  5  4  7  6  9  8
2 3  0  1  6  7  4  5 10 11
3 2  1  0  7  6  5  4 11 10
4 5  6  7  0  1  2  3 12 13
5 4  7  6  1  0  3  2 13 12
6 7  4  5  2  3  0  1 14 15
7 6  5  4  3  2  1  0 15 14
8 9 10 11 12 13 14 15  0  1
9 8 11 10 13 12 15 14  1  0


# Perl 5-n, 62 bytes

for$i(0..$_){printf+(" %".(0|log).d)x($_+1).$/,map$_^$i,0..\$_}


Try it online!

# Go, 145 bytes

A function literal which prints to STDOUT. Abuses Sprintf heavily.

import ."fmt"
func(n int){s:=Sprintf
n++
for i:=0;i<n*n;i++{Printf(s(" %%%dd",len(s("%d",1<<len(s("%b",n-1))-1))),i/n^i%n)
if-^i%n<1{Println()}}}


Try it online! - it appears the Go installation on TIO is older than on my machine, this code runs perfectly locally:

go run "xortable.go" (with n=10)
0  1  2  3  4  5  6  7  8  9 10
1  0  3  2  5  4  7  6  9  8 11
2  3  0  1  6  7  4  5 10 11  8
3  2  1  0  7  6  5  4 11 10  9
4  5  6  7  0  1  2  3 12 13 14
5  4  7  6  1  0  3  2 13 12 15
6  7  4  5  2  3  0  1 14 15 12
7  6  5  4  3  2  1  0 15 14 13
8  9 10 11 12 13 14 15  0  1  2
9  8 11 10 13 12 15 14  1  0  3
10 11  8  9 14 15 12 13  2  3  0


## Explanation

First, we declare the function's arguments (a single integer n) and alias Sprintf to s, as we use it many times later.

func(n int){s:=Sprintf
n++
...
}


Notice that we also increment n. Because the table goes up to n and includes, we actually want n+1 rows. Incrementing n here saves bytes later.

Next, we declare the loop; rather than using a two-dimensional loop, we can simply loop one variable i up to n*n, and use i/n and i^n to access the current coordinates.

for i:=0;i<n*n;i++{...}


Now comes the string padding. To work out the padding required, we need to find the largest entry in the table. This will be n, but with all its non-leading binary 0s changed to 1s. So, we format n into its binary representation, find its length, right-shift 1 by this amount, and decrement.

1<<len(s("%b",n-1))-1


We now format this into base 10 and find its length.

len(s("%d",...))


This, plus 1 is the width that entries should be padded to. Using %Kd pads an integer with spaces to width K, so we create the padding string by using Sprintf once again (note that using a leading space here is a byte shorter than using a +1 for the length):

s(" %%%dd",...)


Now, we print the entry in the XOR table (given by i/n^i%n) via this string format:

Printf(...,i/n^i%n)


Finally, if we have reached the end of a row, we output a newline. We check if (i+1) % n == 0 in the golfiest way possible:

if-^i%n<1{Println()}


# APL, 20 bytes

 {2⊥¨∘.≠⍨↓⍉2⊥⍣¯1⍳⍵+1}


Explanation:

 ⍳⍵+1


integers from 0 to n

 2⊥⍣¯1


base 2 encoding

 ↓⍉


create nested of boolean vectors

 ∘.≠⍨


xor matrix

 2⊥¨


base 2 to base 10 conversion

• ⎕←{2⊥¨∘.≠⍨↓⍉2⊥⍣¯1⍳⍵+1}9 in tio.run/##SyzI0U2pTMzJT////… not result in the right matrix – user58988 Dec 25 '19 at 13:36
• tio.run/##SyzI0U2pTMzJT////… Forgot to say index origin is set to 0. And of course “iota omega +1” gives integers from 0 to n – Popov Dec 26 '19 at 15:05
• i try the one with io=0 and work ok, only the first column has a different spaces than the others columns.… but if you say it is ok i reprint my solution.... – user58988 Dec 27 '19 at 21:41