wu :: forums
wu :: forums - integer encoding with increasing number of bits

Welcome, Guest. Please Login or Register.
May 19th, 2024, 10:41am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: william wu, Grimbal, Eigenray, ThudnBlunder, Icarus, SMQ, towr)
   integer encoding with increasing number of bits
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: integer encoding with increasing number of bits  (Read 621 times)
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
integer encoding with increasing number of bits  
« on: Sep 16th, 2018, 11:16pm »
Quote Quote Modify 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: male
Posts: 7527
Re: integer encoding with increasing number of bit  
« Reply #1 on: Sep 17th, 2018, 2:46am »
Quote Quote Modify Modify

So far I have a method that works for the first 3 and the last 3 values. Smiley
 
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: male
Posts: 2084
Re: integer encoding with increasing number of bit  
« Reply #2 on: Sep 17th, 2018, 6:18am »
Quote Quote Modify 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 Quote Modify 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. Smiley
Cheesy
« Last Edit: Sep 26th, 2018, 7:13pm by dudiobugtron » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: integer encoding with increasing number of bit  
« Reply #4 on: Oct 6th, 2018, 8:09am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board