二进制表示和运算

标签：CSAPP, 操作系统

1. 二进制乘法优化

整数乘法指令的速度相对较慢：大多数机器上，整数乘法指令相对较慢，需要10个或更多的时钟周期，而其他整数操作（如加法、减法、位级操作和移位）只需要1个时钟周期。
移位和加法：当乘以2的幂时，可以通过简单地将数字向左移位来实现乘法。例如，乘以4等同于向左移动两位。这种方法也可以扩展到更复杂的乘法，通过将乘法分解为多个移位和加法操作。
卡拉次乘法（Karatsuba算法）：这是一种分治算法，用于加速大数的乘法。它将大数分解为较小的部分，递归地应用乘法，然后组合结果。这种方法比传统的长乘法更快，特别是对于非常大的数字。
快速傅里叶变换（FFT）：FFT可以用于加速大数的乘法，特别是在数字信号处理中。通过在频域中执行乘法，然后将结果转换回时域，可以实现比传统方法更快的乘法。
表查找和预计算：对于固定的乘数，可以预先计算可能的乘积并存储在表中。这样，乘法就可以通过查找表来快速完成，而不是执行实际的乘法操作。
硬件加速：在某些系统中，可以使用专用的硬件乘法器来加速乘法操作。这些硬件乘法器通常比软件实现更快，更高效。
逼近和截断：在某些应用中，可以接受近似结果。通过逼近乘数或截断中间结果，可以减少所需的计算量。
并行处理：在多核处理器或GPU上，可以并行执行多个乘法操作，从而加速整体计算过程。

2. 二进制除法优化

除了和乘法类似的，移位运算、查表，硬件，并行，近似之外，还有一些其他方法
逆序乘法：这种方法涉及计算除数的逆（或倒数），然后将被除数乘以这个逆。这在除数是固定的情况下特别有用，因为可以预先计算并存储逆。然后，除法可以通过一次乘法和可能的一些调整来完成。
SRT除法：以其发明者Sweeney, Robertson和Tocher命名，这种算法允许在每个步骤中选择多个可能的商，从而加速除法过程。

3. 二进制乘除法比较

二进制乘法：
- 基本的二进制乘法类似于小学数学中的长乘法，但是使用二进制数字。对于一个 n 位，一个 m 位的数字，这种方法的时间复杂度大约是 O(nm)。
- 每一步涉及乘以一个二进制位（0或1），然后将结果移位并累加。
二进制除法：
- 基本的二进制除法类似于长除法，但是使用二进制数字。对于 n 位的被除数和 m 位的除数，这种方法的时间复杂度大约是 O(nm)。
- 每一步涉及比较、减法和移位操作。
在不采用优化的情况下，二进制除法通常比二进制乘法更为复杂和耗时。这是因为除法涉及到更多的比较和条件判断，而乘法则相对直接。此外，除法的中间步骤可能更为复杂，尤其是当涉及到较大数字时。

4. 取整函数

round()：
- 正数：当小数部分大于或等于0.5时，向上取整到最接近的整数。
- 负数：当小数部分小于或等于-0.5时，向下取整到最接近的整数。
floor()：
- 正数：向下取整到最接近的整数，即小于或等于该数的最大整数。
- 负数：同样向下取整到最接近的整数。
ceil()：
- 正数：向上取整到最接近的整数，即大于或等于该数的最小整数。
- 负数：同样向上取整到最接近的整数。
trunc()：
- 正数和负数：直接去掉小数部分，只保留整数部分。

5. 浮点数和整数的运算区别

比较了浮点数和整数在二进制层面上进行加减乘除时的主要区别：

特性/操作	整数	浮点数
表示方式	直接表示数值，可以是二进制、十进制或十六进制等。	由符号位、指数部分和尾数部分组成，通常遵循IEEE 754标准。
加法/减法	直接对数值进行二进制加减。	需要先对齐指数，然后对尾数进行加减，可能需要规格化和舍入。
乘法	直接对数值进行二进制乘法。	尾数相乘，指数相加，可能需要规格化和舍入。
除法	直接对数值进行二进制除法。	尾数相除，指数相减，可能需要规格化和舍入。
精度	精度固定，取决于整数的位数。	精度有限，取决于尾数的位数，但可以表示非常大或非常小的数。
范围	有限的范围，取决于整数的位数。	非常广泛的范围，由于指数的存在可以表示非常大或非常小的数。
溢出处理	可能发生溢出，通常没有内置的处理机制。	溢出时可能产生无穷大或NaN（不是数字）。
特殊值	无特殊值。	可以表示无穷大、无穷小和NaN。

总结来说，整数运算在二进制层面上相对简单直接，而浮点数运算则更为复杂，涉及到对指数的处理、尾数的规格化和舍入等。