Given a positive integer n, sort numbers from 1 to n with increasing number of bits set. If two numbers have same number of bits set, the lower number will come first. (From Codebunk FB Page)

Sort by 1's.py

"""Using the implementation from Wikipedia: https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation """

def hamming_weight(n):
  t1 = n - ((n>>1) & 0x55555555)
  t2 = (t1 & 0x33333333) + ((t1 >> 2) & 0x33333333)
  return ((((t2 + (t2 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24,n)

def hamming_sort(n):
  return [x[1] for x in sorted(map(hamming_weight,xrange(1,n+1)))]

print hamming_sort(8)

"""Depreciated! Saw a better way of implementing Hamming Weight (in constant time)"""
def sort_ones(n):
  return [x[1] for x in sorted([(bin(y).count('1'),y) for y in xrange(1,n+1)])]

"""
Given a +ve integer n, sort numbers from 1 to n with increasing number of bits set. If two numbers have same number of bits set, the lower number will come first.

O(n) algo!! Awesome!

from hackers delight. Original URL : http://codebunk.com/bunk#-Ix4MPTxEkWFxofMy51L
"""

def next_num(n):
    if n == 0: return 0
    lowbit = n & -n
    ripple = n + lowbit
    ones = n ^ ripple
    ones = (ones >> 2)/lowbit
    return ripple|ones

def foo_generator(n):
    bits_set = 1
    while True:
        x = (1<<bits_set) - 1
        if x > n: break
        while x < n:
            yield x
            x = next_num(x)
        bits_set += 1


for i in foo_generator(100):
    print i,bin(i)[2:]