Author 
Topic: integer encoding with increasing number of bits (Read 631 times) 

towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


integer encoding with increasing number of bits
« on: Sep 16^{th}, 2018, 11:16pm » 
Quote Modify

I'm pondering whether there's a "simple" integer encoding where the number of bits set to 1 increase. So given an maximum integer size, you first count with all integers with only 0s, then with 1 bti set to 1, then with 2 bits set to 1 etc. But ideally there would be a simple way to encode and decode it. The simplest way to count (with maxint=15) is probably like 0000 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111 But is there a simple way to map from value to representation and back? Or is there a better way?

« Last Edit: Sep 16^{th}, 2018, 11:18pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: integer encoding with increasing number of bit
« Reply #1 on: Sep 17^{th}, 2018, 2:46am » 
Quote Modify

So far I have a method that works for the first 3 and the last 3 values. For the rest I have to think a bit more. I think I have a way that is faster than just generating the sequence.


IP Logged 



SMQ
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 2084


Re: integer encoding with increasing number of bit
« Reply #2 on: Sep 17^{th}, 2018, 6:18am » 
Quote Modify

A few properties of note:  The second half of the sequence is the first half of the sequence inverted and reversed (which is true of many useful binary sequences.)  The number of nbit integers with k 1's is just the binomial coefficient (n/k)  There is no closed form equation for partial sums of binomial coefficients. That makes it unlikely that there's a simple way to encode/decode the sequence. SMQ


IP Logged 
SMQ



dudiobugtron
Uberpuzzler
Posts: 735


Re: integer encoding with increasing number of bit
« Reply #3 on: Sep 26^{th}, 2018, 7:10pm » 
Quote Modify

I figured that ordering binary numbers by the number of bits set to 1 was equivalent to ordering elements of a powerset by size, so did a bit of research and I found a blog page that talks about enumerating subsets in size order (the article mentioned in the linked post calls it "Banker's order"), along with links to algorithms, papers and discussions about it. I don't know how useful this would be to you, so apologies in advance if you end up reading it and getting no useful information! Also, I did not generate any of the content myself, so it's certainly not a viable answer if this post was intended as a riddle (rather than general information gathering). on Sep 17^{th}, 2018, 2:46am, Grimbal wrote:So far I have a method that works for the first 3 and the last 3 values. 


« Last Edit: Sep 26^{th}, 2018, 7:13pm by dudiobugtron » 
IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: integer encoding with increasing number of bit
« Reply #4 on: Oct 6^{th}, 2018, 8:09am » 
Quote Modify

Here are the conversion procedures to/from ABC encoding (Ascending Bit Count) choose(n,k) is the binomial coefficient. public static int convertToABC(int len, int value){ int code = 0; int k = 0, c; while( (c = choose(len,k)) <= value && k < len){ value = c; k++; } for( int n = len1 ; n >= 0 ; n ){ code = code*2; if( value >= (c = choose(n,k)) ){ value = c; k; code++; } } return code; } public static int convertFromABC(int len, int code){ int value = 0; int k = 0; for( int n=0 ; n < len ; ++n ){ if( (code&1) == 1 ){ value += choose(n, ++k); } code /= 2; } while( k>0 ){ value += choose(len, k); } return value; }

« Last Edit: Oct 6^{th}, 2018, 8:38am by Grimbal » 
IP Logged 



