[Question]
  [
... Ah sorry, no popcorn here, just POPCNT.
Write the shortest **program** or **function** which takes in a number `n` and **output** all integers from 0 to 2n - 1, in ascending order of *number of 1 bits in the binary representation of the numbers* (popcount). No duplicates allowed.
The order of numbers with the same popcount is implementation-defined.
For example, for `n = 3`, all these output are valid:
```
0, 1, 2, 4, 3, 5, 6, 7
[0, 4, 1, 2, 5, 3, 6, 7]
0 4 2 1 6 5 3 7 
```
The input and output format are implementation-defined to allow the use of language features to further golf the code. There are a few restrictions on the output:
* The numbers must be output in decimal format.
* The output must contain a reasonable separator between the numbers (trailing separator allowed, but not leading).
Line feed (`\n`), tab (`\t`), space, `,`, `.`, `;`, `|`, `-`, `_`, `/` are quite reasonable separator. I don't mind additional spaces for pretty printing, but don't use letter or digits as separators.
* The numbers and separators can be surrounded by `[ ]`, `{ }` or any array or list notation.
* Don't print anything else not stated above.
### Bonus
Multiply your score by **0.5** if your solution can generate the number on the fly. The spirit of this bonus is that if you were to directly convert your printing solution to a generator, the generator only uses at most O(n) memory where n is the number of bits as defined above. (You don't have to actually convert your solution to generator). Note that while I impose n <= 28, the memory needed to store all numbers still grows exponentially, and a naive sorting solution would hog up at least 4 GB of memory at n = 28.
Please add some simple explanation of how your solution works before claiming this bonus.
  
[Answer]
# Pyth, 9 bytes
```
osjN2U^2Q
```
`o`rder by the `s`um of the base 2 representation (`jN2`) over the range (`U`) of `2 ^ Q`.
(`Q` = `eval(input())`).
[Try it here.](http://pyth.herokuapp.com/)
[Answer]
# [Python 2](https://docs.python.org/2/), 72 bytes \* 0.5 = 36
```
N=1<<input()
for k in range(N*N):
 if bin(k%N).count('1')==k/N:print k%N
```
[Try it online!](https://tio.run/##K6gsycjPM/r/38/W0MYmM6@gtERDkystv0ghWyEzT6EoMS89VcNPy0/TikshM00hKTNPI1vVT1MvOb80r0RD3VBd09Y2W9/PqqAoM69EASj1/78pAA "Python 2 – Try It Online")
A new method for this now-ancient challenge. The less-golfed below below might be easier to understand:
**87 bytes**
```
n=input()
for i in range(n+1):
 for x in range(2**n):
  if bin(x).count('1')==i:print x
```
[Try it online!](https://tio.run/##Rci9CoAgFAbQ3ae4mz9BoG2CD1ORdZdPEQV7esOpM5781ifBjYHAyK0qLWIqxMSgsuO@FBarvaC5/V9nDGYTRzoYquv1TA1VSSt1COxzYVTqY2wf "Python 2 – Try It Online")
We loop over target popcounts `i` in increasing order, and for each one iterate over the `n`-bit numbers and prints those with exactly `i` set bits.
Even though this loops over the `n`-bit numbers many times, it still satisfies the efficiency bonus criteria of only using `O(n)` memory if the loop were converted to a generator. If fact, the golfed code allocates `n` bits to the target popcount as well as `n` bits to the number being checked. They are stored as a `2*n`-bit number, which allows counting up this single number and extracting the first and last `n` bits as needed.
---
# [Python 2](https://docs.python.org/2/), 59 bytes
```
lambda n:sorted(range(1<<n),key=lambda x:bin(x).count('1'))
```
[Try it online!](https://tio.run/##LclBCoAgEADAr3hzhQgKuoj@pIuWllSr2Ar2euvQdSY9tEccm9dzO81lV8NQ3jGTWyEb3BwMSqHoDvfo/6u0AaGKfokFCfjAhWgpByTmIWAqBB9MLw "Python 2 – Try It Online")
A short sorting-based approach that does not qualify for the bonus.
---
# [Python 2](https://docs.python.org/2/), 75 bytes \* 0.5 = 37.5
```
N=2**input()-1
v=N-~N
while v:t=1+(v|~-v);v=N&t|~-(t&-t)/(v&-v)/2;print v^N
```
[Try it online!](https://tio.run/##K6gsycjPM/r/38/WSEsrM6@gtERDU9eQq8zWT7fOj6s8IzMnVaHMqsTWUFujrKZOt0zTGiilVgJkapSo6ZZo6muUqQFF9Y2sC4oy80oUyuL8/v83BQA "Python 2 – Try It Online")
Repeatedly generates the next highest `v` with the same POPCOUNT by [this bit-twiddling algorithm](https://stackoverflow.com/q/8281951).
Actually, it turned out easier to generate them in decreasing pop-count, then print the complement to make it increasing. That way, then `v` overflows `2**n`, we simply remove all but `n` bits with `&N` where `N=2**n-1`, and that gives the smallest number one popcount lower. That way, we can just do one loop. There's probably a better solution that directly finds the next *lower* number with the same POPCOUNT.
Due to a fencepost issue, we need to start with `v=2**(n+1)-1` so that the operation produces `v=N-1` on the first loop.
Output for `4`:
```
0
8
4
2
1
12
10
9
6
5
3
14
13
11
7
15
```
[Answer]
## J, 19 characters, no bonus.
```
[:(/:+/"1@#:)@i.2^]
```
* `2 ^ y` – two to the power of `y`.
* `i. 2 ^ y` – the integers from `0` to `(2 ^ y) - 1`.
* `#: i. 2 ^ y` – each of these integers represented in base two.
* `+/"1 #: i. 2 ^ y` – the sums of each representation
* `(i. 2 ^ y) /: +/"1 #: i. 2 ^ y` – the vector `i. 2 ^ y` sorted by the order of the items of the previous vector, our answer.
[Answer]
## Python, 63 chars
```
F=lambda n:`sorted(range(1<<n),key=lambda x:bin(x).count('1'))`
>>> F(3)
'[0, 1, 2, 4, 3, 5, 6, 7]'
```
[Answer]
## Mathematica, 50 46
```
SortBy[Range[0,2^#-1],Tr@IntegerDigits[#,2]&]&
```
.
```
SortBy[Range[0,2^#-1],Tr@IntegerDigits[#,2]&]&
{0, 1, 2, 4, 8, 16, 3, 5, 6, 9, 10, 12, 17, 18, 20, 
24, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 15, 
23, 27, 29, 30, 31}
```
[Answer]
**C 179 \* 0.5 = 89.5**
```
main(){int n,i=0,m,o;scanf("%d",&n);m=~((~0)<<n);for(;n--;++i){for(o=0;o<m;++o){int bc=0,cb=28;for(;cb--;)bc+=o&(1<<cb)?1:0;if(bc==i)printf("%d ",o);}}printf("%d\n",m);return 0;}
```
**EDIT: 157 \* 0.5 = 78.5**
```
main(){int n,i=0,m,o;scanf("%d",&n);m=~((~0)<<n);for(++n;n--;++i){for(o=0;o<=m;++o){int bc=0,cb=28;for(;cb--;)bc+=o&(1<<cb)?1:0;if(bc==i)printf("%d ",o);}}}
```
**EDIT: 132 \* 0.5 = 66**
```
main(){int n,i=0,m,o;scanf("%d",&n);m=~((~0)<<n);for(++n;n--;++i){for(o=0;o<=m;++o){if(__builtin_popcount(o)==i)printf("%d ",o);}}}
```
or a bit nicer formatted:
```
main()
{
    int n, i = 0, m, o;
    scanf("%d", &n);
    m = ~((~0) << n);
    for(++n; n--; ++i)
    {
        for(o = 0; o <= m; ++o)
        {
            if (__builtin_popcount(o) == i)
                printf("%d ", o);
        }
    }
}
```
What it does?
```
m = ~((~0) << n);
```
calculates the last number to show (pow(2, n) - 1)
```
    for(++n; n--; ++i)
    {
        for(o = 0; o <= m; ++o)
        {
```
the outer loop iterates over the bit count (so 0 to n-1)
while the inner loop just counts from 0 to m
```
            if (__builtin_popcount(o) == i)
                printf("%d ", o);
```
On x86 there is the POPCNT instruction that can be used to count the set bits.
GCC and compatible compilers may support the \_\_builtin\_popcount function that basically compiles to that instruction.
[Answer]
# CJam, 13 bytes
```
2ri#,{2b1b}$p
```
Pretty straight forward implementation.
**How it works**:
```
2ri#,             "Get an array of 0 to 2^n - 1 integers, where n is the input";
     {    }$      "Sort by";
      2b1b        "Convert the number to binary, sum the digits";
            p     "Print the array";
```
[Try it online here](http://cjam.aditsu.net/#code=2ri%23%2C%7B2b1b%7D%24p&input=3)
[Answer]
# [K (ngn/k)](https://bitbucket.org/ngn/k), ~~18~~ ~~9~~ 8 bytes
-9 bytes from @ngn's improvements
-1 byte from using `where` instead of `take`
```
<+/!2+&:
```
[Try it online!](https://tio.run/##y9bNS8/7/z/NykZbX9FIW83qf5qCMVeagsl/AA "K (ngn/k) – Try It Online")
A tacit function, equivalent to `{<+/!2+&x}`.
* `2+&:` generate `x` 2's
* `!...` generate "odometer" of the input (in this case this provides the binary representation of the numbers from 0 to pow(2,x))
* `+/` sum column-wise
* `<` "grade up" the sums (i.e. sort them by the number of 1's in the binary-representation of each value)
[Answer]
# [Husk](https://github.com/barbuz/Husk), 8 bytes
```
ÖoΣḋŀ`^2
```
[Try it online!](https://tio.run/##yygtzv7///C0/HOLH@7oPtqQEGf0//9/YwA "Husk – Try It Online")
```
     `^2  flip ^, partially applied, gets fully applied with implicit input, 2 ^ n
    ŀ     range from [0, n)
Ö         sort by
 o        composed function
  Σ       sum
   ḋ      binary digits
```
[Answer]
# JavaScript (ES6) 41 (82\*0.5)
The simplest way, golfed
```
F=b=>{
  for(l=0;l<=b;l++)
    for(i=1<<b;i;t||console.log(i))
      for(t=l,u=--i;u;--t)
        u&=u-1;
}
```
**Ungolfed**
```
F=b=>
{
  for (l = 0; l <= b; l++)
  {
    for (i = 1 << b; i > 0; )
    {
      --i;
      for (t = 0, u = i; u; ++t) // Counting bits set, Brian Kernighan's way
        u &= u - 1;
      if (t == l) console.log(i);
    }
  }
}
```
**Test** In Firefox/FireBug console
```
F(4)
```
> 
> 0  
> 
> 8  
> 
> 4  
> 
> 2  
> 
> 1  
> 
> 12  
> 
> 10  
> 
> 9  
> 
> 6  
> 
> 5  
> 
> 3  
> 
> 14  
> 
> 13  
> 
> 11  
> 
> 7  
> 
> 15
> 
> 
> 
[Answer]
# Bash + coreutils, 66
One to get you started:
```
jot -w2o%dpc $[2**$1] 0|dc|tr -d 0|nl -ba -v0 -w9|sort -k2|cut -f1
```
[Answer]
# Haskell, (87 \* 0.5) = 43,5
```
f n=[0..n]>>=(\x->x#(n-x))
a#0=[2^a-1]
0#_=[0]
a#b=[1+2*x|x<-(a-1)#b]++[2*x|x<-a#(b-1)]
```
Usage example: `f 4`, which outputs `[0,1,2,4,8,3,5,9,6,10,12,7,11,13,14,15]`
How it works: neither sorting nor repeatedly iterating over [0..2^n-1] and looking for numbers containing i 1s. 
The `#` helper functions takes two parameters `a` and `b` and constructs a list of every number made up of `a` 1s and `b` 0s. The main function `f` calls `#` for every combination of `a` and `b` where `a+b` equals `n`, starting with no 1s and `n` 0s to have the numbers in order. Thanks to Haskell's laziness all those lists don't have to be constructed completely in memory.
[Answer]
## Ruby 47 chars
Much like the Python one from @KeithRandall :
```
f=->n{(0..1<<n).sort_by{|x|x.to_s(2).count ?1}}
```
[Answer]
# Mathematica, 26
```
Tr/@(2^Subsets@Range@#/2)&
```
Example:
```
Tr/@(2^Subsets@Range@#/2)&[4]
```
> 
> {0, 1, 2, 4, 8, 3, 5, 9, 6, 10, 12, 7, 11, 13, 14, 15}
> 
> 
> 
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 7 bytes
```
2*’BS$Þ
```
[Try it online!](https://tio.run/##y0rNyan8/99I61HDTKdglcPz/v//bwwA "Jelly – Try It Online")
## Explanation
```
2*’BS$Þ
2*      2^n
  ’     decremented
     $Þ sort the (implicit) range using the following two functions:
   B    binary
    S   summed
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 7 bytes
```
oL<Σb1¢
```
[Try it online!](https://tio.run/##yy9OTMpM/f8/38fm3OIkw0OL/v83BgA "05AB1E – Try It Online")
```
oL<Σb1¢  # full program
   Σ     # sort...
 L       # [1, 2, 3...
o        # ...2 **...
         # implicit input
 L       # ]...
  <      # with one subtracted from...
         # (implicit) each element...
   Σ     # by...
      ¢  # number of...
     1   # ones...
      ¢  # in...
         # (implicit) current element in list...
    b    # in binary
         # implicit output
```
# Alternative, 7 bytes
```
oL<Σ2вO
```
[Try it online!](https://tio.run/##yy9OTMpM/f8/38fm3GKjC5v8//83BgA "05AB1E – Try It Online")
```
2вO  # full modified section
  O  # sum of...
 в   # list of (base-10) values of digits of...
     # (implicit) current element in list...
 в   # in base...
2    # literal
```
# Another alternative, 7 bytes
```
oL<ΣbSO
```
[Try it online!](https://tio.run/##yy9OTMpM/f8/38fm3OKkYP///40B "05AB1E – Try It Online")
```
bSO  # full modified section
  O  # sum of...
 S   # list of characters of...
     # (implicit) current element in list...
b    # in binary
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal), 6 bytes
```
‹Eʁµb∑
```
[Try it Online!](https://lyxal.pythonanywhere.com?flags=&code=%E2%80%B9E%CA%81%C2%B5b%E2%88%91&inputs=4&header=&footer=)
```
  ʁ    # 0...
‹E     # 2 ** (n-1)
   µ   # Sorted by
    b  # binary
     ∑ # Summed
```
[Answer]
# Java 8, 205
```
public class S{public static void main(String[] n){java.util.stream.IntStream.range(0,1<<Integer.parseInt(n[0])).boxed().sorted((a,b)->Integer.bitCount(a)-Integer.bitCount(b)).forEach(System.out::print);}}
```
[Answer]
C++11, 117 characters:
```
using namespace std;int main(){ set<pair<int,int> > s;int b;cin>>b;int i=0;while(++i<pow(2,b))s.insert({bitset<32>(i).count(),i});for (auto it:s) cout <<it.second<<endl;}
```
Ungolfed:
```
using namespace std;
int main()
{
    set<pair<int,int> > s;
    int b;
    cin>>b;
    int i=0;
    while (++i<pow(2,b))  {
        s.insert({bitset<32>(i).count(),i});
    }
    for (auto it:s) {
        cout <<it.second<<endl;
    }
}
```
Explanation:
Create a set of int,int pairs. The first int is bit count, the second one is the number. Pairs compare themselves according their first parameter, so the set is sorted by bit count.
[Answer]
# [MathGolf](https://github.com/maxbergmark/mathgolf/blob/master/math_golf.txt), 6 [bytes](https://github.com/maxbergmark/mathgolf/blob/master/code_page.py)
```
óráÅàç
```
[Try it online.](https://tio.run/##y00syUjPz0n7///w5qLDCw@3Hl5wePn//4ZcRlzGXCZcpgA)
**Explanation:**
```
ó       # Push 2 to the power of the (implicit) input-integer
 r      # Pop and push a list in the range [0,2**input)
  á     # Sort this list by,
   Å    # using the following two characters as inner code-block:
    à   #  Convert it to a binary-string
     ç  #  And only leave the truthy digits, removing the 0s
```
[Answer]
# Perl, 64/2 = 32
```
#!perl -ln
for$i(0..$_){$i-(sprintf"%b",$_)=~y/1//||print for 0..2**$_-1}
```
Simply iterate over the range `[0..2^n-1]` `n + 1` times. In each iteration print only the numbers that have number of 1 bits equal to the iteration variable (`$i`). Bits are counted by counting `1`'s (`y/1//`) in the number converted to binary string with `sprintf`.
Test [me](http://ideone.com/q2wj7G).
# Perl, 63
Sorting approach:
```
#!perl -l
print for sort{eval+(sprintf"%b-%b",$a,$b)=~y/0//dr}0..2**<>-1
```
]