Author |
Topic: integer encoding with increasing number of bits (Read 638 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print