Алгоритм перебора всех сочетаний

Возникла потребность в "быстром" алгоритме перебора всевозможных размещений K единиц в N разрядах. Немного погуглил, но так и не нашел алгоритмов без дважды вложенных циклов. А ведь хочется получить функцию для "выработки" следующей комбинации на основе предыдущей. Да и хранить единицы и нули желательно не в строках(побайтно), а в многоразрядных числах(побитно). В этом случае, конечно, возникает вопрос разрядности чисел, как ограничение на параметр N ... тогда используем числа разрядности 64, 128, 256 бит и т.д. Например, можно воспользоваться классом big_int в составе библиотеки Boost. Прикинем на глаз всевозможные варианты размещения 3-ёх единиц в 5-ти разрядах и порядок перебора этих вариантов:

1 1 1 0 0
1 1 0 1 0
1 1 0 0 1
1 0 1 1 0
1 0 1 0 1
1 0 0 1 1
0 1 1 1 0
0 1 1 0 1
0 1 0 1 1
0 0 1 1 1

Итого 10 вариантов (число сочетаний из пяти по три). Визуально алгоритм выглядит как пробегающая слева направо единица. Опишем его формально с использованием рекурсии:

2) Если самый правый символ "1", то отрубаем самый правый символ и отправляем полученную комбинацию (длины N-1 с K-1 единицами) на п.1 алгоритма. В полученном значении находим самую правую единицу и вписываем вырезанную ранее единицу сразу после неё.

Задание необходимых операций на языке C++

При хранении комбинации в многоразрядных переменных нам понадобятся следующие операции:

а) Операция определения значения младшего разряда

(a & 1)

int shiftLast1(int a) {
   return ((a-1) ^ ((a^(a-1)) >> 2));
}

int add1AfterLast1(int a) {
   return ( a | ( ((a^(a-1)) + 1) >> 2 ) );
}

int firstSoch(int n, int k) {
   return ( ((1 << k) - 1) << (n - k) );
}

int nextSoch(int a)
{
   // в случае последней комбинации вернём нуль
   if ((a & (a+1)) == 0)
      return 0;
 
   if (a & 1)
      return add1AfterLast1( nextSoch(a >> 1) << 1 );
   else
      return shiftLast1(a);
}

Дополнение

1) Вместо функций (б) и (в) можно использовать макросы.
(Аккуратнее с вложенным вызовом макросов! - напоролся однако)

2) Аккуратнее с типами констант:
(1 << 48) не равно (0x01000000000000)
(__int64(1) << 48) равно (0x01000000000000)

Очень рекомендую этот материал: Bit Twiddling Hacks

Если алгоритм вам пригодился или вы имеете интересные замечания/комментарии, как говорится, feel free to comment . . .