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 Help Search Members Login 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 Notify of replies Send Topic 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:
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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »