我试图找到一个位串的奇偶校验,如果x有一个奇数#为0,它返回1.
我只能使用基本的按位运算,到目前为止,我已经通过了大部分测试,但我想知道两件事:
为什么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;
}
我的解决方案（对于输入块的每一位，都有这样一行）：
*parity ^= (((x[0] >> 30) & 0x00000001) * 0xc3e0d69f);
所有类型均为uint32。该行获取输入 x 的第二位，将其移位到 LSB并将所有其他位设置为零。然后，将 32 位奇偶校验与该位的相应奇偶校验集进行异或。
我发现这个乘法解决方案是执行条件异或的最快方法。有更快的方法吗？
我正在尝试计算大量uint64的位奇偶校验.比特奇偶校验是指接受uint64的函数,如果设置的比特数是偶数则输出0,否则为1.
目前我正在使用以下功能(@Troyseph,在这里找到):
uint parity64(uint64 n){
n ^= n >> 1;
n ^= n >> 2;
n = (n & 0x1111111111111111) * 0x1111111111111111;
return (n >> 60) & 1;
}
相同的SO页面具有以下汇编例程(由@papadp提供):
.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
它利用了机器的奇偶校验标志.但我不能让它与我的C程序一起工作(我知道旁边没有汇编).
问题.如何在C源文件中包含上面(或类似)代码作为内联汇编,以便该parity64()函数运行该代码？
(我在Intel Xeon Haswell上使用GCC和64位Ubuntu 14)
如果它有任何帮助,则parity64()在以下例程中调用该函数:
uint bindot(uint64* a, uint64* b, uint64 entries){
uint parity …我必须创建一个bitParity(int x)取整数的函数,1如果0在位形式中有奇数个,则返回x,0否则返回.
例如: bitParity(5) = 0, bitParity(7) = 1
但是,这很难,因为我只能在这个问题上使用位运算符(! ˜ & ˆ | + << >>是唯一合法的).这意味着,没有循环,if-then或任何类型的东西.可以使用常量.
到目前为止,我有什么不行的,但我想,我应该整数的位移位16,8以及4时间和XOR剩余的整数.
有人可以提供一些建议吗？谢谢.
我想找出第1位的数字是奇数还是偶数.这是代码:
int odd_ones(unsigned x)
{
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
return !(x&1);
}
但我不知道它是如何运作的; 我已经坚持了很长时间.