bitParity - поиск нечетного числа бит в целом числе. - PullRequest
Новая
       22

bitParity - поиск нечетного числа бит в целом числе.

2 голосов
/ 03 февраля 2012

Мне нужно создать функцию bitParity(int x), которая принимает целое число и возвращает 1, если есть нечетное число 0 в битовой форме x, и 0 в противном случае.

Пример: bitParity(5) = 0, bitParity(7) = 1

Однако это сложно, так как я могу использовать только битовые операторы для этой задачи (! ˜ & ˆ | + << >> - единственные допустимые).Это означает, что нет петель, if-then или чего-либо подобного.Можно использовать константы.

Пока что то, что у меня есть, не работает, но я решил, что мне следует сдвинуть биты целых чисел 16, 8, 4 раз и XOR оставшиеся целые числа.

Может кто-нибудь дать совет?Спасибо.

Ответы [ 3 ]

7 голосов
/ 03 февраля 2012

Для 32-битных номеров: 

function bitParity(int x) {
   x ^= x >> 16;
   x ^= x >> 8;
   x ^= x >> 4;
   x &= 0xf;
   return (0x6996 >> x) & 1;
}

Примечание * 0x6996 представляет битовый вектор чисел 1, 2, 4, 7, 8, 11, 13 и 14. Все 4-битные значения, которые могут быть представлены нечетным количество бит В 0x6996 бит устанавливается, если его позиция в векторе соответствует (1, 2, 4, 7, 8, 11, 13 или 14).

Вот почему (0x6996 >> x) & 1 имеет смысл, после сдвига на x это выражение приведет к возвращенному 1, только если x равно любому из значений в битовом векторе, что означает нечетное число биты были установлены.

5 голосов
/ 03 февраля 2012

Это правильно решается с помощью цикла.Но вот способ сделать это без. 

x = (x & 0x0000FFFF) ^ (x >> 16)
x = (x & 0x000000FF) ^ (x >> 8)
x = (x & 0x0000000F) ^ (x >> 4)
x = (x & 0x00000003) ^ (x >> 2)
x = (x & 0x00000001) ^ (x >> 1)

Редактировать: мне не нужно &.Лучшая версия: 

x ^= x >> 16
x ^= x >> 8
x ^= x >> 4
x ^= x >> 2
x ^= x >> 1
x &= 1;
0 голосов
/ 03 февраля 2012

Вот одна из моих функций, которые я использовал во время моей работы над дипломной работой бакалавра;) 

/** Calculates number of bits in unsigned char
 * @brief Bit count
 * @param input to be checked
 * @return int 0-8
 */
int bitCount( unsigned char input)
{
    static unsigned char count[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
    return (int)(
            count[ input & 0x0f] +
            count[ (input >> 4) & 0x0f]
    );
}

Таким образом, общее число для целого числа 4B будет: 

int bytes = bitCount( (unsigned char)((number >> 0)&255))
            + bitCount( (unsigned char)((number >> 8)&255))
            + bitCount( (unsigned char)((number >> 16)&255))
            + bitCount( (unsigned char)((number >> 24)&255));

И четность: 

 return bytes%2;
 return bytes&1; // if you preffer

Я всегда хотел повторно использовать эти коды:)

РЕДАКТИРОВАТЬ : Как вы могли заметить, unsigned char (8b) можно разделитьна 2 части по 4b каждый, что означает 16 значений, которые легко хранить и использовать повторно.Таким образом, вы берете первые 8b из целого числа, делите их на две части.Убедитесь, что они оба находятся в интервале <0,15>, и просто получите счетчик битов.Повторите:)

...