基础野:细说无符号整数[通俗易懂]

基础野:细说无符号整数[通俗易懂]Brief本来只打算理解JS中0.1+0.2==0.30000000000000004的原因,但发现自己对计算机的数字表示和运算十分陌生,于是只好恶补一下。本篇我们一起来探讨一下基础的基础

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

Brief                              

  本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004的原因,但发现自己对计算机的数字表示和运算十分陌生,于是只好恶补一下。

  本篇我们一起来探讨一下基础的基础——无符号整数的表示方式和加减乘除运算。

 

Encode                              

  无符号整数只能表示大于或等于零的整数值。其二进制编码方式十分直观,仅包含真值域。

  我们以8bit的存储空间为例,真值域则占8bit,因此可表示的数值范围是{0,…,255},对应的二进制编码是{00000000,…,11111111}。

  从集合论的角度描述,我们可以将十进制表示的数值范围定义为集合A,将二进制表示的数值范围定义为集合B,他们之间的映射为f。f(a)=b,其中a属于A、b属于B。并且f为双射函数。因此无符号整数表示方式具有如下特点:

  1. 可表示的数值范围小;

  2. 十进制表示的数值范围与二进制表示的数值范围的元素是一一对应的,两者可精确映射转换。(相对浮点数而言,某些二进制表示的数值只能映射为十进制表示的数值的近似值而已)

 

Zero-extend                          

  零扩展运算用于在保持数值不变的前提下,不同字长的整数之间的转换。

  例如现在我们要将8bit的00000100扩展为16bit,那么我们只要将高8bit设置为0即得到000000000000000100,而其数值并不产生变化。

 

Truncation                           

  截断会减少位数,并对原始值取模。模为2^n,n为截断后的位数。

  例如现在将16bit的000000100000000100截断为8bit,那么结果为00000100,而模是2^8。

 

Addition                             

  注意:位级运算均是模数运算,即加减乘除后均会对运算结果取模,并以取模后的结果作为终止返回。

  无符号整数加法的运算顺序:

  1. 算术加法;

  2. 执行截断操作。

  示例,两个4bit的无符号数相加(11+6):

  1011

+0110

10001,然后执行截断得到0001

 

Subtraction                          

  无符号整数减法的运算顺序:

  1. 将减法转换为加法(对减数取补码);

  2. 算术加法;

  3. 执行截断操作。

  示例,两个4bit的无符号数相减(11-6):

 1011

-0110

对减数求补码后,减法转换为加法

  1011

+1010

 10101,然后执行截断得到0101

 

Multiplication                        

  对于乘法实质上就是通过移位操作和加、减法组合而成,且根据乘数是否为2的n次幂区别处理。

  1. 对于乘数为2的n次幂的情况,乘法公式为:a<<n,如6*4等价于6*(2^2),则可转换为移位操作6<<2即可。然后再对结果取模。

  2. 对于乘数不为2的n次幂的情况

      2.1. 将乘数以二进制形式表示,并以连续的1作为分组。如43的二进制形式为00(1)0(1)0(11),从左至右可分成3组分别是(1)、(1)和(11)。

      2.2. 以n表示每组的最高位的指数,以m表示每组最低位的指数。如第一组n=m=5,第二组n=m=3,第三组n=1而m=0。

      2.3. 根据公式(x<<n+1)-(x<<m)对每组进行运算,并将结果相加。如(假设被乘数为2)

            第一组:2<<(5+1) – 2<<5 = 64

            第二组:2<<(3+1) – 2<<3 = 16

            第三组:2<<(1+1) – 2<<0 = 6

            相加得到86

      2.4. 对结果取模。

 

Dividision                           

  对于除法实质上就是通过移位操作和加、减法组合而成,且根据除数是否为2的n次幂区别处理。

  1. 对于被除数为2的n次幂的情况,除法公式为:a>>n,如6/4等价于6/(2^2),则可转换为移位操作6>>2即可。然后再对结果取模。

  2. 对于被除数不为2的n次幂的情况,则情况复杂不少。运算步骤如下:(实质上我们就是按这个步骤做十进制除法的)

      2.1. 高位对齐,在除数值小于被除数值的前提下,让除数的位数等于被除数;若执行高位对齐后,除数值大于被除数时,则除数右移一位。得到位移数。

      2.2. 试商,除数-被除数*N = 余数中间值 ,其中N*被除数 <= 除数 && (N+1)*被除数 > 除数。商 = 商 + N * 基数^位移数。

      2.3. 循环执行上述步骤,直到无需再执行高位对齐,那么2.2中得到的余数中间值将作为除法运算的最终余数,否则余数中间值则作为一下轮高位对齐的被除数处理。

  以下是C的实现:

#include <stdio.h>

// 前置条件
const unsigned short lowest_bit_weight = 1; // 二进制最低位的位权重

int main(){
  // 输入
  unsigned short dividend = 14, divisor = 5;
 
  // 输出
  unsigned short quotients = 0,  //
                 rem = 0;        // 余数

  // 中间值
  unsigned short highest_bit_weight,
         divisor_aligned,
         tmp_dividend = dividend;
  unsigned short high_alignment;

  // 开始运算
  while (1){
      // 高位对齐 (从高位开始运算)
      // 结果:1. 要么被除数的最高位小于除数的最高位;
      //       2. 要么被除数的最高位对齐除数的最高位, 且被除数大于除数;
      high_alignment = 0;
      highest_bit_weight = lowest_bit_weight;
      divisor_aligned = divisor;
      while (tmp_dividend >= divisor_aligned){
        divisor_aligned = divisor_aligned << 1;
        highest_bit_weight = highest_bit_weight << 1;

        high_alignment += 1;
      }
      if (high_alignment > 0){
        divisor_aligned = divisor_aligned >> 1;
        highest_bit_weight = highest_bit_weight >> 1;
        high_alignment -= 1;
      }

      // 当无需执行高位对齐时,则将下一轮的被除数作为余数,并且结束运算
      if (0 == high_alignment) {
        rem = tmp_dividend;
        break;
      }

      // 上一轮运算的商加上最高位权重得到当前运算的商值
      quotients = quotients | highest_bit_weight;
      // 被除数减除数的差值作下一轮的被除数
      tmp_dividend = tmp_dividend - divisor_aligned;
  }
  printf("%u/%u=%u(rem:%u)\n", dividend, divisor, quotients, rem);
  return 0;
}

 

Conclusion                          

  尊重原创,转载请注明来自:http://www.cnblogs.com/fsjohnhuang/p/5078290.html 肥子John^_^

Thanks                            

  《深入理解计算机系统》

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168155.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 深度相机种类_深度相机原理

    深度相机种类_深度相机原理本文首发于微信公众号:计算机视觉life。本文的深度相机制造商涉及:Microsoft、Intel、LeapMotion、Orbbec、图漾、OccipitalStructure、Stereolabs、DUO。文末附深度相机详细对比清单。MicrosoftKinect微软推出了两款Kinect,Kinect一代(Kinectv1)是基于结构光原理的深度相机,Kinect二代(Kine

    2022年10月30日
  • linux nohup命令输出日志_nohup运行sh文件

    linux nohup命令输出日志_nohup运行sh文件(一)前言因为经常使用Xshell进行服务器代码的运行,但是每次到关机后,或者是关掉Xshell连接窗口,在服务器上的命令,操作也就断掉了。这不得不找到了一个Linux命令:nohup(二)基本用法nohupcommand[arg…][&amp;]拿pythontest.py为例子一般我们运行命令是直接:pythontest.py,但是在xshel…

  • vbs代码之“电脑系统崩溃”「建议收藏」

    vbs代码之“电脑系统崩溃”「建议收藏」熟练掌握vbs脚本,可以让你…我也不知道。具体操作:新建文本文档,将本段代码复制进入文本,保存;将后缀.txt改为.vbs即可。codeCreateObject(“SAPI.SpVoice”).Speak”你的电脑受到ddos木马攻击,系统严重瘫痪,电脑系统将在三秒后崩溃”setWshShell=WScript.CreateObject(“WScript.Shell”)WScript.Sleep2000CreateObject(“SAPI.SpVoice”).Speak”电脑系统已

  • 一个程序员的蜕变(我是如何成为架构师的)

    一个程序员的蜕变(我是如何成为架构师的)

  • 培根密码加解密_二进制密码在线解密

    培根密码加解密_二进制密码在线解密0x00介绍培根密码实际上就是一种替换密码,根据所给表一一对应转换即可加密解密它的特殊之处在于:可以通过不明显的特征来隐藏密码信息,比如大小写、正斜体等,只要两个不同的属性,密码即可隐藏0x01代码实现脚本很简单,就是建立对应关系,对密文,或者明文进行相应的替换即可需要注意的是输入的都应该是全小写字母或全大写字母,在脚本里也有说明python脚本如下:#…

    2022年10月25日
  • UFW 修改before.rules等文件时reload无效

    UFW 修改before.rules等文件时reload无效

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号