基础野:细说无符号整数

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 条评论
登录 后参与评论

相关文章

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

Java案例-数组随机数

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

3638
来自专栏calmound

图的着色

图着色问题,相邻的点颜色不同       基础知识:http://wenku.baidu.com/view/d7242fd1c1c708a1284a444d.h...

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

解密回文——栈

1363
来自专栏二进制文集

LeetCode 004 Median of Two Sorted Arrays 详细分析

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

861
来自专栏Albert陈凯

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

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

3105
来自专栏数说工作室

【SAS Says】基础篇:5. 开发数据(一)

本节目录: 开发数据 5.1 创建并重新定义变量 5.2 使用SAS函数 5.3 使用IF-THEN语句 5.4 用IF-THEN语句将观测值分组 5.5 构造...

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

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

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

2835
来自专栏前端杂谈

前端算法-基本排序算法比较

36213
来自专栏菜鸟前端工程师

JavaScript学习笔记005-运算符

862
来自专栏xiaoxi666的专栏

【模板小程序】十进制大数除法(输出商和余数)

大数除法,应该算是四则运算里面最难的一种了。不同于一般的模拟,除法操作步数模仿手工除法,而是利用减法操作实现的。

1402

扫码关注云+社区