Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
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.

share|improve this answer
1  
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.

Try it out online.

share|improve this answer

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

share|improve this answer

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!

share|improve this answer
    
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>

share|improve this answer
    
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.

share|improve this answer

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)
share|improve this answer

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.