Convert integer to binary string with variable size

Question

Suppose I want to get every combination of 1's and 0's with length n. For example, if n = 3, then I want

000
001
010
011
100
101
110
111

My initial thought was to use something like:

#include <iostream>
#include <bitset>
#include <cmath>

int main() {
  int n = 3;
  for (int i = 0; i < pow(2, n); i++)
    std::cout << std::bitset<n>(i).to_string() << '\n';
}

but this does not work since std::bitset takes a const, whereas I need n to be variable (for example if I am in a loop).

How can I do this?

Answer 1

A straightforward way: Extract each bits using bitwise shift operation.

#include <iostream>

int main() {
    int n = 3;
    for (int i = 0; i < (1 << n); i++) {
        for (int j = n - 1; j >= 0; j--) {
            std::cout << ((i >> j) & 1);
        }
        std::cout << '\n';
    }
    return 0;
}

Note that this method will work only if n is small enough not to cause an integer overflow (1 << n doesn't exceed INT_MAX).
To generate larger sequence, you can use recursion:

#include <iostream>
#include <string>

void printBits(int leftBits, const std::string& currentBits) {
    if (leftBits <= 0) {
        std::cout << currentBits << '\n';
    } else {
        printBits(leftBits - 1, currentBits + "0");
        printBits(leftBits - 1, currentBits + "1");
    }
}

int main() {
    int n = 3;
    printBits(n, "");
    return 0;
}

Answer 2

C++20 format to the rescue:

int main()
{
    int p;
    while (std::cin >> p) {
        std::cout << std::format("--------\n2^{}\n", p);
        auto n = 1 << p;
        
        for (int i = 0; i < n; i++) {
            std::cout << std::format("{:0{}b}\n", i, p);
        }
    }
}

https://godbolt.org/z/5so59GGMq

Sadly for now only MSVC supports it.

Answer 3

It is also possible to declare and use an Integer class with a parametrable number of bits (static variable) like below ? Use is simple :

#include "Integer.hpp"

int main (int argc, char* argn []) {
  Integer::set_nbit (3);
  Integer i (0);
  do {
    i.write (std::cout); std::cout << std::endl;
    ++i;
  }
  while (!i.is_max ());
  if (i.is_max ()) {i.write (std::cout); std::cout << std::endl;}
  return 0;
}

The results are those expected :

000
001
010
011
100
101
110
111

And the Integer class is not that complex now (to be completed with other operation than pre-incrementation, operator =, ==...) : using Little Endian Convention internally, and Big Endian convention for outputs (Integer class can be easily extended to an undetermined number of bits Integer)

#include <iostream>
#include <vector>
#include <algorithm>

class Integer {
  static int nbit_;
  static int nmax_;
public :
  static void set_nbit (int s) {nbit_ = s; auto q (1); auto nb (0); while ((nb +1) < nbit_) {q <<= 1;++nb; nmax_ += q;} }

  Integer (int i = 0) : val_ (nbit_, 0) {
    int q (1);
    int siz (0);
    while (q <= i) { ++siz; q<<=1;}
    if (!siz) return;
    if (q > 1) q >> 1;
    auto rit (val_.rbegin ());
    auto rest (i);
    while (rest > 1) {
      *rit++ = rest%q ?true:false;
      rest -= q;
      q >>= 1;
    }
    if (q) *rit++ = true;
  }
  Integer (const Integer& i) : val_ (i.val_) {
  }
  void operator ++ () {
    auto carry ((int) 1);
    std::find_if (val_.begin (), val_.end (), [&carry] (std::_Bit_iterator::reference b) {
      if (!carry) return true;
      if (b) {
        b = false;
        //carry continues to be 1
      }
      else {
        b = true; carry = 0;
      } 
      return false;
    });
    if (carry) exit (1);
  }
  operator std::string () const {
    std::string str (val_.size (), '0');
    auto i (str.begin ());
    auto b0 ('0'), b1 ('1');
    std::for_each (val_.rbegin (), val_.rend (), [&i, &b0, &b1] (const auto& b) {*i++ = b ?b1:b0;});
    return str;
  }
  void write (std::ostream& os) const{
    os << operator std::string ();
  }
  bool is_max () const {
    auto i (val_.begin ());
    i = std::find_if (val_.begin (), val_.end (), [] (const auto& b) {return !b;});
    if (i == val_.end ()) return true;
    return false;
  }

  //operators == (string), < (int), < (Integer), =, == TO be written
  private :
  std::vector<bool> val_;
};

int Integer::nmax_ (0);

int Integer::nbit_ (0);