奇偶位數的位奇偶校驗碼

我正在嘗試查找位串的奇偶校驗位，以便它返回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

奇偶位數的位奇偶校驗碼

回答

相關問題