做leetcode的时候刷到了浮点数计算相关的问题，特在此记录一下相关知识

直观形式的小数二进制表示

十进制的3.5 表示为二进制数为 0000 0011.1000 0000
即2^1 + 2^0 + 2^(-1) = 3.5

二进制小数的精度丢失

二进制小数部分本质上是【2的负数幂的和】
如十进制0.75 = 0.5 + 0.25 = 2^(-1) + 2^(-2) = .1100 0000(二进制)
而2的负数幂的和是无法表示所有(0,1)内的数的，如十进制0.2就无法使用有限个2的负数幂的和来表示
类似地，十进制0.2也无法使用三进制小数、四进制小数实现准确表示

正是因为小数在不同进制下可能无法有限地表示，而计算机往往只能使用有限的位数进行表示，因此小数的进制变换就可能产生精读丢失问题

计算机的小数表示

计算机内小数以定点数和浮点数两种方式存储

定点数局限较大，顾名思义，定点数使用固定长度的bit分别存储整数部分和小数部分，如我可以定义无符号32位定点数高16位存整数部分，低16位存小数部分，小数点的位置是死的，因而叫定点数

浮点数的表示方法借鉴了科学计数法。十进制有科学计数法，二进制也有
如0000 0011.1000 0000 就可以表示为1.11 * 2^1(乘以2^1等同于小数点右移一位)

IEEE 754规定，任意一个二进制浮点数可以表示成
V = (-1)^s x M x 2^E

其中，

• s表示sign符号位，取0为正，取一为负
• M表示有效数字，并约定1 <= M < 2。由于M总是在1和2之间，即M总是1.xxx的形式，我们把1去掉，只记录小数部分，节省存储空间
• E是无符号整数，表示阶码

因此，浮点数只需要存储s、M和E，然后通过公式计算得到真实数值V
浮点数的M本质上是一个定点数，但配合阶码E能够实现对M的小数点位置的左右移动，这就是叫浮点数的原因

单/双精度浮点数

单精度浮点数占4字节共32bit，s占1bit，E占8bit，M占23bit，即可以保存小数点后23位二进制数字，精度为2^(-23)
双精度浮点数占8字节共64bit，s占1bit，E占11bit，M占52bit，即可以保存小数点后52位二进制数字，精度为2^(-52)

关于浮点数的阶码E

以单精度浮点数为例，阶码E占一个字节，可以表示无符号数0-255。全0和全1被保留用作特殊情况，因此可表示范围为1-254
但事实上，阶码既可以是正数，也可以是负数。IEEE 754通过移码实现了这一目的：

真实的指数 = 阶码M - 127
即当2的指数存入阶码位时，需要偏移127。这样，1-254范围的阶码实际上表示的是-126 至 127 的真实值
说白了就是个简单的值偏移

思考：

要实现阶码表示负数的目的，为什么不直接用补码，而是用移码呢？
如果使用补码，那么8bit的空间可以表示的范围是-128至127，完全可以满足需求啊，为啥要使用补码呢？
个人理解，这里面主要有2个点：

• 使用补码不能直接反映阶码的大小关系，而使用移码可以直接反应大小关系。在对阶码进行比较时，如果使用补码，就不能直接比较，因为补码是不能直接比较的。例如-1的补码是1111 1111，1的补码是0000 0001，直接比较的话计算机会认为前者较大，这是不对的；计算机还得先把它们化成原码，再对其进行比较，比较繁琐
• 使用移码能够无缝兼容补码的存储和运算法则。我们知道，移码规则下，真实的指数 = 阶码M - 127，阶码M范围1-254，为正整数，127也是正整数，正整数的补码是其自身，两个正整数相减就是其补码相减，得到的值就是补码形式的差
  如126 - 127 = 0111 1110 - 0111 1111 = 1111 1111，而1111 1111就是-1的补码
  因此，对真实指数的计算完全符合补码体系

浮点数的运算

根本思想：通过阶码对齐将浮点数计算转化为定点数计算

以最基础的加法为例
两个浮点数相加，首先需要对阶，也就是把2个浮点数的E一致化，一致化后就可以直接进行位的加操作
对阶的原则是【小阶对其大阶】
例如，0.2 = 1.100110011001100... * 2^(-3)，0.4 = 1.100110011001100... * 2^(-2)

十进制值	s	E	M
0.2	0	0111 1100	(1)10011001100110011001100
0.4	0	0111 1101	(1)10011001100110011001100

注：M的括号内的值表示缺省的整数部分

0.2的E要对齐0.4的E，同时，0.2的M要由移一位以对冲解码对齐的影响。如下

十进制值	s	E	M
0.2	0	0111 1101	(0)11001100110011001100110
0.4	0	0111 1101	(1)10011001100110011001100

阶码对齐之后，加法运算只和M有关，浮点数的运算转换成了常规的定点数运算
详情可以参考https://zhuanlan.zhihu.com/p/28162086

如何保证浮点数计算的精度呢

基于浮点数的存储机制，一旦产生浮点数，是必然躲不掉精度丢失的
因此，为了保证精度，就需要尽量避免产生浮点数
我们可以自行模拟乘除法的运算过程而不是直接使用浮点数乘除法，来避免精度丢失

leetcode 166. 分数到小数

这一题，如果直接把numerator和denominator转成浮点数然后直接除，必然会丢失精度，不能正确解答
实际上，应该自行模拟整数除法，不断更新被除数numerator，如果被除数numerator重复出现，则说明存在循环节

golang解答如下

import (
    "strconv"
    "fmt"
)
func fractionToDecimal(numerator int, denominator int) string {
    // 统一为非负数处理
    signFlag := ""
    if numerator > 0 && denominator < 0 { // 异号
        signFlag = "-"
        denominator = -denominator
    } else if numerator < 0 && denominator > 0 {
        signFlag = "-"
        numerator = -numerator
    }else if numerator < 0 && denominator < 0 {
        numerator = -numerator
        denominator = -denominator
    }

    // 总的思路：使用整数除法法则来运算小数除法。当计算小数部分时，如果numerator重复，则说明存在循环节
    var numeratorMap = map[int]int{} // 记录numerator首次出现的下标
    var zhengshuPart string // 整数部分
    var xiaoshuPart string // 小数部分
    for numerator != 0 {
        // 整数部分
        if numerator >= denominator {
            ans := numerator / denominator
            m := numerator % denominator
            zhengshuPart = zhengshuPart + strconv.Itoa(ans)
            numerator = m 
        } else {
            // 小数部分
            index, has := numeratorMap[numerator]
            if !has {
                numeratorMap[numerator] = len(xiaoshuPart)
                ans := numerator * 10 / denominator
                m := numerator * 10 % denominator
                xiaoshuPart = xiaoshuPart + strconv.Itoa(ans)
                numerator = m 
            } else {
                // numerator重复，说明循环节从xiaoshuPart[index]处出现
                xiaoshuPart = xiaoshuPart[:index] + "(" +xiaoshuPart[index:] + ")"
                break
            }
        }
    }
    // 处理返回值：整数部分和小数部分拼接
    if zhengshuPart == "" {
        zhengshuPart = "0"
    }
    if xiaoshuPart == ""{
        return signFlag + zhengshuPart
    }
    return signFlag + zhengshuPart + "." + xiaoshuPart
}