Как проверить, имеет ли значение четную четность битов или нечетную?
Значение имеет четную четность, если оно имеет четное число 1 бит. Значение имеет нечетную четность, если оно имеет нечетное число 1 бит. Например, 0110 имеет даже паритет, и 1110 имеет странное соотношение.
Я должен вернуться 1 если x имеет даже паритет.
int has_even_parity(unsigned int x) {
return
}
8 ответов
Пытаться:
int has_even_parity(unsigned int x){
unsigned int count = 0, i, b = 1;
for(i = 0; i < 32; i++){
if( x & (b << i) ){count++;}
}
if( (count % 2) ){return 0;}
return 1;
}
Valter
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return (~x) & 1;
Предполагая, что вы знаете, целые 32-битные.
Посмотрим, как это работает. Для простоты давайте используем 8-битное целое число, для которого мы можем пропустить первые два сдвига /XOR. Давайте обозначим биты от a до h. Если мы посмотрим на наш номер, мы увидим:
(a b c d e f g h)
Первая операция x ^= x >> 4 (помните, что мы пропускаем первые две операции, так как в этом примере мы имеем дело только с 8-битным целым числом). Давайте напишем новые значения каждого бита, объединив буквы, которые являются XOR'ами (например, ab означает, что бит имеет значение a xor b).
(a b c d e f g h) xor (0 0 0 0 a b c d)
Результатом являются следующие биты:
(a b c d ae bf cg dh)
Следующая операция x ^= x >> 2:
(a b c d ae bf cg dh) xor (0 0 a b c d ae bf)
Результатом являются следующие биты:
(a b ac bd ace bdf aceg bdfh)
Обратите внимание, как мы начинаем накапливать все биты на правой стороне.
Следующая операция x ^= x >> 1:
(a b ac bd ace bdf aceg bdfh) xor (0 a b ac bd ace bdf aceg)
Результатом являются следующие биты:
(ab abc abcd abcde abcdef abcdefgh abcdefgh)
Мы собрали все биты в оригинальном слове, XOR вместе, в младшем значащем бите. Таким образом, этот бит теперь равен нулю тогда и только тогда, когда во входном слове было четное число 1 бит (четная четность). Тот же процесс работает с 32-разрядными целыми числами (но требует тех двух дополнительных сдвигов, которые мы пропустили в этой демонстрации).
Последняя строка кода просто удаляет все, кроме наименее значимого бита (& 1 а затем переворачивает его (~x). Тогда результат равен 1, если четность входного слова была четной, или ноль в противном случае.
В GCC для этого есть встроенная функция:
Встроенная функция:
int __builtin_parity (unsigned int x)Возвращает соотношение
x, т.е. количество 1-бит в х по модулю 2.
Т.е. эта функция ведет себя как has_odd_parity, Инвертировать значение для has_even_parity,
Это гарантированно будет самой быстрой альтернативой в GCC. Конечно, его использование не переносимо как таковое, но вы можете использовать его в своей реализации, например, с помощью макроса.
Шон Эрон Андерсон (Seander Ecs Anderson), seander@cs.stanford.edu, без стеснения ответил:
Вычислить четность слова с умножением
Следующий метод вычисляет четность 32-битного значения только за 8 операций> с использованием умножения.
unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;
Также для 64-битных 8 операций все еще достаточно.
unsigned long long v; // 64-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;
Эндрю Шапира придумал это и отправил мне 2 сентября 2007 года.
Чтобы обобщить ответ @TypelA для любой архитектуры:
int has_even_parity(unsigned int x)
{
unsigned char shift=1;
while (shift < (sizeof(x)*8))
{
x ^= (x>>shift);
shift<<=1;
}
return !(x & 0x1);
}
Основная идея заключается в следующем. Удалите самый правый бит "1" с помощью x & ( x - 1 ), Скажем, х = 13(1101) и операция x & ( x - 1 ) является 1101 & 1100 это 1100, обратите внимание, что самый правый установленный бит преобразуется в 0,
Сейчас x является 1100, Операция x & ( x - 1 ) т.е. 1100 & 1011 является 1000, Обратите внимание, что оригинал x является 1101 и после двух операций x & (x - 1) x является 1000т.е. два установленных бита удаляются после двух операций. Если после odd количество операций, x становится равным нулю, тогда это нечетное соотношение, иначе это четное соотношение.
Вот одна строка#define это делает трюк для char:
#define PARITY(x) ((~(x ^= (x ^= (x ^= x >> 4) >> 2) >> 1)) & 1) /* even parity */
int main()
{
char x=3;
printf("parity = %d\n", PARITY(x));
}
Это портативно, как черт и легко модифицируется для работы с большими словами (16, 32 бит). Важно также отметить, используя #define Ускоряет код, каждый вызов функции требует времени, чтобы протолкнуть стек и выделить память. Размер кода не страдает, особенно если он реализован всего несколько раз в вашем коде - вызов функции может занять столько же объектного кода, сколько XOR.
По общему признанию, те же самые эффективности могут быть получены с использованием встроенной версии функции этого, inline char parity(char x) {return PARITY(x);} (GCC) или __inline char parity(char x) {return PARITY(x);} (MSVC). Предполагая, что вы сохраняете одну строку определения.
int parity_check(unsigned x) {
int parity = 0;
while(x != 0) {
parity ^= x;
x >>= 1;
}
return (parity & 0x1);
}
Это довольно старый вопрос, но я публикую его для тех, кто мог бы использовать его в будущем.
Я не буду добавлять пример этого в c, так как уже есть достаточно хороших ответов.
Если предполагается, что конечным результатом будет фрагмент кода, который может работать (быть скомпилирован) с программой ac, тогда я предлагаю следующее:
.code
; bool CheckParity(size_t Result)
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
END
Это фрагмент кода, который я использую для проверки четности результатов вычислений в 64-битной программе c, скомпилированной с использованием MSVC. Вы можете явно портировать его на 32-битные или другие компиляторы.
Преимущество этого в том, что он намного быстрее, чем при использовании c, а также использует функциональность cpus.
Этот пример принимает в качестве входного параметра (передаваемый в RCX - __fastcall соглашение о вызовах). Он увеличивает его на 0, устанавливая таким образом флаг четности процессора и затем устанавливая переменную (RAX) в 0 или 1, если флаг четности включен или нет.