Author |
Topic: integer encoding with increasing number of bits (Read 628 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 16th, 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 16th, 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 17th, 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 17th, 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 n-bit 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 26th, 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 17th, 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 26th, 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 6th, 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 = len-1 ; 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 6th, 2018, 8:38am by Grimbal » |
IP Logged |
|
|
|
|