专栏首页偏前端工程师的驿站基础野:细说有符号整数

基础野:细说有符号整数

Breif                              

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

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

Encode                              

  有符号整数可表示正整数、0和负整数值。其二进制编码方式包含 符号位 和 真值域。

  我们以8bit的存储空间为例,最左1bit为符号位,而其余7bit为真值域,因此可表示的数值范围是{-128,...,127},对应的二进制补码编码是{10000000,...,01111111}。

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

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

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

  3. C语言中虽然没有规定必须采用补码来对有符号数进行编码,但大部分实现均是采用补码。而Java和C#则明确规定采用补码来表示有符号数。

Sign-extended                        

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

  例如现在我们要将8bit的10000100扩展为16bit,那么我们只要将高8bit设置为与原来符号位相同的值(这里是1)即得到1111111110000100,而其数值和符号并不产生变化。

Truncation                          

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

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

Addition                            

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

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

  1. 算术加法(由于采用补码对有符号数进行编码,则是已经将负数转换为正数存储,所以含负数的加法只需要直接执行算术加法即可);

  2. 执行截断操作。

  示例1,两个4bit的有符号数相加(3+6):

  0011

+0110

  1001,然后执行截断得到1001,发生正溢出得到 -7

  示例2, 两个4bit的有符号数相加(-3+6):

        1101

+0110

       10011,然后执行截断得到0011,发生正溢出得到 3

Subtraction                          

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

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

  2. 算术加法;

  3. 执行截断操作。

  示例1,两个4bit的有符号数相减(-5-6):

 1011

-0110

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

  1011

+1010

 10101,然后执行截断得到0101,发生负溢出得到5

   示例2,两个4bit的有符号数相减(-5-(-6)):

 1011

-1010

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

  1011

+0110

 10001,然后执行截断得到0001,得到1

Multiplication                         

  对于乘法实质上就是通过移位操作和加、减法组合而成。

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

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

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

            第一组:(1111)<<(3+1) - (1111)<<3 = 0000 - 1000 = 0000 + 1000 = 1000

            第二组:(1111)<<(1+1) - (1111)<<0 = 1100 - 1111 = 1100 + 0001 = 1101

            两组相加:1000 + 1101 = 10101,截断得到0101,等于十进制数值5.

      2.4. 对结果取模。

Division                            

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

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

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

   2.1. 对负数取补,提取符号乘积。

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

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

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

      2.5. 符号乘积乘以商得到最终商,符号乘积乘以余数得到最终余数。

 C语言实现:

#include <stdio.h>

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

int main(){
  // 输入
  char dividend = -5, divisor = -2;
 
  // 输出
  char quotients = 0,  // 商
    rem = 0;        // 余数

  // 中间值
  char highest_bit_weight,
       divisor_aligned,
       tmp_dividend = dividend,
       tmp_divisor = divisor;
  char high_alignment;
  char sign,
       sign1 = 1,
       sign2 = 1;
 
  // 负数转换为正数, 求符号乘积
  if (tmp_dividend < 0){
    tmp_dividend = ~tmp_dividend;
    tmp_dividend += 1;
    sign1 = ~sign1;
    sign1 += 1;
  }
  if (tmp_divisor < 0){
    tmp_divisor = ~tmp_divisor;
    tmp_divisor += 1;
    sign2 = ~sign2;
    sign2 += 1;
  }
  sign = sign1 * sign2; 


  // 开始运算
  while (1){
      // 高位对齐 (从高位开始运算)
      // 结果:1. 要么被除数的最高位小于除数的最高位;
      //       2. 要么被除数的最高位对齐除数的最高位, 且被除数大于除数;
          high_alignment = 0;
          highest_bit_weight = lowest_bit_weight;
      divisor_aligned = tmp_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("%d/%d=%d(rem:%d)\n", dividend, divisor, quotients * sign, rem * sign);
  return 0;
}

Convert Unsigned 2 Signed, and Convert Signed 2 Unsigned 

  无符号数与有符号数间转换采取的是位级表示(位模式)不变,解析方式变化引起最终所表示的值变化。

  例如:无符号数15的4bit位模式为1111,强制转换为有符号数时其位模式依然是1111,但实际表示的值则变为-1。

  无符号数转换为有符号数的公式 U2Tw(x) = x - xw-1*2w,其中w表示位数,x表示无符号数的十进制值,x表示无符号数的二进制位模式。

  有符号数转换为无符号数的公式 T2Uw(x) = x + xw-1*2w,其中w表示位数,x表示无符号数的十进制值,x表示无符号数的二进制位模式。

  注意:在C语言中若参与运算的两运算数分别是有符号数和无符号数,那么会隐式将有符号数转换为无符号数后再进行运算。

Conclusion                            

 尊重原创,转载请注明

Thanks                              

 《深入理解计算机系统》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

推荐阅读

  • 远程办公经验为0,如何将日常工作平滑过度到线上?

    我是一名创业者,我的公司(深圳市友浩达科技有限公司)在2018年8月8日开始运营,现在还属于微型公司。这个春节假期,我一直十分关注疫情动向,也非常关心其对公司带来的影响。

    TVP官方团队
    TAPD 敏捷项目管理腾讯乐享企业邮箱企业编程算法
  • 数据中台,概念炒作还是另有奇效? | TVP思享

    作者简介:史凯,花名凯哥,腾讯云最具价值专家TVP,ThoughtWorks数据智能业务总经理。投身于企业数字化转型工作近20年。2000年初,在IBM 研发企业级中间件,接着加入埃森哲,为大型企业提供信息化架构规划,设计,ERP,云平台,数据仓库构建等技术咨询实施服务,随后在EMC负责企业应用转型业务,为企业提供云迁移,应用现代化服务。现在专注于企业智能化转型领域,是数据驱动的数字化转型的行业布道者,数据中台的推广者,精益数据创新体系的创始人,2019年荣获全球Data IQ 100人的数据赋能者称号,创业邦卓越生态聚合赋能官TOP 5。2019年度数字化转型专家奖。打造了行业第一个数据创新的数字化转型卡牌和工作坊。创建了精益数据创新方法论体系构建数据驱动的智能企业,并在多个企业验证成功,正在向国内外推广。

    TVP官方团队
    大数据数据分析企业
  • 扩展 Kubernetes 之 CRI

    使用 cri-containerd 的调用流程更为简洁, 省去了上面的调用流程的 1,2 两步

    王磊-AI基础
    Kubernetes
  • 扩展 Kubernetes 之 Kubectl Plugin

    kubectl 功能非常强大, 常见的命令使用方式可以参考 kubectl --help,或者这篇文章

    王磊-AI基础
    Kubernetes
  • 多种登录方式定量性能测试方案

    最近接到到一个测试任务,某服务提供了两种登录方式:1、账号密码登录;2、手机号+验证码登录。要对这两种登录按照一定的比例进行压测。

    八音弦
    测试服务 WeTest
  • 线程安全类在性能测试中应用

    首先验证接口参数签名是否正确,然后加锁去判断订单信息和状态,处理用户增添VIP时间事务,成功之后释放锁。锁是针对用户和订单的分布式锁,使用方案是用的redis。

    八音弦
    安全编程算法
  • 使用CDN(jsdelivr) 优化博客访问速度

    PS: 此篇文章适用于 使用 Github pages 或者 coding pages 的朋友,其他博客也类似.

    IFONLY@CUIT
    CDNGitGitHub开源
  • 扩展 Kubernetes 之 CNI

    Network Configuration 是 CNI 输入参数中最重要当部分, 可以存储在磁盘上

    王磊-AI基础
    Kubernetes
  • 聚焦【技术应变力】云加社区沙龙online重磅上线!

    云加社区结合特殊时期热点,挑选备受关注的音视频流量暴增、线下业务快速转线上、紧急上线防疫IoT应用等话题,邀请众多业界专家,为大家提供连续十一天的干货分享。从视野、预判、应对等多角度,帮助大家全面提升「技术应变力」!

    腾小云
  • 京东购物小程序购物车性能优化实践

    它是小程序开发工具内置的一个可视化监控工具,能够在 OS 级别上实时记录系统资源的使用情况。

    WecTeam
    渲染JavaScripthttps网络安全缓存

扫码关注云+社区

领取腾讯云代金券