Я пытаюсь найти четность битовой строки, так что она возвращает 1, если x имеет нечетное число из 0.
Я могу использовать только базовые побитовые операции и то, что у меня есть, проходит большинство тестов, но мне интересно 2 вещи:
Почему x ^ (x + ~ 1) работает? Я наткнулся на это, но, похоже, вы получите 1, если есть нечетное количество бит и что-то еще, если даже. Как 7 ^ 6 = 1, потому что 7 = 0b0111
Это правильное направление решения проблемы для этого? Я предполагаю, что моя проблема связана с первой операцией, в частности (x + ~ 1), потому что она переполнит некоторые номера дополнений 2. Спасибо
Код:
int bitParity(int x) { int first = x ^ (x + ~1); int second = first ^ 1; // if first XOR gave 1 you'll return 0 here int result = !!second; return result; } Я бы использовал фактический подсчет, а не хакеры на уровне бит, которые используют представление чисел, которые будут чувствовать себя более безопасными и быть более чистыми и понятными. Наверное, медленнее, конечно, но это довольно хороший компромисс, особенно когда никто ничего не знает о ожиданиях производительности.
Сделайте это, просто напишите код, чтобы подсчитать количество 1 бит, наиболее прямолинейное решение обычно сводится к циклу.
ОБНОВЛЕНИЕ: Учитывая (странные и раздражающие) ограничения, мой ответ, вероятно, состоял бы в том, чтобы отключить цикл, указанный в «наивном» решении на странице bithacks . Это было бы некрасиво, но тогда я мог бы сделать что-то полезное. 🙂
Ваша функция четности на самом деле не работает, насколько я могу судить, – кажется, что ответ получил примерно половину времени, что примерно так же хорошо, как возврат случайного результата (или даже просто возrotation 0 или 1 все время) ,
Существует несколько бит-хаков, которые действительно работают: http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive – вы, вероятно, захотите посмотреть на последний из них: http: //graphics.stanford .edu / ~ seander / bithacks.html # ParityParallel
Бит-четность может быть выполнена следующим образом:
#include int parity(unsigned int x) { int parity=0; while (x > 0) { parity = (parity + (x & 1)) % 2; x >>= 1; } } int main(int argc, char *argv[]) { unsigned int i; for (i = 0; i < 256; i++) { printf("%d\t%s\n", i, parity(i)?"odd":"even"); } }