首页 > 代码库 > 奇偶校验算法

奇偶校验算法

1即计算出所给数中包含1的个数

方法一:每一位分别异或(时间复杂度O(n)n代表数位数)

函数功能:如果1的个数为奇数个,则返回1,如果1的个数为偶数个,则返回0。
parity_check(unsigned x)
{
int val=0;
while(x)
{
val^=x;//val 和x进行异或运算
x>>=1;//x右移一位
}
return val&0x1;//取末位运算. val的二进制形式最后一位位1则返回1,为0则返回0.
}
实例分析,假设无符号数x转换成二进制后长度为5位,五个位置的数据(二进制数,0或者1)分别记为①②③④⑤,两个位置的数进行异或运算记为①^②。注意,给定x后化成二进制形式最高位①为1。
则整个程序执行过程(只需要考虑异或运算结果的末位数)可以表述为:
(((⑤^④)^③)^②)^①——表达式1
假设⑤和④不同,则⑤^④运算结果为1,表示有一个1。表达式1可以化成:((1^③)^②)^①——表达式2
③如果不是1,则表示⑤④③中只有一个1;如果是1,⑤④③中有两个1.这两种结果等价于1^③运算的结果。假设③就是1,则表达式2可以化成:(0^②)^①——表达式3
假设②为0(①为1是前提),则表达式3可以化简为:(0^0)^1,运算结果为1,即五个二进制数中有奇数个1,⑤和④中有一个1,③是1,②为0,①为1共3个1得以验证。
该算法形式简单,功能强大,却不好理解。该函数可用于奇偶校验。
 
方法二:时间复杂度0(1的个数)
int a=1;
while(x)
{
a^=0;//改为 count++;可以计算该数二进制中包含1的个数
x&(x-1);
}
方法三:时间复杂度0(lgn)n为位数
8位的数据D(D7~D0),他的算法为:

D ^= D >>4;

D ^= D >>2;

D ^= D >>1;

D&=1;

最后D就是偶校验的值了。

可能有的同学一时之间看不明白算法的原理,这里解释一下吧。

首先从D里面找两个位D1和D0,而D1D0的偶校验值E0=D1^D0,这个大家都明白的,然后D3和D2的检验值E1=D3^D2,同理还有E2=D5^D4以及E3=D7^D6;

E0=1时代表了D1和D0里面有奇数个1,E1、E2和E3同理;

然后复习一下小学数学:奇数*奇数=奇数,偶数*奇数=偶数

如果E0和E1里面有奇数个1,那么D3~D0里面就有奇数数个1,此时D3~D0的偶校验值为1;

“如果E0和E1里面有奇数个1”这句话的意思不就是求由E1和E0组成的两位二进制的偶校验么?而且当E1E0的偶校验值F0=1时,对应的D3~D0的偶校验值也为1。

同理,E3E2的偶校验值F1=1时,对应的D7~D4的偶校验值也为1;

继续同理,由F1和F0组成的两位二进制的偶校验G0=1时,对应的是E3~E0的偶校验值为1,同时对应的D7~D0的偶校验值为1。

于是求D7~D0的偶校验值变成了求F1F0的偶校验值。

那么首先就要将D7~D0的8个位两两分组后在分别求异或,然后再将得出的值的4个位两两分组后分别异或,最后将得出的值的2个位进行异或,得到的值就是D7~D0的偶校验值了。

而分组则不必是相邻的,将D右移4位再和原来的D进行异或的话就简单多了

D7——D3

D6——D2

D5——D1

D4——D0

如此类推,每次先进行右移,然后和原来的值异或,最终就能得到D的校验值了;另外在计算的过程中,仅仅需要关注后面的位数就可以了,如第二次计算时,高4位会有一些数据,到最后高7位也会有数据的,但这些数据都已经没有用了,所以最后只需要来一个&1就可以l。

于是文章开头的那段8位二进制数的算法为:

D ^= D >>4;

D ^= D >>2;

D ^= D >>1;

D&=1;

另外对于2^N位二进制数,第一次右移(2^N)/2位后再异或,然后重复类似的计算N次就可以了。

 
 

奇偶校验算法