Мне нужно создать функцию bitParity(int x), которая принимает целое число и возвращает 1, если в битовой форме x есть нечетное число 0 и 0.
Пример: bitParity(5) = 0, bitParity(7) = 1
Однако это сложно, так как я могу использовать только битовые операторы по этой проблеме (! ˜ & ˆ | + << >> являются единственными законными). Это означает, что нет циклов, if-then или что-то в этом роде. Можно использовать константы.
До сих пор то, что у меня не работает, но я полагал, что я должен смещать биты целого числа 16, 8 и 4 times и XOR оставшиеся целые числа.
Может кто-нибудь предложить какой-нибудь совет? Спасибо.
Это правильно решается с помощью цикла. Но вот способ сделать это без.
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;
Для 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 равно любому из значений в битовом векторе, то есть нечетное количество битов было задавать.
Вот одна из моих функций, которые я использовал во время моей работы над бакалаврской диссертацией;)
/** 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>, и просто получают счетчик бит. Повторите:)