subset — генерирует целые числа с равномерным весом Хэмминга (popcount) Переполнение стека
Я хочу эффективно (с помощью битовых хаков) генерировать все целые числа до заданного числа k, чтобы они имели равномерный вес Хэмминга без явного вычисления их весов Хэмминга. Для меня не важно, происходит ли это в порядке возрастания или убывания.
Бонус (связанная задача) был бы, если бы я мог генерировать все целые числа с равномерным весом Хэмминга, которые являются подмножествами (в смысле кода Грея) из k.
Пример:
input-> k = 14 (бинарный 1110)
вывод всего-> 3 (0011), 5 (0101), 6 (0110), 9 (1001), 10 (1010), 12 (1100)
выходные поднаборы-> 6 (0110), 10 (1010), 12 (1100)
Пример кода с использованием popcount:
for (unsigned int sub=1; sub<k; sub++){
if (__builtin_popcount(sub) % 2 == 0){
cout << sub << endl;
}
}
Пример кода с использованием popcount для подмножеств:
for (unsigned int sub=((k-1)&k); sub!=0; sub=((sub-1)&k)){
if (__builtin_popcount(sub) % 2 == 0){
cout << sub << endl;
}
}
Решение
Мы можем построить дерево с номерами в узлах, у каждого узла есть два дочерних элемента, один с перевернутым битом с номером x, а другой с неперевернутым битом с номером x. Нам нужно исключить всех потомков со значением, превышающим начальное значение. Мы можем хранить popcount в переменной и уменьшать и увеличивать каждый раз, когда мы переворачиваем бит в зависимости от значения перевернутого бита, таким образом, избегая вычисления popcount при каждом изменении переменной.
Я не знаю, если этот метод быстрее или нет. Я думаю, это может быть быстрее, но накладные расходы на рекурсивную функцию могут быть слишком большими.
Это было весело:
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cinttypes>
#include <cassert>
#include <bitset>
#include <cstring>
namespace gen {
bool isEven(unsigned int x) {
return x % 2 == 0;
}
// find last set bit, just like ffs, but backwards
unsigned int fls(unsigned int x)
{
assert(x >= 1);
if (x == 0) {
return 0;
}
#ifdef __GNUC__
const unsigned int clz = __builtin_clz(x);
#else
#error find clz function in C++
#endif
assert(clz >= 1 && (sizeof(x) * CHAR_BIT) >= clz + 1);
return (sizeof(x) * CHAR_BIT) - clz - 1;
}
unsigned int popcount(unsigned int x) {
#ifdef __GNUC__
return __builtin_popcount(x);
#else
return std::bitset<sizeof(x)*CHAR_BIT>(x).count();
#endif
}
/**
* Generates all integers up a given number k with even hamming weight
* @param out - output vector with push_backed results
* @param greycodesubset - set to true, if only interested in grey subset integers only
* @param startk - starting k value
* @param k - the current number value
* @param pos - one plus the position of the bit in number k that we will change in this run
* @param popcount - Hamming weight of number k up to position pos
* @param changes - the number of bits changed in number k since startk. Used only if greycodesubset = true
*/
void loop(std::vector<unsigned int>& out, const bool& greycodesubset,
const unsigned int& startk,
unsigned int k, unsigned int pos, unsigned int popcount,
unsigned int changes)
{
// k > startk may happen for example for 0b10, if we flip last byte, then k = 0b11
if (startk < k) {
return;
}
// end of recusive function
if (pos == 0) {
if (isEven(popcount) && k != 0) {
out.push_back(k);
}
return;
}
// decrement pos
--pos;
const int mask = 1 << pos;
const bool is_pos_bit_set = k & mask;
// call without changes
loop(out, greycodesubset, startk,
k, pos, popcount + (is_pos_bit_set ? +1 : 0), changes);
// when finding grey code subset only we can change maximum 1 byte
if (greycodesubset) {
if (changes >= 1) {
return;
}
++changes;
}
// call with toggled bit number pos
loop(out, greycodesubset, startk,
k ^ mask, pos, popcount + (!is_pos_bit_set ? +1 : 0), changes);
}
std::vector<unsigned int> run(const unsigned int& k, const bool& greycodesubsetonly)
{
assert(k > 0);
std::vector<unsigned int> out;
if (k < 2) return out;
loop(out, greycodesubsetonly, k, k, fls(k) + 1, 0, 0);
return out;
}
} // namespace gen
int main()
{
const unsigned int k = 14;
const int bits_in_k = 4;
std::vector<unsigned int> out = gen::run(k, false);
std::vector<unsigned int> out_subset = gen::run(k, true);
std::cout << "input-> k=" << k << "(" << std::bitset<bits_in_k>(k).to_string() << ") " << std::endl;
std::cout << "output all-> ";
std::for_each(out.begin(), out.end(), [](int v) {
std::cout << v << "(" << std::bitset<bits_in_k>(v).to_string() << ") ";
});
std::cout << std::endl;
std::cout << "output subsets-> ";
std::for_each(out_subset.begin(), out_subset.end(), [](int v) {
std::cout << v << "(" << std::bitset<bits_in_k>(v).to_string() << ") ";
});
std::cout << std::endl;
return 0;
}
input-> k=14(1110)
output all-> 12(1100) 10(1010) 9(1001) 6(0110) 5(0101) 3(0011)
output subsets-> 12(1100) 10(1010) 6(0110)
Другие решения
Других решений пока нет …