# 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. :) – luser droog Jul 25 '13 at 9:09
• Also related: A simple logic gate calculator – FireFly Nov 7 '14 at 13:39
• Are leading or trailing newlines accepted? – Titus Sep 20 '16 at 17:10
• Yes, extra newlines are fine. – luser droog Sep 20 '16 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!) – luser droog Jul 25 '13 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. – John Dvorak Jul 26 '13 at 3:56
• Nice to see something shorter than Golfscript... – fuenfundachtzig Jul 27 '13 at 6:12
• Reimplemented your solution in postscript – luser droog Mar 7 '14 at 6:45
• @luserdroog Wow. That's a lot of code. Much more readable than the J source code though. :-) Very cool. – Gareth Mar 7 '14 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? – Tim Seguine Mar 20 '14 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". – luser droog Nov 9 '14 at 8:33
• Save a byte: (4⍴2)⊤2⊥⍣¯1 – Adám Jun 16 '16 at 23:42

# Jelly, 42 7 bytes (non-competing)

⁴Ḷ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! – luser droog Sep 18 '16 at 1:41
• @luserdroog That's fine. But, I thought the challenge was newer. – Erik the Outgolfer Sep 18 '16 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. – luser droog Sep 18 '16 at 20:38
• +1 for the 42 to 7 codegolf. That's something you don't see every day (unless done on purpose). – Kevin Cruijssen Sep 19 '16 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". – Erik the Outgolfer Sep 19 '16 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. – Erik the Outgolfer Sep 15 '16 at 11:28
• @EriktheGolfer Feel free to improve, but I think that's the shortest possible version. :) – Cedric Reichenbach Sep 15 '16 at 11:30
• I'm porting this to Sprects. – Erik the Outgolfer Sep 15 '16 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? – Howard Jul 25 '13 at 16:12 • On the other hand you can do 16,zip{','-~n}% – Howard Jul 25 '13 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. – Peter Taylor Jul 25 '13 at 16:55 • Seems to output 4 extra lines of zeros here – aditsu May 16 '14 at 5:00 • @aditsu, works on the online demo. I wonder why the difference. Ruby version, maybe? – Peter Taylor May 16 '14 at 18:37 # 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. – luser droog Nov 17 '14 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)+ :"" – Shaun H Sep 15 '16 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? – luser droog Apr 9 '15 at 18:20 • @luserdroog | operates on floats. 2|3.25 is 1.25. We don't want that. – John Dvorak Apr 9 '15 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}  ## 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. # 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. – msh210 Sep 20 '16 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. – NinjaBearMonkey Nov 14 '14 at 2:09

# Sprects, 44 bytes

 aaaa
bbbb
zozo
zzoo o1111 z0000 b0011 a0101


# MATL (non-competing), 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 (non-competing), 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


# 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... – RosLuP Sep 18 '16 at 8:30
• What would it take to split after the 35 bytes? – Titus Sep 21 '16 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) – Arnauld Sep 21 '16 at 9:41
• hmm ... and .replace(/.{16}/g,"$0\n") has the same length. Too bad. – Titus Sep 21 '16 at 9:59 # 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) ## 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. – Elias Mårtenson Mar 24 '14 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. – luser droog Apr 2 '14 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 ++. – Peter Taylor Jul 27 '13 at 12:10
• Saved 3 by changing main to f. lol – luser droog Nov 10 '16 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.