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

二进制反码求和原理

二进制补码的计算原理

  • 补码作用:可以把减法按加法来处理;同时,还可以将符号位和其它位统一处理。
  • 正数的补码与原码相同;
  • 负数的补码是其反码加1。

我们以8位二进制为例,计算5-2=3,用二进制表示为:

00000101(原)+10000010(原)

=00000101(原)+11111101(反)

=00000101(原)+11111110(补)

=00000011

  • 补码计算方法是在其原码的基础上, 符号位不变, 其余各位取反再加一,那么补码为什么要这么算,其中的原理是什么呢?

1、为什么要取反再加一?

仍以上面的8位二进制数为例,模是100000000,即2^8=256,十进制数2的8位二进制数表示是00000010,取反得到11111101,二者相加:00000010(原)+11111101(反)=11111111,而11111111+1=100000000(模),

由以上可以看出:二进制数原码加上取反后得到的值再加一就刚好得到模。而已知原码+补码=模,因此能够得出结论:补码等于原码取反加一,这是计算补码最简单的方法。在这个过程中,反码没有什么实质意义,它只是计算机为了计算补码时的一个中间量。

2、为什么符号位可以参与运算,和其它位统一处理?

在计算机中正数和负数存储方式是不同的,我们通过观察二进制数第一位是0还是1可以知道这个数是正数还是负数。如果它的第一位是0,那么它就是正数原码,如果它的第一位是1,那么它就是负数补码。这里的符号位其实是算出来的,所以它可以参与运算。

我们仍以8位二进制为例,计算2-5=-3,用二进制表示为:

00000010(原)+10000101(原)

=00000010(原)+11111010(反)

=00000010(原)+11111011(补)

=11111101

计算结果11111101第一位为1,那么这个数值是负数补码,反求原码=(00000010)反+1 =00000011= 十进制数3,由此可知,11111101表示的是负数的3,在运算过程中我们没有考虑符号位,仅用单纯的加法运算进行运算,而得到的结果11111101也没有人为去添加一个符号位,符号位是计算所得的,因为在计算过程中存在第一位为0则是正数,为1则是负数这个规律,于是我们认定第一位为符号位,也就是先有规律之后才有规定。

运算规则

二进制数的逻辑运算有四种:“与”运算AND、“或”运算OR、 “非”运算NOT、“异或”运算XOR。

  • 其中“或”运算又称逻辑加法、“与”运算又称逻辑乘法、“非”运算又称逻辑否定,“异或”运算又称逻辑半加法。
  • 二进制数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;

声明:所有白马号原创内容,未经允许禁止任何网站及个人转载、采集等一切非法引用。本站已启用原创保护,有法律保护作用,否则白马号保留一切追究的权利。发布者:甜媛,转转请注明出处:https://www.bmhysw.com/article/16321.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
甜媛甜媛

相关推荐

  • 无线能连接上但不能上网,解决无线连接成功但无法上网的问题

    解决无线连接成功但无法上网的问题 检查连接 重置路由器 检查IP地址 更新驱动程序 1.检查连接 首先检查您的电脑是否已连接到无线网络。如果您已连接,请确保您的设备已获得IP地址。 如果您的设备没有获得IP地址,请尝试断开连接并重新连接。您还可以尝试通过重启计算机来解决该问题。 2.重置路由器 如果您已经检查了您的设备和网络连接,但无法上网,请尝试重置您的路…

    2023-06-12
    00
  • 0xc00000e9怎么修复?Win11错误代码0xc00000e9简单解决办法

    如何修复0xc00000e9错误代码?Win11错误代码0xc00000e9简单解决办法 错误代码0xc00000e9的原因 Win11错误代码0xc00000e9简单解决办法 结论 错误代码0xc00000e9的原因 错误代码0xc00000e9是Windows系统中常见的错误代码之一。它通常会在系统启动时出现,导致计算机无法正常启动。这个错误代码的原因有…

    2023-06-19
    00
  • 16比9尺寸的长宽是多少(9:16图片尺寸宽和高)

    国际单位中,1英寸=2.54厘米,21寸显示器≈54厘米(cm) 目前市面上显示器主要有,16比9和4比3两种: 1、16比9属于宽屏,是我们日常使用的主流显示器,尺寸为21.5寸,屏幕尺寸一般47.6厘米*26.8厘米; 2、4比3属于普屏,尺寸为21寸,主要用于安防设备,屏幕尺寸40厘米*30厘米。 在显示器为佳分辨率上,21寸显示器为佳分辨率为1920…

    2022-03-16
    00
  • wps中的word怎么转化为pdf

    在许多情况下,我们需要将WPS中的Word文档转化为PDF格式,以确保文档的格式和内容在不同设备上保持一致,同时也增加了文档的安全性。以下是一个简单的步骤指南,帮助您将WPS中的Word文档转化为PDF。 步骤一:打开WPS Word文档 首先,打开您想要转化为PDF的WPS Word文档。确保您的文档已经编辑和排版好,因为PDF将保留文档的当前格式。 步骤…

    2023-09-07
    00
  • 显卡深度学习(深度学习的显卡对比评测:2080ti vs 3090 vs A100)

    显卡大幅降价了但是还可以再等等,新的40系列显卡也要发售了,所以我们先看看目前上市的显卡的性能对比,这样也可以估算下40显卡的性能,在以后购买时作为参考。 但是在本文之前一定要说下的是:本文并不推荐现在就买显卡,除非必须,现在一定不要买显卡,谁买谁吃亏,目前的情况是,“等” 就对了 回到正题,在这篇文章中我整理了几个在 NVIDIA GeForce RTX …

    2022-04-21 投稿
    00

联系我们

QQ:183718318

在线咨询: QQ交谈

邮件:183718318@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

关注微信