# Bijective mapping from integers to a variable number of bits

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.

-
May we return a string of 0's and 1's? – xnor Feb 12 at 21:18
@xnor Yes, a string of 0s and 1s is fine. – orlp Feb 12 at 21:19

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

-
Inverse: `lambda s:int('1'+s,2)-1`. – orlp Feb 12 at 21:45

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

-

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

-

``````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!

-
Interesting idea. The iterated function can be written `[(0:),(1:)]<*>` – xnor Feb 12 at 22:20
@xnor: Oh, you showed me the `<*>` trick before, but I forgot about it. Thanks again! – nimi Feb 12 at 22:26
Ooh, you can define the whole list lazily: `l=[]:[b:x|x<-l,b<-[0,1]];(l!!)`. – xnor Feb 12 at 22:53
@xnor: Great! Thanks a lot! Oh, switching to strings saves one more byte. – nimi Feb 13 at 1:01
I feel like there should be some shorter way to express `[b:x|x<-l,b<-"01"]` with a product or concat-map, but the product expression `(:)<\$>[0,1]<*>l` goes in the wrong order, first prepending 0 to everything, never getting to 1 because the list is infinite. Do you have any ideas? – xnor Feb 13 at 3:03

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

-
This is readily extended to other bases as per codegolf.stackexchange.com/q/78990 – Neil May 1 at 10:33

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

-

``````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)
``````
-

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

-