Sunday, 1 April 2012

Generate this Sequence.

Your objective is to print all unsigned integers less than N, where N is the largest unsigned integer that can be represented by the number of bits specified by the user. The order in which the numbers should appear is decided by the following rules.
  1. 0 appear first, since its binary representation have zero ones.
  2. 1,2,4,8,.... appear next in the increasing order. Note that their binary representation have exactly one one. 
  3. 3,5,6,9,.... appear next in the increasing order. Note that their binary representation have exactly two one. 
  4. And so on.
One obvious approach is first store all the possible numbers in an array and then sort them based on the number of ones in their binary representation. But this is not what we need since we may need around 16GB of memory to store the numbers if inputs as small as 32. Another approach is to scan this 2^32 numbers 32 times, which may not be a big deal for our processors but still this in not the efficient way of doing it. we can either use some arithmetic relation between numbers of this sequence to find next number if any number in the sequence is given, or we can use bit-wise operators to develop an algorithm to find the next number for any given number.

No comments:

Post a Comment