二进制反码求和原理（运算规则 校验算法 详解）

• 其中“或”运算又称逻辑加法、“与”运算又称逻辑乘法、“非”运算又称逻辑否定，“异或”运算又称逻辑半加法。
• 二进制数1和0在逻辑上可以代表“真”与“假”、“是”与“否”、“有”与“无”。
• 二进制数的逻辑运算算术运算是截然不同的，二进制数的逻辑运算是位对位的运算，本位运算结果不会对其他位产生任何影响，即不会出现算术运算中的进位或者借位。

1、“或”运算OR（逻辑加法）

通常用符号“+”或“∨”或“|”来表示。

运算规则如下：
0+0=0 ，0+1=1 ，1+0=1 ，1+1=1

0∨0=0，0∨1=1，1∨0=1，1∨1=1

0|0=0， 0|1=1， 1|0=1， 1|1=1

表示两者只要有一个1，其逻辑或的结果就为1。

• 简单总结为：“遇1得1”，也类似于并联电路。

例如：求51 | 5

• 深入扩展用法：

（1）与0相“或”可保留原值，与1相“或”可将对应位置1。

例如：将X=10100000的高四位不变，低四位置1的操作为 x| 00001111 = 10101111。

例如：将x的第1、2位置1的操作为x | 00000110B

（2）可以给二进制特定位上的数无条件赋值，比如把二进制最末位强行变成1，或者把二进制最末位变成0。

例如：把A=4（二进制为100）末位变为1的操作为 A|1= (100|001=101)；

把A=7（二进制为111）末位变为0的操作为 A|1-1= (111|001-1=110)。

（3）可以判断二进制数的奇偶。二进制的最末为0，表示该数为偶数，最末尾为1表示该数为奇数。例如：如果x|0=0，则x为偶数。

2、“与”运算AND（逻辑乘法）
通常用符号“×”或“∧”或“·”或“&”来表示。

运算规则如下：

0×0=0，0×1=0，1×0=0，1×1=1

0∧0=0，0∧1=0，1∧0=0，1∧1=1

0·0=0，0·1=0，1·0=0，1·1=1

0&0=0 ，0&1=0 ，1&0=0 ，1&1=1

表示只有当两者同时为1时，其逻辑与的结果才能等于1。

• 简单总结为：“遇0得0”，类似于串联电路。

例如：求51 & 5

• 深入扩展用法：

（1）与0相“与”可清零。例如：对x的第0、3位清零的操作为 x & 11110110B。

（2）与1相“与”可保留原值，例如：取x中的后两位的操作为 x & 00000011B。

（3）可以判断二进制数的奇偶。如果x&1=0，则x为偶数。

（4）可以清除掉二进制整数最右边的1，操作为 x & (x – 1)

3、“非”运算NOT（逻辑否定）

通常用符号“~”、“！”或者上方加一横线来表示。

运算规则如下：

例如：求~51

~ 00110011=11001100

• 简单总结为：“取反”。非开即关，非关即开。

4、“异或”运算XOR（逻辑半加运算）
通常用符号“^”、“⊕”来表示，

运算规则为：
0⊕0=0，0⊕1=1，1⊕0=1，1⊕1=0

0^0=0， 0^1=1， 1^0=1， 1^1=0
表示只有当两者不相同时，结果才为1，两者相同时结果为0。

• 简单总结为：“异1同0” ，直观意思即判断“是不是不一样”。

例如：求51 ^ 5

• 深入扩展用法：

（1）与0相”异或“可保留原值，与1相”异或“可将对应位置取反。例如：对x的3、7位取反的操作为 x^ 10001000B

（2）异或运算的逆运算是他本身，也就是说一个数经过两次异或后还是它本身。

（3）一个数和0异或是它的本身，和自身异或为0。即x^0=x ,x^x=0 。

（4）异或运算可以用于交换两个整数，不使用中间变量。

交换方法为：

A = A ^ B

B = A ^ B

A = A ^ B

证明：

已知 a=51,b=5

那么：

a=a^b=51^5

b=a^b=(51^5)^5=51^5^5=51^0=51

a=a^b=(51^5)^51=51^51^5=0^5=5

得到：a=5,b=51

校验算法

IP/ICMP/IGMP/TCP/UDP等协议的校验和算法都是相同的，算法如下：

在发送数据时，为了计算数IP据报的校验和。应该按如下步骤：
（1）把IP数据报的首部都置为0，包括校验和字段。
（2）把首部看成以16位为单位的数字组成，依次进行二进制反码求和。
（3）把得到的结果存入校验和字段中。
在接收数据时，计算数据报的校验和相对简单，按如下步骤：
（1）把首部看成以16位为单位的数字组成，依次进行二进制反码求和，包括校验和字段。
（2）检查计算出的校验和的结果是否等于零。
（3）如果等于零，说明被整除，校验是和正确。否则，校验和就是错误的，协议栈要抛弃这个数据包。
其中，二进制反码求和的计算方法：
首先，我们计算如图B-1所示的部分和。我们把每一列相加，如果有进位，就加到下一列。注意以下几点：
1————————第16列的进位
1 1————————第15列的进位
| 1
| 1 0
| | 1 1
| | | 1 0
| | | | 1 0
| | | | | 1 1
| | | | | | | 1 0
| | | | | | | | 1 0
| | | | | | | | | 1 1
| | | | | | | | | | 1 1
| | | | | | | | | | 1 0 0———–第3列的进位
| | | | | | | | | | | 1 0 0———–第2列的进位
| | | | | | | | | | | | | 1 1———第1列的进位
| | | | | | | | | | | | | | |
1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0
0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1
1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0
0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1
0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0
0 1 0 0 1 0 0 1 0 1 0 0 1 1 1 1
0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0
__________________________________
1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 部分和
图B-1 二进制记法的部分和
1，当我们加第1列(最右边一列)的时候，我们得到7。在二进制中，数7是111。我们保留最右边的1，把其余的位进到第2列和第3列。
2，当我们加第2列时，我们计入从第1列来的进位。结果是8，它是二进制的1000。我们保留第一个位(最右边的)，把其余100进位给第3列、第4列和第5列。
3，对每一列重复以上过程。
4，当我们加完最后一列时，我们有两个1没有列可以进行相加。这两个1在下一个步骤中应与部分和(Partial sum)相加。
B.1.2和
如果最后一列没有进位，那么部分和就是和。但是，如果还有额外的列(在本例中，有一个具有两行的列)，那么就要把它加到部分和中，以便得出和。下图给出了这样的计算，现在我们得出了和。
1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 部分和
1
1
____________________________________
1 0 0 1 0 1 1 0 1 1 1 0 1 0 1 1 和
0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 校验和
图B-2 二进制记法的和与校验和
B.1.2校验和
在计算出和以后，我们把每一个位求反码，得出检验和。图B-2也给出了检验和。二进制计算方法其实可以转换为十进制计算，原理相同。

算法的实现：
首先，查看了Linux 2.6内核中的校验算法，使用汇编语言编写的，显然效率要高些。代码如下：
unsigned short ip_fast_csum(unsigned char * iph,
unsigned int ihl)
{
unsigned int sum;

__asm__ __volatile__(
“movl (%1), %0 ;\n”
“subl , %2 ;\n”
“jbe 2f ;\n”
“addl 4(%1), %0 ;\n”
“adcl 8(%1), %0 ;\n”
“adcl 12(%1), %0 ;\n”
“1: adcl 16(%1), %0 ;\n”
“lea 4(%1), %1 ;\n”
“decl %2 ;\n”
“jne 1b ;\n”
“adcl , %0 ;\n”
“movl %0, %2 ;\n”
“shrl , %0 ;\n”
“addw %w2, %w0 ;\n”
“adcl , %0 ;\n”
“notl %0 ;\n”
“2: ;\n”

: “=r” (sum), “=r” (iph), “=r” (ihl)
: “1” (iph), “2” (ihl)
: “memory”);
return(sum);
}

在这个函数中，第一个参数显然就是IP数据报的首地址，所有算法几乎一样。需要注意的是第二个参数，它是直接使用IP数据报头信息中的首部长度字段，不需要进行转换，因此，速度又快了（高手就是考虑的周到）。使用方法会在下面的例子代码中给出。

第二种算法就非常普通了，是用C语言编写的。我看了许多实现网络协议栈的代码，这个算法是最常用的了，即使变化，也无非是先取反后取和之类的。考虑其原因，估计还是C语言的移植性更好吧。下面是该函数的实现：
unsigned short checksum(unsigned short *buf,int nword)
{
unsigned long sum;

for(sum=0;nword>0;nword–)
sum += *buf++;
sum = (sum>>16) + (sum&0xffff);
sum += (sum>>16);
return ~sum;