程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

数学专栏课外加餐(一) | 我们为什么需要反码和补码?

黄申 2018-12-24
你好,我是黄申。欢迎来到第一次课外加餐时间。
专栏已经更新了几讲,看到这么多人在留言区写下自己的疑惑和观点,我非常开心。很多同学在留言里提出了很多非常好的问题,所以我决定每隔一段时间,对留言里的疑问、有代表性的问题做个集中的解答,也是对我们主线内容做一个补充,希望对你有帮助。

什么是符号位?为什么要有符号位?

第 1 讲里,我介绍了十进制数转二进制数。这里面很多人对逻辑右移和算术右移中提到的符号位和补码有疑惑。这里面涉及了几个重要的概念,包括符号位、溢出、原码、反码和补码。我详细讲一下这几个点的来龙去脉。
首先我们来看,什么是符号位,为什么要有符号位?用一句话来概括就是,符号位是有符号二进制数中的最高位,我们需要它来表示负数。
在实际的硬件系统中,计算机 CPU 的运算器只实现了加法器,而没有实现减法器。那么计算机如何做减法呢?我们可以通过加上一个负数来达到这个目的。比如,3-2 可以看作 3+(-2)。因此,负数的表示对于计算机中的二进制减法至关重要。
那么,接下来的问题就是,如何让计算机理解哪些是正数,哪些是负数呢?为此,人们把二进制数分为有符号数(signed)和无符号数(unsigned)。
如果是有符号数,那么最高位就是符号位。当符号位为 0 时,表示该数值为正数;当符号位为 1 时,表示该数值为负数。例如一个 8 位的有符号位二进制数 10100010,最高位是 1,这就表示它是一个负数。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(94)

  • 老板来几袋面粉
    好复杂,开始慌了
    2018-12-24
    3
    51
  • 路阳
    为什么负数的补码等于反码加一
    1,基本概念(看看了解一下就好)

    计算机通过将最高位设置为符号位来表示正负数:
    符号位为1时,代表这个数为负数;符号位为0时,代表这个数为正数。

    为了方便理解,本文中的例子全部用4位二进制数举例

    原码:除符号位外的其他位,保存该二进制数的绝对值。
    例如 1:0001 -1:1001

    反码:正数的反码等于原码;
               负数的反码就是其原码除符号位外,按位取反。
    例如 1:0001 -1: 1110

    补码:正数的补码等于其原码
                负数的的补码等于反码加一
    例如 1:1001 -1:1111

    2,原码、补码
    原码、反码、补码都可以通过符号位非常方便的表示正负数,但是在进行加法计算时,原码和反码都存在这样或那样的问题:

    注: 计算机cpu的运算器只实现了加法器,而没有实现减法器,计算机是通过加上一个负数来做减法的

    原码:

    1 + 1 = 0001 + 0001 = 0010 = 2
    1 + -1 = 0001 + 1001 = 1010 = -2

    从上面的计算可以看出,原码无法通过加上一个负数来实现减法

    反码

    1 + -1 = 0001 + 1110 = 1111 = -0
    1 + -2 = 0001 + 1010 = 1011 = -4

    从上面的计算可以看出,反码也无法实现加上一个负数来实现减法

    原码和反码都不能解决的事情,只有通过寻找一种可以完美支持件“减法“的二进制数的表示方法来解决!

    3,补码
    一个4位的二进制数能表示的数是有限的,从 0000 ~ 1111 ,0000表示0,1111表示 - 1,最大值7(0111),最小值-8(1000)。

    看下面这组计算:


    0000 + 0001 = 0 + 1 = 0001 = 1
    0001 + 0001 = 1 + 1 = 0010 = 2
    0010 + 0001 = 2 + 1 = 0011 = 3
    ...
    0111 + 0001 = 7 + 1 = 1000 = -8
    1000 + 0001 = -8 + 1 = 1001 = -7
    1001 + 0001 = -7 + 1 = 1010 = -6
    ...
    1111 + 0001 = -1 + 1 = 0000 = 0
    0000 + 0001 = 0 + 1 = 0001 = 1


    0000 每次加上 0001 ;当最大值7 + 1时,正溢出,结果为最小值-8;最小值-8加上8后,又变成了0000,就像钟表一样,循环往复。

    比如说现在有一个数字2,我们想让它变成0,怎么办?
    有两种方法:
    1. 减去 2 个 1 即:0010 - 0010 = 0000
    2. 加上 14 个 1 即:0010 + 1110 = 0000

    我们可以总结出,当一个四位的二进制数abcd 减去 另一个四位的二进制数 efgh : abcd - efgh = abcd + (1111 + 1 - efgh) 。

    efgh 和 (1111 + 1 - efgh) 对模 (1111 + 1)同余。

    如果不太理解,就可以想象一个钟表的时针停在10点的位置,如果想让时针停在8点的位置,可以逆时针的旋转2个刻度,也可以顺时针的旋转10个刻度。

    通过公式abcd - efgh = abcd + (1111 + 1 - efgh) ,我们可以得出,如果计算机使用(1111 + 1 -efgh)来表示 -(efgh) ,就可以解决减法的问题。这就是我们补码的原理。

    由于1111 - efgh 等于 efgh 的反码 ,所以 efgh 的补码等于 efgh的反码加上1。

    2019-01-02
    50
  • 梓航(﹏)
    老师,你讲的那个取模和反码的关系那一段我看不懂,之前看书也没有遇到你说的这种概念,请问还有其他学习资料吗?

    作者回复: 其他的材料一般都没有将“为什么”这么算说清楚,我画了张图,你结合图来理解。简单的说,你可以认为a-b的减法就是给a加上一个特别大的数,导致溢出,然后剩下的反而比a小,这就达到了减法的目的

    2018-12-24
    19
  • 石佳佳_Gemtra
    思考题:
    原码:10100010
    对补码除符号位取反得
    反码:11011101
    +1操作得
    补码:11011110
    对应十进制数:-94
    还有一种方法,把负数原码除符号位外求和,减去 (2^n-1+1),即 2+32-(2^7-1+1)=-94

    作者回复: 是的

    2018-12-24
    1
    16
  • 风轨
    思考题
    0b10100010 = 0b10000000 + 0b00100010
    其中
    0b10000000 = -128
    0b00100010 = 34
    所以答案是 -94

    2进制取相反数公式
    相反数 = 原数减一再取反

    - 0b10100010 = !(0b10100010-1) = 0b01011110 = 94

    作者回复: 是的

    2018-12-24
    10
  • 祝军
    用大家熟悉的一周七天进行对比吧
    1、计算数据的溢出相当于模:假设第1天为周一,第2天为周二,以此类推第7天为周日,第8天已经大于7溢出了,8对7进行取模为1,也即第八天为周一;取模的除数为上限减去下限+1,替换过来换算:一周的上限为7,下限为1,那一周取模的除数换算为:7-1+1,所以我们想要知道第15天后是周几直接对(7-1+1)取模即可;
    2、i-j=(i-j)+(2^n-1+1)=i+(2^n-1-j),可以换算为 周一 = (周一)+ (7-1+1)进行理解(ps:不一定周一,周几都为同一样,只是将 i-j 看成一个单元用其做概念上的替换)

    作者回复: 是的

    2019-04-12
    6
  • 二十八画生
    本文重要的是说清了补码的由来,为啥这样定义补码
    2019-01-02
    5
  • 彩色的沙漠
    老师,不好意思
    问题有一处错误,我纠正一下,以免误导后来的同学
    java中int的最小值是-2^31
    二进制源码:1 000 0000 0000 0000 0000 0000 0000 0000
    二进制反码:1 111 1111 1111 1111 1111 1111 1111 1111
    -2^31的补码还是自己,符号位进位舍弃

    作者回复: 是的👍

    2018-12-26
    5
  • 彩色的沙漠
    老师您好
    1、文中提到的"对于 n 位的数字类型,符号位是 1,后面 n-1 位全是 0,我们把这种情形表示为 -2^n ,而不是 2^n。"
    第一小问为什么不是-2^(n-1)而是你说的-2^n
    第二小问是不是应该这样描述"对于 n 位的数字类型,符号位是 1,后面 n-1 位全是 0,我们把这种情形表示为-2^(n-1),而不是2^(n-1)"更合适?这个问题依赖第一小问的答案
    2、java中int的最小值是-2^63
    二进制源码:1 000 0000 0000 0000 0000 0000 0000 0000
    二进制反码:1 111 1111 1111 1111 1111 1111 1111 1111
    那他的补码怎么表示 反码+1
    感谢老师的解答!

    作者回复: 第一处有个笔误,我的原意是-2^(n-1),而不是2^n

    第二个问题很好 -2^63的补码还是它自己,符号位进位舍弃

    2018-12-26
    3
  • 吉祥
    以为是-34呢😂
    2018-12-24
    3
  • mickey
    1010 0010
    除符号位取反 -> 1101 1101
    加1 -> 1101 1110
    转十进制 -> -94
    2018-12-24
    3
  • 爱吃锅巴的沐泡
    老师,请教一下问题
    文章中讲的是原码到补码的推导过程。
    一个二进制数在计算机中存储的形式就是补码。
    那么一个数输入到计算机中就是补码形式,还是说有一个从原码到补码的推导过程?可是这个推导过程中也有减法,和补码把减法加法化的说法就冲突了?

    作者回复: 计算机存储的就是补码,这个推导过程是便于人的理解

    2019-06-26
    2
  • 补码代码的数值的快速求法
    负数补码通过非符号位0出现的位置来计算,然后计算结果加1,最后带上符号即可。
    比如 1000,非符号位为000,按照0出现的位置计算,000=2^2+2^1+2^0=4+2+1=7,结果加上1后得到8,所以这个二进制数
    表示-8
    正数补码看非符号位1出现的位置来计算,然后加上符号即可。
    比如 0111,非符号位为111,按照1出现的位置计算,111=4+2+1=7 所以这个二进制数
    表示+7

    对补码的理解:
    目的:为了使用相同电路来实现加减运算,使得计算机cpu设计更加容易
    为何用补码,可以通过如下四位数模拟补码从0开始一直加1的情况
    0000 = 0
    0001 = 1
    0010 = 2
    0011 = 3
    0100 = 4
    0101 = 5
    0110 = 6
    0111 = 7
    1000 = -8
    1001 = -7
    1010 = -6
    1011 = -5
    1100 = -4
    1101 = -3
    1110 = -2
    1111 = -1
    0000 = 0 (再加1又从0开始了,上面表示的不同数值的个数是2^4=16,所以模是16)
    ...
    然后上溢和下溢也顺便理解了,如下所示,
    上溢就是4位二进制数的正数的最大值加1,然后通过补码加法运算后结果是4位二进制数的最小数-8
    上溢:7 + 1 =0111+0001=1000(4位二进制数的最小数)=-8 注:加上1的目的是最大值再大一点,当然就溢出了
    下溢就是4位二进制数的负数的最小值加-1,然后通过补码加法运算后结果是4位二进制数的最大数+7
    下溢:-8+(-1)=1000+1111=0111(最大数)=7 注:加上-1的目的是最小值再小一点,当然就溢出了

    作者回复: 很详细的解释

    2019-06-18
    2
  • Rainbow
    “其中 2^n-1 的二进制码在不考虑符号位的情况下是 n-1位的1“
    这个地方不理解,2^n-1的符号位不是0吗?
    而2^n - 1是有位的1啊。
    这个地方不理解,希望老师能解答一下~

    作者回复: 对于有符号的数据类型,2^n-1是n位1,但是第一个是符号位,所以符号位是1

    2018-12-27
    2
  • 吾本糊涂
    10100010直接用10进制表示不是-34吗 为啥要去它的补码再换算10进制?

    作者回复: 负数在计算机中用补码表示,你可以先算算-34的补码是多少

    2018-12-25
    2
  • 毕明亮
    老师,评论里石佳佳说那个是源码取反加一,Li Shundong又说是补码取反加一得源码……看晕了

    作者回复: 其实两者是可以这样互换的,这样思考可能更简单一点:(2^n-1-j原+1)=j补,那么j原和j补分别移到等号的另一边,就是(2^n-1-j补+1)=j原,2^n-1-j补就是去j补码的反码,然后+1就是j原码

    2018-12-24
    2
  • 阿猫
    负数换算补码时,+1,符号位参与运算吗?听晕了。。。

    作者回复: 符号位不参与

    2018-12-24
    2
  • chengzise
    计算机内部有符号数才用补码表示,10100010最高位为1是个负数,负数的绝对值是其补码取反再加1,为01011110。十进制为94.因此10100010的十进制值为-94

    作者回复: 是的👍

    2018-12-24
    2
  • zj
    2^n-1-2这个图解中,为什么是n-1个1呢,不考虑符号位的话应该是n个1吧

    作者回复: 要考虑符号位

    2019-06-26
    1
  • Temme
    思考题:10100010
    如果是原码,所对应的数字就是-34
    如果是补码,那么就减一取反求原码,11011110,就是-94。

    然而对着补码再去求一次补码也可以得出原码,所以神奇的是某个回答也是对的。。。这就是所谓的互为补码。

    作者回复: 对的,负负得正的原理

    2019-06-19
    1
收起评论
94
返回
顶部