奇偶位数的位奇偶校验码

我正在尝试查找位串的奇偶校验位，以便它返回1，如果x有奇数个0。
我只能用基本的位运算和我有什么迄今为止通过大多数测试，但我想知道两两件事：奇偶位数的位奇偶校验码

为什么χ^（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; 
}

来源

2011-09-23 tippenein

你从哪里找到该算法？ – rnunes

不使用'int'，会有溢出，这是未定义的行为。使用'unsigned'和'1u'来代替，这里的环绕是明确的。 –

此算法不起作用。它的0至255 –

我会用实际计数，而不是利用数字的表示比特级别的黑客，这将既感到更安全，更清洁，易于理解。当然，速度可能较慢，但这是一个相当不错的折衷，尤其是当人们对性能期望一无所知时。

这样做，只需编写代码来计算1位的数量，最直接的解决方案通常归结为一个循环。

UPDATE：鉴于（怪异和恼人的）限制，我的回答很可能是unwind在bithacks页面上"naive"解决方案给出的循环。那不会很好，但是我可以去做一些有用的事情。 :)

来源

2011-09-23 14:45:25 unwind

我肯定将使用循环方便地读每一位甚至只是XOR所有位在一起，但对于这项任务，我不能使用的控制结构。只是| ^＆>><<〜+！所以，你的回应是我对此的直接反应，但没有骰子。 – tippenein

我已经采取了位计数以前编写的代码，只是AND'd与为0x1的结果，看看是否有奇数个与否。但是，我通过强力执行bitCount（int x）算法;检查每一位与！（x＆（1 << bit＃））目前对我来说这还不够好，但现在已经解决了位平价问题。 – tippenein

你的奇偶校验功能实际上并不至于我可以告诉工作 - 它似乎得到正确的答案大约一半的时间，大约是为返回随机结果（或者甚至只是返回0，好或1始终）。

有几个位级的黑客，其做实际工作：http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive - 你可能想看看这最后一个：http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel

来源

2011-09-23 15:02:02

我意识到我的完整代码不起作用，但x ^（x-1）似乎给出了对我尝试的值有意义的答案。如果你是正确的，那么我应该转储它并重新开始。 – tippenein

只要尝试输入值0,1,2和3，你会发现它不起作用。 –

位奇偶校验可以这样进行：

#include <stdio.h> 

int parity(unsigned int x) { 
    int parity=0; 
    while (x > 0) { 
     parity = (parity + (x & 1)) % 2; 
     x >>= 1; 
    } 
} 

int main(int argc, char *argv[]) { 
    unsigned int i; 
    for (i = 0; i < 256; i++) { 
     printf("%d\t%s\n", i, parity(i)?"odd":"even"); 
    } 
}

来源

2011-09-23 15:05:18 sastanin

奇偶位数的位奇偶校验码

回答

相关问题