# Generate a Universal-binary-function Lookup Table

This is tangentially related to my quest to invent an esoteric programming language.

A table of the binary numbers 0 .. 15 can be used to implement a Universal Binary Function using indexing operations. Given two 1-bit inputs X and Y, all 16 possible functions can be encoded in a 4-bit opcode.

X Y  F|0 1 2 3 4 5 6 7 8 9 A B C D E F
- -    - - - - - - - - - - - - - - - -
0 0    0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1    0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0    0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 1    0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
-     -   - -   -   -   -   - -
0    ~X  ~Y ^   &   Y   X   | 1
ZERO    NOT-Y   AND         OR
NOT-X   XOR              ONE


So this set of 16 functions can be applied to binary inputs as the function

U(f,x,y): (f >> ((x<<1) | y)) & 1,

or

U(f,x,y): (f / 2^(x×2 + y)) % 2,

or with indexing or matrix partitioning.

It will be useful to know the most compact way to represent or generate such a table of values for any possible languages to be built upon this type of binary operation.

## The goal:

Generate this exact text output:

0101010101010101
0011001100110011
0000111100001111
0000000011111111


That's it! Shortest-code wins.

• I had an intuition that the APL-family would do well here. :) Commented Jul 25, 2013 at 9:09
• Also related: A simple logic gate calculator Commented Nov 7, 2014 at 13:39
• Are leading or trailing newlines accepted? Commented Sep 20, 2016 at 17:10
• Yes, extra newlines are fine. Commented Sep 20, 2016 at 17:32

## J, 10 (13?) characters

|.|:#:i.16


Number list:

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


to binary:

   #:i.16
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1


Transpose:

   |:#:i.16
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1


Reverse:

   |.|:#:i.16
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1


Do we need to remove the spaces? Looking at the other J answer it seems we do so we'll need to add 3 characters and borrow the 1": from Jan's answer.

• Very nice style of explanation. +1 (damn short, too!) Commented Jul 25, 2013 at 8:55
• As soon as I saw Peter's Golfscript answer I knew I could have done much better. Well, you had already done it. Commented Jul 26, 2013 at 3:56
• Nice to see something shorter than Golfscript... Commented Jul 27, 2013 at 6:12
• Reimplemented your solution in postscript Commented Mar 7, 2014 at 6:45
• @luserdroog Wow. That's a lot of code. Much more readable than the J source code though. :-) Very cool. Commented Mar 7, 2014 at 8:47

## Python 2, 40

for n in 1,2,4,8:print 8/n*('0'*n+'1'*n)


## APL (14)

Assuming ⎕IO=0 (that's a setting):

⎕D[⊖(4⍴2)⊤⍳16]


Explanation:

• ⍳16: numbers [0,16)
• (4⍴2)⊤: encode each number in base 2 using 4 digits
• ⊖: horizontal reverse (so the MSB ends up on top)
• ⎕D[...]: select these values from ⎕D which is the string 0123456789. (A numeric matrix is displayed with spaces between the values, a character matrix is not. So this converts each numerical bit to one of the chars '0' '1').
• Is the first character in the source supposed to look like a square, or am I still missing some fonts? Commented Mar 20, 2014 at 10:37
• @TimSeguine Yes, it's a square, called quad in the APL literature. Variable names beginning with quad are system variables which change the environment. IO = "index origin". Commented Nov 9, 2014 at 8:33
• Save a byte: (4⍴2)⊤2⊥⍣¯1
Commented Jun 16, 2016 at 23:42

# Jelly, 42 7 bytes

⁴ḶBUz0Y


Try it online!

Thanks to Dennis for his help. Here is the first message, here is the last (other discussions also occured). With his help, I apparently (almost) square-rooted the score.

• Since the language is newer than question, I can't accept it as answer. Definitely in the running for the bounty, tho! Commented Sep 18, 2016 at 1:41
• @luserdroog That's fine. But, I thought the challenge was newer. Commented Sep 18, 2016 at 8:42
• I know what you mean, it doesn't feel like that long ago that I posted it. But even my own inca2, at 2 years old, is too young a language. Commented Sep 18, 2016 at 20:38
• +1 for the 42 to 7 codegolf. That's something you don't see every day (unless done on purpose). Commented Sep 19, 2016 at 14:18
• @KevinCruijssen Why should it be ever done on purpose? I'm just a Jelly newbie (I know Python 2 and 3 well), so I did it on a string way, while I "need to treat Jelly as an array-manipulating language". Commented Sep 19, 2016 at 14:33

# ///, 51 bytes

Try it online

/a/0101/aaaa
/b/0011/bbbb
/z/0000//o/1111/zozo
zzoo

• Welcome to PPCG! You beat me to it. Commented Sep 15, 2016 at 11:28
• @EriktheGolfer Feel free to improve, but I think that's the shortest possible version. :) Commented Sep 15, 2016 at 11:30
• I'm porting this to Sprects. Commented Sep 15, 2016 at 11:32

## GolfScript (18 17 15 chars)

(With thanks to Howard)

16,zip{','-~n}%


I don't understand why the 10-char

16,zip{n}/


doesn't work; I suspect that a bug in the standard interpreter is resulting in unsupported types on the stack.

An alternative at 18 characters which I understand fully is:

4,{2\?.2,*$8@/*n}%  A more mathematical approach is a bit longer, at 28 chars: 4,{2.@??)2.4??.@/+2base(;n}/  A lot of that is for the base conversion and zero-padding. Without those, it drops to 19 chars, 4,{2.@??)2.4??\/n}/  with output 21845 13107 3855 255  • It was asked for exact text output - why should 16,zip{n}/ work then? Commented Jul 25, 2013 at 16:12 • On the other hand you can do 16,zip{','-~n}% Commented Jul 25, 2013 at 16:26 • @Howard, I think that zip should return an array of arrays, but it actually seems to return an array of Ruby arrays (is my best guess). Whatever the elements are, applying    to them doesn't affect the way they print, which is unlike any of the 4 GolfScript data types. You're right that ','- seems to turn them into normal arrays: nice trick. Commented Jul 25, 2013 at 16:55 • Seems to output 4 extra lines of zeros here Commented May 16, 2014 at 5:00 • @aditsu, works on the online demo. I wonder why the difference. Ruby version, maybe? Commented May 16, 2014 at 18:37 ## Postscript 1081771267774 70 [43690 52428 61680 65280] {16{dup 2 mod =only 2 idiv}repeat<>=}forall  Reversed the values for a simpler mod- off method. ## 151131 119 Applying a more APL-ish approach. edit: replaced string chopping and array zipping with indexing and for-loops. [[0 1 15{}for]{16 add 2 5 string cvrs}forall]4 -1 1{0 1 15{2 index exch get 1 index 1 getinterval =only}for pop<>=}for  Indented: [[0 1 15{}for]{16 add 2 5 string cvrs}forall] 4 -1 1{ % [] i 0 1 15{ % [] i j 2 index exch get % [] i [](j) 1 index 1 % [] i [](j) i getinterval % [] i [](j)<i> =only % [] i }for pop<>= % [] }for  Reimplementing the functions used in the winning J answer leads to this (with a lot of support code). -1 16 i + #: |: |.{{==only}forall()=}forall  i here is 1-based vector described in Iverson's Elementary Functions, hence the -1 ... + to produce 0 .. 15. # CJam - 16 4,{G,f{\m>2%}N}/  Equivalent java code (as explanation): public class Lookup { public static void main(final String... args) { for (int i = 0; i < 4; ++i) { for (int j = 0; j < 16; ++j) { System.out.print((j >> i) % 2); } System.out.println(); } } }  # Javascript (ECMA6), 67 s=(k,n)=>n-.5?s((k<<n/2)^k,n/2)+"0".repeat(n)+k.toString(2)+"\n":""  To use this, call s(255,8)  Bitshift! And also XOR and a bit of recursion. The first thing to notice is that if we take any line and you shift it (# of continuous 0's) / 2 left, we get a nice XOR to get the next line up. For example, 0000000011111111 //line 4 0000111111110000 //shifted 4 to the left  XOR these bitwise give us 0000111100001111 //XOR'ed. This is line 3!  which is the next line up (line 3). Applying the same process for line 3, shift 2 left and we get... 0000111100001111 0011110000111100  XOR'ed gives 0011001100110011  which is line 2. Notice that the amount we shift halves each time. Now we simply call this function recursively, with 2 arguments. The integer value of this line, and N, which is how much we need to shift. When we do recursing just pass in the shifted XOR'ed value and n/2. "0".repeat(n)  is to pad 0's to the beginning of each line because toString takes out leading 0's. • +1 Very cool. I had not noticed that pattern before. Commented Nov 17, 2014 at 4:59 • A couple byes can be cut off this by bit shifting n instead of dividing it, and replacing the new line with a template string: s=(k,n)=>n?s((k<<n/2)^k,n>>1)+"0".repeat(n)+k.toString(2)+ :"" Commented Sep 15, 2016 at 19:05 ### J, 21 characters 1":<.2|(2^i.4)%~/i.16  • i.16 is a list of 0..15 • 2^i.4 is a list (1,2,4,8) • %~/ produces the table of divisions where the left argument forms rows but is the right argument to division • 2| calculates the remainder after dividing [each cell] by two • <. floors that value to 0 or 1 • 1": formats the table with one character per cell • I feel like the floor should not be necessary. The domain of 2| is already 0 or 1, right? Commented Apr 9, 2015 at 18:20 • @luserdroog | operates on floats. 2|3.25 is 1.25. We don't want that. Commented Apr 9, 2015 at 23:23 ### GolfScript, 19 chars Another GolfScript approach 4,{2\?{&!!}+16,%n}%  # Ruby (44) Boring and long: Just printing the 0-padded binary representations of the numbers. [21845,13107,3855,255].map{|i|puts"%016b"%i}  # Perl (36+1) +1 for say, as usual. the double 0 is not a typo :) map say((00x$_,1x$_)x(8/$_)),1,2,4,8

• No need to add 1 for say. perl -e'...' is standard and this requires perl -E'...', no increase in byte count. Anyway, I think it was decided on Code Golf Meta that -M5.01 is free. Commented Sep 20, 2016 at 17:07

# JavaScript (ECMA6), 108

Trying a different approach here. Even though it was encouraged to use binary operators, I allowed myself to submit this solution since the challange is also and I was thinking - how can I reduce the amount of code representing those values...? Bases.

['gut','a43','2z3','73'].forEach(n=>{a=parseInt(n,36).toString(2);


(Line break for convenience).

It's a shame I had to mess with padding with leading zeros, but the point of this code is simply representing the target binary result in Base 36, which are exactly those gut, a43, 2z3, 73 values.

Note: I realize it won't be anywhere near the winning answer, but just for the sake of the idea...

• I was about to do basically the same thing when I saw yours. I got it down to 92 bytes using the technique from my answer to a similar question: alert(['gut','a43','2z3',73].map(n=>(1e8+parseInt(n,36).toString(2)).slice(-16)).join('\n')). This approach uses newlines instead of four alert()s. Commented Nov 14, 2014 at 2:09

# Sprects, 44 bytes

 aaaa
bbbb
zozo
zzoo o1111 z0000 b0011 a0101


# JavaScript (ES6), 58 52 bytes

Builds the string recursively.

f=(n=64)=>n--?f(n)+(!n|n&15?'':
)+(n>>(n>>4)&1):''


### How it works

This recursion is based on the fact that the pattern is made of the vertical binary representation of nibbles 0x0 to 0xF:

  0101010101010101 bit #0 <- Y = 0
0011001100110011 bit #1
0000111100001111 bit #2
0000000011111111 bit #3 <- Y = 3
----------------
0123456789ABCDEF
^              ^
X = 0          X = 15


Therefore, each position (X,Y) in this pattern can be expressed as the Y-th bit of X: X & (1 << Y). We can also isolate this bit with: (X >> Y) & 1. Rather than keeping track of X and Y, we iterate on a single variable n ranging from 0 to 63. So, the formula becomes: (n >> (n >> 4)) & 1. It's actually easier to iterate from 63 to 0, so the string is built in reverse order. In other words, character n-1 is appended to the left of character n.

As a side note, recursion doesn't bring anything here except shorter code.

Without the linebreaks, the code is 35 bytes long:

f=(n=64)=>n--?f(n)+(n>>(n>>4)&1):''


We need 17 more bytes to insert the linebreaks. This could be shortened to 14 bytes if a leading linebreak is acceptable.

### Demo

f=(n=64)=>n--?f(n)+(!n|n&15?'':
)+(n>>(n>>4)&1):''

console.log(f());

• In ideone with both languages JavaScript not compile in the exapme above there is one let more.... It is good the idea of one recursive function...
– user58988
Commented Sep 18, 2016 at 8:30
• What would it take to split after the 35 bytes? Commented Sep 21, 2016 at 9:25
• @Titus - Well. At first glance, I don't have any good solution for that. Here is a (very bad) attempt: (f=(n=64)=>n--?f(n)+(n>>(n>>4)&1):'')().match(/.{16}/g).join\n  (63 bytes) Commented Sep 21, 2016 at 9:41
• hmm ... and .replace(/.{16}/g,"$0\n") has the same length. Too bad. Commented Sep 21, 2016 at 9:59 • f=(n=64)=>n--?f(n)+(n>>(n>>4)&1)+(~n%16?'':"\n"):''; with a trailing newline, which seems more reasonable – l4m2 Commented Jan 27, 2023 at 3:02 # Bash + coreutils, 65 bytes Not the shortest, but not the longest either: for i in {1,2,4,8};{ eval echo \$\[$${0..15}\&i$$/$i];}|tr -d \  (The last character is a space) # MATL, 8 bytes 16:qYB!P  Try it online! ### Explanation 16: % Generate range [1 2 ... 16] q % Subtract 1, element-wise YB % Convert to binary. Gives a 16×4 char array. Each original number is a row ! % Transpose P % Reverse vertically. Implicitly display  # CJam, 10 9 bytes Thanks to @Dennis for 1 byte off! Y4m*zW%N*  Try it online! ### Explanation Y e# Push 2 4 e# Push 4 m* e# Cartesian power of 2 (interpreted as [0 1]) with exponent 4 z e# Zip W% e# Reverse the order of rows N* e# Join with newlines. Implicitly display  ## NARS2000 APL, 22 "01"[⊖1+(4⍴2)⊤(⍳16)-1]  Derived from marinus's APL answer, which doesn't seem to work on NARS2000. Generate vector  ⍳16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  Change to zero-based  (⍳16)-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  Generate shape for encode  (4⍴2) 2 2 2 2  Encode  (4⍴2)⊤(⍳16)-1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1  Adjust for 1-based indexing  1+(4⍴2)⊤(⍳16)-1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2  Reverse primary axis  ⊖1+(4⍴2)⊤(⍳16)-1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2  Index  "01"[⊖1+(4⍴2)⊤(⍳16)-1] 0101010101010101 0011001100110011 0000111100001111 0000000011111111  • You can set ⎕IO to 0, so that you don't have to adjust for 1-based indexing. That brings it down to 16 characters. Commented Mar 24, 2014 at 13:32 • Yes, but then I fear it's too similar to the other APL answer and wouldn't deserve to be here at all. Commented Apr 2, 2014 at 4:44 # C, 73 chars i;main(){for(;i<64;)i&15||puts(""),putchar(48|1&~0xFF0F0F33335555>>i++);}  This is just a general solution for outputting 64 bits in four 16-bit blocks; you just need to change the number 0xFF0F0F33335555 to output an other bit sequence. simplified & ungolfed: int main() { int i; for(i = 0; i < 64; i++) { if(i % 16 == 0) { puts(""); } int bit = ~0xFF0F0F33335555 >> i; bit &= 1; putchar('0' + bit); } }  # Haskell, 73 Yikes, 73 chars! I can't for the love of god get this any smaller though. r=replicate f n=r(div 8n)("01">>=r n)>>=id main=mapM(putStrLn.f)[1,2,4,8]  The real sad part about this is that if you were to echo the output using bash, you'd only need 74 characters. # JavaScript (ES5) 69 for(x="";4>x;x++){z="";for(n=0;16>n;)z+=1-!(n++&1<<x);console.log(z)} # inca2, 3327 24 4 16#(,2|(~16)%.2^~4){D  This is based on Jan Dvorak's answer. inca2 is able to execute this as of yesterday's bugfixes. Technically invalid since the language was invented after the question, but invention of a language was part of my goal in posing the question. So here's some payback in gratitude to the other answers. :) Explanation: 4 16#(,2|(~16)%.2^~4){D (~16) integers 0 .. 15 2^~4 first 4 powers of 2: 1 2 4 8 (~16)%.2^~4 division table 2| mod 2 (and floor)  transpose , ravel ( ){D map to chars '0'..'9' 4 16# reshape to 4x16  Some of the parentheses should be unnecessary, but apparently there are some remaining issues with my interpretation of the grammar. And "ravel => map => reshape" is really clumsy: map needs to be smarter. Edit: bugfixes allow elimination of parens. Factoring the base conversion into a separate function N:x|y%.x^~1+[]/x.y yields this 19 16 char version. 4 16#(,2N~16){D  And while I'm cheating anyway here, I've gone ahead and made this a built-in function. But, even though it's a niladic function (not requiring an argument), there is no support for niladic functions, and it must be supplied with a dummy argument. # inca2, 2 U0  # Pyth 24 / 26 The shortest method was grc's answer translated to Pyth which I felt was cheap so I did my own method: ### Mine: 26 characters  mpbjk*/8dS*d[0 1)[1 2 4 8  ### grc's: 24 characters Fd[1 2 4 8)*/8d+*\0d*\1d  ## C++ 130 Converts hex to binary #define B std::bitset<16> #define C(x) cout<<x<<endl; void main(){ B a(0xFF),b(0xF0F),c(0x3333),d(0x5555); C(d)C(c)C(b)C(a) }  # Haskell (Lambdabot), 47 bytes unlines$reverse$transpose$replicateM 4['1','0']


Kinda cheaty because it uses transpose from Data.List and replicateM from Control.Monad, however both are loaded by default from Lambdabot.

Also, I'm sure there is room for improvement, just wanted to share the idea

# Julia (39 Bytes)

Second script I've ever written in Julia, gotta admit I'm liking Julia, she's a pretty beast.

hcat(map(x->collect(bin(x,4)),0:15)...)


Returns

[0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]


Explanation:

• bin(x,4) - Convert int to binary integer with padding to 4 characters.
• collect(_) - Split string into char array.
• map(x->_,0:15) - Do this for the first 16 digits in the range.
• hcat(_...) - Splat and horizontally concatenate into a matrix.

## C 83777674 71

x;f(n){for(;x<4;x++,puts(""))for(n=0;n<16;)putchar(49-!(n++&(1<<x)));}


Pretty straightforward.

x;
f(n){
for(;x<4;x++,puts(""))
for(n=0;n<16;)
putchar(49-!(n++&(1<<x)));
}

• There's an easy saving of 2 by not using ?:, and another saving of 1 by moving a ++. Commented Jul 27, 2013 at 12:10
• Saved 3 by changing main to f. lol Commented Nov 10, 2016 at 0:57

# R, 53 41 bytes

A translation of @grc's python answer. Shaved off 12 bytes from the original translation through use of rep()'s each and length arguments (and partial argument matching), and by remembering that 0:1 is equivalent to c(0,1).

for(n in 2^(0:3))print(rep(0:1,e=n,l=16))


for(n in 2^(0:3))print(rep(c(rep(0,n),rep(1,n)),8/n))


You can also attempt a translation of @Gareth's J answer, something like this (34 bytes):

t(e1071::bincombinations(4))[4:1,]


However, it uses a function that's not part of base R, and outputs a matrix which is hard to format into exact printed text like in the specification.