Ответ 1
Попробуйте:
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;
}
Вальтера
Значение имеет четную четность, если оно равно четному числу 1 бит. Значение имеет нечетную четность, если оно имеет нечетное число из 1 бита. Например, 0110
имеет четную четность, а 1110
имеет нечетную четность.
Мне нужно вернуть 1
, если x
имеет четную четность.
int has_even_parity(unsigned int x) {
return
}
Попробуйте:
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;
}
Вальтера
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return (~x) & 1;
Предполагая, что вы знаете, что ints - 32 бита.
Посмотрим, как это работает. Чтобы это было просто, позвольте использовать 8-битное целое число, для которого мы можем пропустить первые два сдвига /XOR. Пусть обозначают биты a через h. Если посмотреть на наш номер, мы увидим:
(a b c d e f g h)
Первая операция x ^= x >> 4
(помните, что мы пропускаем первые две операции, так как в этом примере мы имеем дело только с 8-разрядным целым числом). Пусть записываются новые значения каждого бита, комбинируя буквы, которые являются XOR'd вместе (например, ab означает, что бит имеет значение a xor b).
(a b c d e f g h) исключающее (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) исключающее (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) исключающее (0 a b ac bd ace bdf aceg)
В результате появляются следующие биты:
(a ab abcdefgh abcdefgh)
Мы накопили все биты в исходном слове, XOR'd вместе, в младшем значении. Таким образом, этот бит теперь равен нулю, если и только если в входном слове было четное число 1 бит (даже четность). Тот же процесс работает с 32-битными целыми числами (но требует этих двух дополнительных сдвигов, которые мы пропустили в этой демонстрации).
Последняя строка кода просто удаляет все, кроме наименее значимого бита (& 1
), а затем переворачивает его (~x
). Тогда результатом будет 1, если четность входного слова была четной или в противном случае - 0.
Шон Эрон Андерсон (Seander Ecs Anderson), [email protected], без стеснения ответил:
Вычислить четность слова с умножением
Следующий метод вычисляет четность 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 года.
В GCC есть встроенная функция для этого:
Встроенная функция:
int __builtin_parity (unsigned int x)
Возвращает четность
x
, то есть число 1 бит в x по модулю 2.
т.е. эта функция ведет себя как has_odd_parity
. Инвертировать значение для has_even_parity
.
Это гарантировано будет самой быстрой альтернативой GCC. Конечно, его использование не является переносимым как таковое, но вы можете использовать его в своей реализации, например, защищенным макросом.
Основная идея такова. Уберите самый правый бит "1", используя x & ( x - 1 )
. Предположим, что x = 13 (1101), а операция x & ( x - 1 )
равна 1101 & 1100
, что составляет 1100, обратите внимание, что самый правый бит установлен в 0
.
Теперь x
- 1100
. Операция x & ( x - 1 )
i.e 1100 & 1011
равна 1000
. Обратите внимание, что оригинал x
равен 1101
, а после двух операций x & (x - 1)
x
- 1000
, то есть два установленных бита удаляются после двух операций. Если после odd
количества операций, x
становится равным нулю, тогда его нечетная четность, иначе это четная четность.
Обобщение ответа @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);
}
int parity_check(unsigned x) {
int parity = 0;
while(x != 0) {
parity ^= x;
x >>= 1;
}
return (parity & 0x1);
}
Вот одна строка #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.
Это довольно старый вопрос, но я публикую это для тех, кто может использовать его в будущем.
Я не буду добавлять пример выполнения этого в c, так как уже есть достаточно хороших ответов.
В случае, если конечный результат должен быть частью кода, который может работать (компилироваться) с помощью программы c, я предлагаю следующее:
.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, таким образом устанавливая флаг четности cpus, а затем устанавливая переменную (RAX) на 0 или 1, если флаг четности включен или нет.