Объедините биты, затем определите, сколько нулей имеет результат
Я пытаюсь написать функцию, которая принимает три битовых вектора, представляющих используемые цифры в строке, столбце и блоке головоломки Судоку с позиций 1-9. Ячейка может использовать только неиспользуемые цифры, и предполагается, что функция возвращает то, дают ли цифры во всех векторах одну возможность или существует более одной возможности. Я понял, что это означает, что мне придется объединить все три вектора, а затем определить, где в результирующем шаблоне были «неустановленные» биты.
Однако моя функция в gdb, похоже, не возвращает правильную маску, хотя она была вдохновлена этим выводом: http://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge
Я пытаюсь объединить один набор из двух, затем третий набор в предыдущее слияние, получить число 1 в окончательном слиянии и вычесть его, чтобы получить количество нулей.
Затем я написал следующую функцию:
bool possibilities(unsigned short row, unsigned short col, unsigned short bloc)
{
unsigned int mask = (1 << col) - 1;
unsigned int inbw = (row & ~mask) | (col & mask);
unsigned int mask2 = (1 << bloc) - 1;
unsigned int final = (inbw & ~mask2) | (bloc & mask2);
int num_1s;
while (result != 0) {
result &= (result - 1);
num_1s++;
}
int zeroes = 32 - num_1s; // 32 being the presumed number of bits in a short.
if (zeroes == 1) return true;
return false;
}
Решение
Согласно этому документу:
http://www.cplusplus.com/doc/tutorial/variables/
Короткий не меньше чем полукокса. Не менее 16 бит
Так что вы можете ошибаться, вычисляя нули как 32 — num_1s.
Вместо этого вы можете получить беззнаковое короткое замыкание и заполнить его 1 с, установив 0 в первые 9 бит.
var = 0xFFFFFE00
Таким образом вы избегаете того, чтобы решение сильно зависело от размера используемой вами переменной.
Решение этой проблемы может быть следующим (предполагая row, col и bloc, как указано выше):
possibilities = row | col | bloc;
while (possibilities != 0) {
num_0s += ((~possibilities)&1);
possibilities = (possibilities >> 1);
}
Другие решения
Если я правильно понял, что каждый из row, col, а также bloc (sic) — это битовые маски с отдельными битами (предположительно, битами 0-8), представляющими наличие цифр 1-9, ваши маски ошибочны (и действительно совершенно бессмысленны). Например, если col имеет бит 8, то mask = (1 << col) - 1 смещается на 1 влево на 256 — поскольку крайне маловероятно, что unsigned short быть более 256 бит в ширину, это приводит к 0 после сдвига и затем к маске со всеми битами, установленными после вычитания 1. После этого (row & ~mask) | (col & mask) будет только col поскольку ~mask это 0.
На ум приходит пара простых вариантов:
1) Не объединяйте, просто делайте popcount для каждой из трех переменных в отдельности. В некоторых современных процессорах есть инструкция для popcount, поэтому, если вам удастся использовать ее, например, через встроенную функцию компилятора (например, __builtin_popcount), это будет даже быстрее.
2) Маскируйте биты по каждой переменной индивидуально и сдвигайте их в положение, например:
const unsigned int mask = 0x1FF;
unsigned int final = (col & mask) | ((row & mask) << 9) | ((bloc & mask) << 18);
Кроме того, не вычитайте число 1 из 32, а из 27 (= 3 × 9) — это максимальное количество 1 бит, если для каждой из трех переменных может быть установлено не более 9 бит.
редактировать: Может быть, я неправильно понял, что вы пытаетесь сделать путем слияния. Если вы имеете в виду простое объединение всех 1 битов в трех переменных, то это будет просто unsigned int final = col | row | bloc без необходимости маскировать. Затем вы вычли бы попконт (число 1 бит) из 9.