Как перебрать все цепочки битов с одним 0, двумя 0, вплоть до n 0?

Question

У меня есть функция для увеличения строки битов следующим образом:

void increment(boost::dynamic_bitset<> &bitset)
{   
    for (int loop = 0; loop < bitset.size(); ++loop)
    {
        if ((bitset[loop] ^= 0x1) == 0x1)
        {
            break;
        }
    }
}

Я хочу, чтобы функция вызывалась так же, как и приращение, но изменяла бы цепочку битов по-разному. Каждый раз, когда он вызывается, я хочу получить следующую цепочку битов с тем же числом нулей, что и предыдущая.

Например, если цепочка битов имеет длину 10, первые 10 вызовов этой функции дадут цепочку битов с одним 0. Затем вызовы с 11 по 20 вернут битовые строки с 2 0. Я хочу, чтобы это продолжалось до тех пор, пока цепочка битов не будет равна нулю.

Как я мог настроить такую ​​функцию? Спасибо!

Answer 1

Вы можете найти ответ в Вопросы вычислений , глава 1.24.3 «Порядок смен». Вам придется изменить целые числа на битовые наборы и перевернуть значения. Возможно, эта реализация не оптимальна при использовании с битовыми наборами.