I/O Over

I'm flipping, I'm folding;

整数补充

上一篇文章漏了一部分。

首先是舍入,无符号整数除法的舍入是 floor ,也就是向下取整。而有符号整数实际上是向零取整,也就是说正数向下,负数向上。

除以二的幂如果用右移操作的话,因为在位层面上负数是正数加上偏置值而成的,所以和正数一样是向下取整的,为了向上取整,可以根据位移量算出一个偏置量,使得无需舍入的数在加上偏置量以后,偏置量影响的位直接被移走,什么都不影响。而需要进位的数,偏置量会让这个负数进一,所以最终实现向上取整。

不过用右移操作的除法,除数必须是二的幂。所以相比左移乘法,右移除法就没那么泛用了。不过在写二分查找的时候可以用到,以避免溢出。

浮点数

二进制小数

二进制小数可以理解成在实数范围内的二分查找逼近的过程。

IEEE 浮点数

  符号 阶码 小数 阶码偏置 非规格阶码
Float (32) 1 8 23 127 -126
Double (64) 1 11 52 1023 -1022

阅读更多

毒奶如果要正式地说的话可以叫做「反向预言」,在我的印象中,毒奶是从不祥之兆演化而来的。

比如说现在被当作毒奶的马伯庸,实际上一开始是作为玩笑的不详梗,并没有多少类似黄旭东的毒奶举动,但是随着毒奶的概念流行还是常常和张召忠、黄旭东、孟德尔(md2)放在一起。在毒奶还没诞生的年代有类似的不祥之兆,比如说发改委调整油价和飞机坠落。

在这里我用在论坛上经常见到的孟德尔,和耳熟能详的黄旭东作为模式生物……哦不,样例来分析。

阅读更多

《深入理解计算机系统》第三版出了,重新看,这次仔细做习题,发现上次忽略了不少东西。

单纯的阅读笔记,标注一些重要的地方避免忘。

整数

有符号整数和无符号整数共用同一套指令,对于位数 $w$,无符号中 $ \geq 2^{w-1} $ 的数字都会被看作负数。原理是最高有效位看作负权值,实际的值是除去最高位后剩余的位所表示的值再减去有符号数中的最小数 $Min_w = -2^{w-1}$。

位数较小的有符号整数扩展到较大的,只需要在开头填充若干个符号位的值就行了,$1XX$ 和 $11XX$ 所表示的负数是相同的,因为 $-2^w + 2^{w-1}=-2^{w-1}$。

对无符号整数 $x$ 来说,总有一个数字 $-x$ 使得 $x+(-x)=0$,求法是 $ -x = 2^{w} - x $ 。

程序中的算法是 ~x+1 即对 x 按位取反然后 +1。这对有符号数也适用。

因为除了正数负数还有 0,所以有符号整数的区间是不对称的。$Min_w$ 就在正数上没有对应的数。它的位表示是 $100\dots00$ ,取反了以后还是自己。

char 类型 C 标准没有规定是否是有符号的,不过很多机器都是有符号的。

无符号整型和有符号整型之间的转换,方式是不改动位信息,直接重新解释。如果大小不同,先提升大小再转换。

int32_t a = 0xFFFF;
(uint64_t) a == (uint64_t)(int64_t)a == -1;
(int64_t)(uint64_t) a = 0x0000FFFF;

无符号整数和有符号整数在一起的表达式,C 会隐式提升有符号整数看作无符号整数,也就是说 -1 > 0U 为真,-1 转为无符号整数就变成 $Max_w$ 也就是最大的正数。所以注意类型小心混用。

阅读更多