Generate the next integer with the same number of bits.

The statement of the algorithm is as follows :
Given an integer N, what is the next higher number with the same number of bits. Write an algorithm to produce the same, return error if the given number is already the highest number with the same number of bits.

The code given below works on a vector of boolean. However it would be straight-forward to convert it to bit manipulation routine. There is also an alternate brute-force implementation, and the main method tests that the two produce the same output.

#include <cassert>
#include <cstdio>
#include <cstdint>
#include <string>
#include <vector>
using namespace std;

// Locate the first zero followed by some 1. If there is no such zero,
// return false, because the permutation cannot be incremented.
// Once found set it 1, shifting all the remaining 1's encountered so
// far to the right end.
bool GenerateNextInterleaving(vector<bool>& array) {
  int onbits = 0;
  int i = 0;
  for (; i < array.size(); ++i) {
    if (array[i]) {
      ++onbits;
      array[i] = false;
    } else if (onbits > 0) {
      // It is the first zero followed by some 1.
      array[i] = true;
      break;
    }
  }
  if (i >= array.size()) {
    return false;
  }
  for (i = 0; i < (onbits-1); ++i) {
    array[i] = true;
  }
  return true;
}

// Iterate through all possible combinations, with given total bits,
// and number of on bits.
void GenerateAllInterleavings(int numbits, int onbits,
                        vector<string>* outputs) {
  vector<bool> array(numbits, false);
  for (int i = 0; i < numbits && i < onbits; ++i) {
    array[i] = true;
  }
  char buffer[numbits + 1];
  buffer[numbits] = '\0';
  do {
    for (int i = 0; i < numbits; ++i) {
      buffer[i] = array[numbits-1-i] ? '1' : '0';
    }
    printf("algorithm's solution: %s\n", buffer);
    outputs->push_back(buffer);
  } while (GenerateNextInterleaving(array));
}

// A brute force version to test the above algorithm.
void BruteForceSolution(int size, int onbits, vector<string>* outputs) {
  uint64_t limit = (1UL << size);
  char buffer[size + 1];
  buffer[size] = '\0';
  for (uint64_t n = 0; n < limit; ++n) {
    // Count number of bits in n.
    int count = 0;
    for (uint64_t copy = n; copy; copy >>= 1) {
      if (copy & 0x1) ++count;
    }
    if (count == onbits) {
      uint64_t copy = n;
      for (int i = 0; i < size; ++i) {
        buffer[size - 1 - i] = (copy & 0x1) ? '1' : '0';
        copy >>= 1; 
      }
      printf("brute-force solution %s\n", buffer);
      outputs->push_back(buffer);
    }
  }
}

int main() {

  int numbits = 8, onbits = 3;

  // Ensure that the algorithm produces the same output as the
  // brute-force solution.
  vector<string> bruteforce_result;
  BruteForceSolution(numbits, onbits, &bruteforce_result);

  vector<string> algo_result;
  GenerateAllInterleavings(numbits, onbits, &algo_result);

  assert(algo_result == bruteforce_result);
  return 0;
}