Bijective mapping from integers to a variable number of bits

Question

A variable number of bits is an array of 0 or more bits. So [0, 1] is a variable number of bits, but so is [].

Write a function or program that, given an nonnegative integer returns a variable number of bits such that every integer has a one-to-one (bijective) mapping with an array.

There are an infinite amount of such mappings, you are free to construct one as you please, but it must be one-to-one. Your mapping must conceptually be one-to-one for an arbitrarily sized integer, but it's OK if your implementation fails for large integers due to numerical limits of types in your preferred language (e.g. C's int).

As an example of what is not a one-to-one mapping, is simply listing the binary digits of the integer. In such a system 5 becomes [1, 0, 1] (or 0b101), but it's not one-to-one, because 0b0101 or [0, 1, 0, 1] also means 5.

It should be fairly obvious that a mapping is not one-to-one if it skips an integer (e.g. it doesn't work for 5), but I'd like to make it clear that skipping a variable bit array is also not one-to-one. You must map to every possible variable bit array, including [].

---

Shortest code in bytes wins.

Answer 1

Jelly, 3 bytes

‘BḊ

Same idea as xnor: maps 0 1 2 3 4 ... to [] [0] [1] [0 0] [0 1] ...; the code is basically increment → binary → remove first.

Try it out online.

Answer 2

Python, 20 bytes

lambda n:bin(~n)[4:]

Test:

>> [bin(~n)[4:] for n in range(16)]
['', '0', '1', '00', '01', '10', '11', '000', '001', '010', '011', '100', '101', '110', '111', '0000']

Doing lambda n:bin(n+1)[3:] increments the input, then takes the binary representation with the first symbol removed ([3:] because the prefix 0b is two chars chars). Since any positive number starts with 1 in binary, this uniquely gives a binary representation.

A byte is saved by instead using the bit complement ~n to get the negation -(n+1), and removing the negative sign by chopping off one more symbol.

Answer 3

Pyth, 5 bytes

t.BhQ

Simply a translation of xnor's answer into Pyth.

Q is eval()'d input(), h increments it, .B converts it to a binary string, and t takes the "tail" (which is everything except the first character).

Answer 4

Haskell, 41 38 30 29 bytes

l="":[b:x|x<-l,b<-"01"]
(l!!)

Usage example: (l!!) 4 -> "10".

Starting with the empty list as the first element, walk lazily through the list and append the current element with 0 and with 1 in front of it.

Edit: @xnor saved 3 11 bytes. Thanks!

Answer 5

JavaScript (ES6), 29 bytes

x=>(~x).toString(2).slice(2)

Same idea as xnor.

f=x=>(~x).toString(2).slice(2);
[...Array(100)].map((v,x)=>A.textContent+=x + ': ' + f(x) + '\n')

<pre id=A></pre>

Answer 6

Jolf, 4 bytes

Try it here!

wBhj
  hj  input + 1
 B    converted to binary
w     with first removed.

Very simple strategy, also happens to be the shortest.

Answer 7

Haskell, 35 bytes

h 1=[]
h n=mod n 2:h(div n 2)
h.(+1)

Haskell doesn't have a binary built-in, so the (reversed) conversion is done manually. To remove the initial 1, the base case has 1 transform to the empty list.

Edit: Saved a byte by conjugating by the +1 instead.

h 0=[]
h m=1-mod m 2:h(div(m+1)2-1)

Answer 8

C, 40 bytes

f(n){if(++n/2)putchar(n%2+48),f(n/2-1);}

Converts the input to bijective base 2 (with symbols 0 and 1), like the other answers.

ideone it!