Добавить на ответ @ sehe, включенный ниже (первоначально от Дарио Снейдерманиса, также на http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation.)
#include <utility>
#include <iostream>
#include <bitset>
using I = uint8_t;
auto dump(I v) { return std::bitset<sizeof(I) * __CHAR_BIT__>(v); }
I bit_twiddle_permute(I v) {
I t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
I w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
return w;
}
int main() {
I p = 0b001001;
std::cout << dump(p) << "\n";
for (I n = bit_twiddle_permute(p); n>p; p = n, n = bit_twiddle_permute(p))
{
std::cout << dump(n) << "\n";
}
}
Существуют пограничные проблемы с bit_twiddle_permute (I v). Всякий раз, когда v - последняя перестановка, t - все 1 (например, 2 ^ 8 - 1), (~t & -~t) = 0, а w - первая перестановка битов с одним меньшим 1 с, чем v, за исключением случаев, когда v = 000000000, в этом случае w = 01111111 , В частности, если вы установите p в 0; цикл в main произведет все перестановки с семью единицами, а следующая небольшая модификация цикла for будет циклически перебирать все перестановки с 0, 7, 6, ..., 1 установленным битом -
for (I n = bit_twiddle_permute(p); n>p; n = bit_twiddle_permute(n))
Если это намерение, возможно, оно заслуживает комментария. Если нет, то это тривиально исправить, например,
if (t == (I)(-1)) { return v >> __builtin_ctz(v); }
Итак, с дополнительным небольшим упрощением
I bit_twiddle_permute2(I v) {
I t = (v | (v - 1)) + 1;
if (t == 0) { return v >> __builtin_ctz(v); }
I w = t | ((~t & v) >> (__builtin_ctz(v) + 1));
return w;
}
int main() {
I p = 0b1;
cout << dump(p) << "\n";
for (I n = bit_twiddle_permute2(p); n>p; n = bit_twiddle_permute2(n)) {
cout << dump(n) << "\n";
}
}
Следующей адаптации идеи Дарио Снейдерманиса может быть немного легче следовать
I bit_twiddle_permute3(I v) {
int n = __builtin_ctz(v);
I s = v >> n;
I t = s + 1;
I w = (t << n) | ((~t & s) >> 1);
return w;
}
или с аналогичным решением проблемы, о которой я говорил в начале этого поста
I bit_twiddle_permute3(I v) {
int n = __builtin_ctz(v);
I s = v >> n;
I t = s + 1;
if (v == 0 || t << n == 0) { return s; }
I w = (t << n) | ((~t & s) >> 1);
return w;
}