Wyświetlenie liczb z zakresu zawierających binarną 1 n-razy

Cześć
chodzi mi o to że na wejściu mam podany
a) zakres (od 1 do n)
b) ilość jedynek w binarnej reprezentacji liczny

np
a) 15 <1. 15>
b) 3

11 to binarnie 1111
minimalna liczba z trzema jedynkami to 2^3-1 czyli 7 czyli binarnie 0111

a kolejno liczby z 3 jedynkami to
0111 = 7
1011 = 11
1101 = 13
1110 = 14

no i teraz jak to sprytnie zrobić

ja zrobiłem to tak

 
for(int i = 1; i <=n; i++)
{
        std::bitset<sizeof(size_t) * CHAR_BIT> b(i);
        if(b.count() == ilosc)
          cout<<i;
}

ale czy da się to zrobić lepiej, szybciej, wydajniej, sprytniej

czyli że zaczynam od 2^n-1 a potem coś dodaję coś przesuwam i mam kolejne liczby

000
001
010
011
100
101
110
111

I teraz pomyśl... Patrząc pionowo (n - ilość kolumn) 2^n wierszy. Pierwsza kolumna (od góry) 2^n-1 0 i tyleż samo jedynek. Druga kolumna 2^n-2 0 i tyleż samo jedynek powtarzane (2^n)/(2^n-1) razy.

Rozpisz to sobie i pomyśl. Da się jeszcze bardziej uprościć. Zrobić równanie mówiące co wstawić w danym miejscu ;). Wtedy robisz sobie po prostu cout<<rownanie;

Jak masz 3 jedynki na 4 bity to lepiej to natychmiast przekształcić na 1 zero na 4 bity, więc od razu wiadomo jak to zrobić.
Trochę gorzej jak masz 3 jedynki na 8 bitów oznacza to że masz 5 zer na te 8 bitów.
Miejsca na zera masz 4 - po każdej stronie jedynek.
Więc trzeba podzielić 5 zer na 4 kupki, np tak:

#include <stdio.h>

int main()
  {
   int k1,k2,k3;
   for(k1=0;k1<=5;++k1)
      for(k2=0;k2<=5-k1;++k2)
         for(k3=0;k3<=5-k1-k2;++k3)
            if(5>k1+k2+k3) printf("%0*d%0*d%0*d%0*d\n",k1+1,1,k2+1,1,k3+1,1,5-k1-k2-k3,0);
            else printf("%0*d%0*d%0*d\n",k1+1,1,k2+1,1,k3+1,1);
   return 0;
  }

@ŁF specjalnie dla ciebie załamałem jednowierszowy program ;P

Ola Nordmann napisał(a):

000
001
010
011
100
101
110
111

> 
> I teraz pomyśl... Patrząc pionowo (n - ilość kolumn) `2^n` wierszy. Pierwsza kolumna (od góry) `2^n-1` 0 i tyleż samo jedynek. Druga kolumna `2^n-2` 0 i tyleż samo jedynek powtarzane `(2^n)/(2^n-1)` razy.
> 
> Rozpisz to sobie i pomyśl. Da się jeszcze bardziej uprościć. Zrobić równanie mówiące co wstawić w danym miejscu ;). Wtedy robisz sobie po prostu `cout<<rownanie;`



Nie ogarniam
***Patrząc pionowo (n - ilość kolumn) `2^n` ***

czyli 8 - no i jest ok 8 wierszy

***Pierwsza kolumna (od góry) `2^n-1` 0 i tyleż samo jedynek.***

(2^n(ilość kolumn = 3) - 1) to wychodzi 7 - no nie wyjdzie tyle samo 0 i 1 w kolumnie - nie ogarniam

***Druga kolumna `2^n-2`  0 i tyleż samo jedynek ***

(2^n(ilość kolumn = 3) - 2) to wychodzi 6 - no nie wyjdzie tyle samo 0 i 1 w kolumnie - nie ogarniam znów

możesz jaśniej - może coś źle rozumiem

z góry dziękuję

#include <iostream>
#include <vector>
using namespace std;

void fun(unsigned K,unsigned N)
  {
   unsigned P=N-K,sum=0;
   vector<unsigned> T(P+1);
   while(true)
     {
      for(unsigned p=0;p<P;++p,cout<<0) for(unsigned n=0;n<T[p];++n) cout<<1;
      for(unsigned n=sum;n<K;++n) cout<<1;
      cout<<endl;
      unsigned p=P-1;
      while((p<P)&&(sum>=K))
        {
         sum-=T[p];
         T[p--]=0;
        }
      if(p>=P) break;
      ++sum;
      ++T[p];
     }
  }

int main()
  {
   fun(5,8);
   return 0;
  }

@up: Mam dość negatywne nastawienie do nieczytelnych kodów. Proponuje najprościej jak się da:

#include <iostream>

#define NDEBUG

using namespace std;

typedef unsigned int uint;

int GetBit(uint n, int bitIndex);
void PrintBinary(uint n);
void PrintBinaryLn(uint n);
void PrintNumber(uint n);
class BitStack;
class NumberFinder;

int GetBit(uint n, int bitIndex)
{
  return (n >> bitIndex) & 1;
}

void PrintBinary(uint n)
{
  bool foundOne = false;
  for (int i = 31; i >= 0; i--)
  {
    int bit = GetBit(n, i);
    foundOne |= bit;
    if (foundOne)
    {
      cout << bit;
    }
  }
  if (!foundOne)
  {
    cout << 0;
  }
}

void PrintBinaryLn(uint n)
{
  PrintBinary(n);
  cout << endl;
}

void PrintNumber(uint n)
{
  PrintBinary(n);
  cout << " = " << n << endl;
}

class BitStack
{
public:
  BitStack() : stack(0), currentBit(0) {}
  void Push(int bit)
  {
    bit &= 1;
    if (currentBit == 32)
    {
      cerr << "Error: Stack overflow" << endl;
      return;
    }
    stack |= (uint)bit << currentBit;
    currentBit++;
  }
  void Pop()
  {
    if (currentBit == 0)
    {
      cerr << "Error: Stack underflow" << endl;
      return;
    }
    currentBit--;
    stack &= ~((uint)1 << currentBit);
  }
  int Peek() const
  {
    return GetBit(stack, currentBit - 1);
  }
  uint ToUInt() const { return stack; }
  void Clear()
  {
    stack = 0;
    currentBit = 0;
  }
  bool HasSpace() const { return currentBit != 32; }
private:
  uint stack;
  int currentBit;
};

class NumberFinder
{
public:
  NumberFinder(int aNumberOfOnes, uint aMaxValue)
    : stack(), numberOfOnes(aNumberOfOnes), maxValue(aMaxValue) {}

  void PrintAll()
  {
    PrintCombinations(numberOfOnes);
  }

private:
  BitStack stack;
  const int numberOfOnes;
  const uint maxValue;

  void PrintCombinations(int onesLeft)
  {
    uint value = stack.ToUInt();
    #ifndef NDEBUG
      cout << "::: onesLeft : " << onesLeft << " : ";
      PrintNumber(value);
    #endif
    bool smallerThanMax = value <= maxValue;
    if (onesLeft == 0)
    {
      if (smallerThanMax)
      {
        PrintNumber(value);
      }
      return;
    }

    if (!stack.HasSpace()) return;

    stack.Push(1);

    if (stack.ToUInt() > maxValue)
    {
      stack.Pop();
      return;
    }
    PrintCombinations(onesLeft - 1);

    stack.Pop();
    stack.Push(0);
    PrintCombinations(onesLeft);
    stack.Pop();
  }
};

int main()
{
  int numberOfOnes, maxValue;
  cin >> numberOfOnes >> maxValue;
  NumberFinder(numberOfOnes, maxValue).PrintAll();
  return 0;
}