基础野:细说无符号整数

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                          

  尊重原创,转载请注明

Thanks                            

  《深入理解计算机系统》

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Albert陈凯

技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构 在线练习 Le...

34750
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

38720
来自专栏糊一笑

关于一道面试题【字符串 '1 + (5 - 2) * 3',怎么算出结果为10,'eval'除外】

最近徘徊在找工作和继续留任的纠结之中,在朋友的怂恿下去参加了一次面试,最后一道题目是: 写一个函数,输入一个字符串的运算式,返回计算之后的结果。例如这样的: ...

589100
来自专栏GIS讲堂

geotools等值线生成

前文中,提到了等值面的生成,后面有人经常会问等值线的生成,本文在前文的基础上做了一点修改,完成了等值线的geotools生成。

38150
来自专栏章鱼的慢慢技术路

解密回文——栈

15930
来自专栏小詹同学

Leetcode打卡 | No.015 三数之和

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

15020
来自专栏Java帮帮-微信公众号-技术文章全总结

Java案例-数组随机数

五四青年节,是为纪念1919年5月4日爆发的五四运动而设立的。它来源于中国一九一九年反帝爱国的。1939年,陕甘宁边区西北青年救国联合会规定5月4日为中国青年节...

42380
来自专栏tkokof 的技术,小趣及杂念

sizeof 知多少?

稍熟悉C/C++的朋友,对于sizeof肯定不陌生,通过他我们可以知晓某个类型或者实例的内存大小(以字节计),但是如果深入一下sizeof计算的细节,想来大部分...

8100
来自专栏二进制文集

LeetCode 004 Median of Two Sorted Arrays 详细分析

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

13310
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

33950

扫码关注云+社区

领取腾讯云代金券