【C】《整数的存储》

cyycoish

        在这里我打算和大家一起探讨整数的存储。
        既然是我的帖子我发言在先，如果大家觉得这个内容比较有趣的话请踊跃跟帖讨论。我开始啦。
一、一切为了搬家
        首先计算机中的整数必须是大小固定的——这个很好理解：我们可以有很多钱。但是你的一元硬币和我的大小几乎都是一样的。这一枚一元硬币的尺寸就好比一个整数的大小。如果我拿出一枚直径1m的一元硬币就会出现以下两种情况：

using 人类;
using 人类.代词.第一人称；
using 人类.代词.第二人称；

int main(int 时间, char ** 地点)
{
        人类 . 作者 我；
        人类 . 读者 你；
        if (你没想太多)
        {
                你 . 说（”这假币吧？”）；
                你 . 发送消息（拒收）；
                你 . 不信任度＋＋；
        }
        else
        {
                你 . 一元 . 交易（我 . 一元）；
                你 . 获取现在的面部表情（buffer）;
                if (Buffer == 滑稽)
                        print “交易成功”
                else
                        你 . 说 （“小气鬼！\n”）；
        }
        return 0;
}

        不同尺寸的硬币（整数）在交换时只会出现更复杂麻烦的情况。所以人们将整数的大小加以规定分类。
        然后就要讲到人们怎样对整数进行分类的啦。早就听说：计算机是只认识二进制的，所以整数归根结底都是用二进制表示的。——不对，而且我不喜欢这样子笼统粗略的观点。计算机可聪明啦谁说它只认识二进制？如果这样的话你的计算器APP显示的都是0和1了。我们只能说：在大部分计算机内整数用二进制表示，因为0，1可以表示为电子计算机内部电路最基本的两种状态。在我们人类的大脑中，信息都是以神经递质分子＋电信号传输、表示的。那么照这个逻辑我只能说：人类是只认识多巴胺、羟色胺……的。
        清楚了计算机不是只认识二进制，和为什么计算机要使用二进制以后我们用二进制对整数的长度加以分类：
        最简单的当然是一位整数了：1位（1 bit）整数只有一位。要么是0，要么是1。能不能同时是0又是1呢？绝对不能——你别给我整量子计算机那一套东西，再说了量子计算机在计算的时候也要将0与1确定下来。
        然后，我们规定还可以有8个位的整数。一个8位整数可以是 00000001 也可以是 11111111 还可以是 00101100……一共有 2^8 ＝ 256 种表示方法（就是256个整数）。随着机器处理能力的增加 我们又规定一个 8*2 ＝ 16位的整数，它可以表示 2^16 ＝ 65536个整数。还有 8*4 = 32，8*8 = 64位…… 这里引申出来3个问题：
        1.我好像听说8位整数叫做Byte。16位整数叫做Word。32位整数因为大小是两个Word，所以也叫Double Word 简称 DWORD（双字）。64位整数就是Qword（aka: Quad Word，四字）咯。至于128位整数却没人叫它 Octuple Word。
        是这样的：一开始设计制造一台计算机的时候必须确定计算机的处理“字长”。起初还有36 bits作为一个字的：https://en.wikipedia.org/wiki/36-bit 。但是后来IBM起头，Intel Microsoft 后起跟风，人们也就习惯了如上分法。我们可以从 Word 的本意：“字”上加以理解。Word本意是字，以前还从来没有特指一个16位整数的说法，更没有特指MS Office中某一款产品的说法。因为人们用计算机来处理的各种信息语言中单位是字，所以能放下一个字的整数就叫字。而不管你用36个位放还是用16个位放。而 Office Word 想必大家也知道是怎么回事了。本来很单纯，用的人多了，便也不单纯了。这样的字还有“日”……。不要觉得难为情，字是没有任何意义的，赋予它特定意义的是人。F＊ck在大多数情况下，不都是一个感叹词吗：What the f*ck？Wich f*uck word are you thinking about?
        2.为什么人们只规定8位，两个8位，四个8位……而不规定 三个8位＝24位之类的？
        因为：没有强迫症，怎么能学得好计算机嘛！（开玩笑）。2的n次方来表示整数长度仅仅是因为方便，对方便。如果有更加玄学的解释则会是：你看偶数（Even number）成双成对，才是一个真正的数。奇数（Odd Number）这种奇怪的东西怎么能用来表示整数嘛。24/8=3，你不要拿这么奇怪的东西给我看。
        3.我还听说一个8位整数能表示的范围是－128到＋127。一个16位整数能表示-32768到＋32767之间的整数？
        答：嗯，你知道的太多了。这样的话只能将剩下的机密也告诉你了。

cyycoish

二、突然发现需要好好装修
        如果说上一节讲的是珈百璃刚刚来到人间，怎样接触人类的话。那么这一节则会是珈百璃学习如何拯救苍生的开始。如果你放弃学下去的话……哎，又一个珈百璃堕落了。
        上回说到原来能表示0到255的 Byte，一下就能表示－128到＋127了。原来0～255共256个整数，现在0～127怎么变少了呀？诶？不对还有－128到0一共128个负数，再加127个整数和1个0，还是256个整数！计算机，你到底在整数里藏了什么不可告人的秘密？这事儿首先要从原来简简单单的二进制怎么变成如今这样难以捉摸的八进制、十进制、十六进制、乃至浮点数（小数）说起。我们来看一张映射表：
二进制 八进制 十进制 十六进制
         0           0            0            0
         1           1            1            1
       10           2            2            2
       11           3            3            3
     100           4            4            4
     101           5            5            5
     110           6            6            6
     111           7            7            7
   1000         10            8            8
   1001         11            9            9
   1010         12           10           A
   1011         13           11           B
   1100         14           12           C
   1101         15           13           D
   1110         16           14           E
   1111         17           15           F
10000         20           16          10
10001         21           17          11
10010         22           18          12
10011         23           19          13
10100         24           29          14
10101         25           30          15
       …         …          …          …
        用你大脑的神经网络快速做一下模式识别便会发现，这张表就是二进制、八进制、十进制、十六进制之间的转换函数。这种进制转换的映射的关系被以上列表展现出来了一小部分。在这里我不会去讲这其中的道理。要是还有什么不明白的话，你需要一本《组合数学》。学到群环域的时候，就是解决这个奇怪的函数映射的时候。如果我讲出来了那么上面好大的、32行的表格也就变成浪费网站存储资源的垃圾。这片帖子也就丧失了70%的趣味性和65%以上的读者。所以，作业还是不能让薇奈特代工啊……
        如果你在读以下这些文字之前看了组合数学，那么可喜可贺下面的文字变成了1+1.
        下面要谈的主题也就是1+1。我们来看看二进制的代数运算：
0+0=0；1+0=1；0+1=1；1+1=10；
0-0=0； 1-0=1； 0-1=-1；   1-1=0；
0*0=0；1*0=0；  0*1=0；   1*1=1；
        以上是最基本的运算法则。在组合数学中有这么一句话：如果一个集合在某运算下是一个群，那么它将满足封闭性、结合律。它将存在单位元素，存在逆元素。读懂了的你会发现这条定理的完美体现原来就在这儿啊。如果没去读，那么没关系你只需要将以上规则保存在自己大脑的数据库中便会知道下一节的内容了。

cyycoish

        在上一节中好端端的帖子被我写成了Brain F*ck的事情。 我保证下一节中的奥义不会太多了。来看看几个8位整数Byte吧：00000001表示十进制1。00000010表示十进制2。00000001+00000010就是十进制3咯。一直到11111111可以表示十进制255。还能表示更多的数字吗？不能啦。八个bit都用完了，却不能表示出负数。我们叫这种整数为无符号整数。在C语言中一个Byte的长度等于一个char类型变量的长度。如果在定义char类型变量之前加上unsigned 修饰符，比如 unsigned char c; 那么变量c就是一个长度或说大小为8个bit的无符号整数。c最小存放整数0。c能放下的最大整数是255。我偏要放个256！那下次就只能拿出来个0。因为256等于二进制 1 0000 0000，最高的一位1因为放不下而被扔了。
        什么？扔了！1: “老司机，不要丢下我啊，让我上车！” 在运算过程中发生越界而被抛弃的现象叫做溢出，其实溢出发生时，在抛弃多余的数据之前大多数CPU将标志寄存器的溢出标志位设置为有效：表示：“有个乘客拉下了啊……” 溢出有 Overflow（上溢）和 Underflow（下溢）之分。大致来说你买不上车顶的挂票就发生了上溢。后备箱塞不下你了就发生了下溢（这个下溢以后再说）。看来老司机不会丢下你，哪怕再派一辆车也会接上你。就怕新司机不仅会漏下乘客，有时候连车门都忘了关，爆了栈，翻了车。
        对于无符号整数还有一个特别有意思的运算：移位运算。我们来看看在飞驰的车厢里大家怎样开Party。对一个二进制无符号8位整数01000001左移一位，原数就变成了：10000010。于是原来的65变成了130，相当于乘了2。这时你可能会想！大好！我以后就这样算倍数是2的乘法。稍等！我们把8位无符号整数130再左移一位：10000010 << 1 = 00000100。说好的260呢！就这样溢出变成了4。同样8位无符号整数130右移3位，原来低位表示十进制2的1连后备箱也塞不下了，结果整个整数因为下溢变成了00010000，等于十进制16。无符号整数差不多是这样了。下面要说的是由队长带领的有符号整数。

cyycoish

        两个代表队进场啦！首先进场的是由0作为领队的整数127。除了0作为队长以外，剩下的是由清一色的1组成的127代表队昂首阔步地向我们走来！这时对面走来了-128代表队，这一队队长是1，队员都是胖乎乎身强力壮的0。打起来了，两支队伍打起来啦！一个CPU时钟单位之后，场上的形势大有变化！其间-128代表队队长1干掉了127队长0，真是一场最高位之间的战争！与此同时看似战斗能力较弱的瘦子127队的队员们杀掉了-128队所有的0。127队的7个1和-128队的队长会发生激烈冲突吗？啊嘞？它们一见如故哦！于是现在寄存器变成了11111111。全体队员一直讨论决定，改队名为“-1”。“-1”队万岁！
        刚才进行的正是两个有符号8位整数127和-128做加法运算时角斗场CPU中所发生的故事。我们来看看计算机的世界为何如此奇妙。我们规定有符号整数中该整数的MSB（Most Significant bit，最高有效位）作为符号位。而且符号位为0表示整数，符号位为1表示负数。那么01111111就是十进制＋127。但是负整数的表示方法却不是11111111表示十进制-127。这里需要引入补码。一个整数的补码就是将这个整数逐位取反后再加一的值。所谓逐位取反很容易理解，每一位上0变成1，1变成0。127的补码就是1000 0000 ＋ 1 ＝ 10000001 ＝ 十进制的-127。所以在计算机中一个整数的补码和原整数互为相反数。
        为什么要这么麻烦？因为这样做了以后我们就可以省去设计减法电路呀。试想一下不计算减法的情况下要计算8位整数 3-5 的差。那么首先 3-5 ＝ -2. 十进制3表示为二进制0000 0011，十进制5表示为二进制 0000 0101。3-5=3+（-5）。我们要计算5的相反数，就是8位5的补码。8位5的补码为：1111 1010+1＝1111 1011. 然后再加上3:
    1111 1011
＋0000 0011
—————
    1111 1110
最后这个 1111 1110 就表示-2。可以这样看-2: 我们知道-2的相反数是＋2。而8位-2的相反数等于其补码。1111 1110 的补码为 0000 0001 ＋ 1 ＝ 0000 0010 就是十进制的+2。
        如此这般计算机就可以不用设计单独的减法电路从而计算一定长度内所有整数的加减法啦。是计算机只会算加法嘛？不对，计算机太聪明了什么都会干。我们不如说是人太聪明了，人想让它做什么它就做什么。计算机真是个听话的女仆。但是再聪明的仆人也需要作为主人的你认真调教。否则你就得做它的仆人。换一句话，知其然又知其所以然，事半功倍。知其然而不知其所以然，事倍功半。再进一步：老司机开车，新司机被车开。除非你是个万年抖M＋病娇癌晚期否则不会轻易让一个机器调教你的。
        好了关于有符号整数我这个资深中二病还有一点问题要提：有符号整数做移位运算会和无符号整数一样吗？（其实我真正想说：将位移大法施在无符号整数上取得的效果是否和有符号整数相同？）我们计算一下：(char) 65 << 1 = ? 八位有符号十进制整数65表示为二进制 0100 0001， 左移1位后变成 1000 0010 。符号位变成了1一定是负数。到底是负几？我们计算一下它的相反数。结果原来是126 那么原数就是－126。这一左移不得了，正数能变成负数。我们再把－126左移1位。结果又变成了正数8。原理还是一样左移后溢出的部分被扔了，在右侧补零。位移有逻辑位移和算数位移之分。逻辑向左位移和算数向左位移处理有符号无符号整数的办法都一样：扔掉上溢整数，原数LSB（Least Significant Bit，最低有效位）后补相应个数的零。但是在做算术右位移时，如果该整数是一个有符号整数，且符号位为1（就是个负数）那么除了扔掉下溢的数字外要在高位MSB处补1。如果该整数是一个有符号整数，且符号位为0（一个正数）或者该数是一个无符号整数，那么扔掉下溢数字同时在高位MSB处补0。举例来说十进制-127也就是二进制1000 0001 算术右移7位结果等于 1111 1111。而 0100 0001 算术右移7位结果等于 0000 0000。如果位移位数超过了整数位数怎么办。比如0100 0001 右移9位（魔法施加过头，会有后遗症吗？）使用位移运算之前除了仔细阅读以上说明按时按量服用外，位移运算本身的副作用是很小的 0100 0001 右移九位，假设0100 0001 是有符号整数且它本身为正数那么就都移没了，变成0000 0000。有符号负数1000 0001 右移九位发生算数位移，抛掉下溢部分，MSB补1变成1111 1111。
        最后提一种比较特殊的位移运算：Roll Left和 Roll Right。这个怎么翻译好呢？向左／右循环移位？不如翻译成象形的向左滚，向右滚。8位二进制整数1000 0001 右滚1位变成 1100 0000。原来MSB处的1向低位移动，而LSB处的1跑到了最高位MSB处。反之亦然：8位二进制整数1000 0001 左滚1位变成 0000 0011。

cyycoish

三、整理一下房间，准备开始崭新的生活吧。
        刚开始读这篇帖子的时候，也许你会觉得计算机很好懂嘛！然后在第二段发现我竟然还要学习《组合数学》、《离散数学》……之类的鬼东西。这还没完，接着你又被一大堆概念搞得头昏脑胀，想放弃的时候却陡然间发现自己又长进了不少。以前总觉得魔术师好神奇，从礼帽里能拉出一只兔子。长大后发现自己的眼睛还是太年轻太幼稚了。以前总觉得计算机说不出来的有趣。玩游戏就如同看一场魔术表演。不知不觉中我们自己也变成了一位魔术师。可是，我们都知道我们的水平距离丹尼斯里奇这样的大卫科波菲尔或是约翰卡马克这样的胡迪尼还差很远。那么大家一起努力吧，计算机的世界永无止境。
        接下来我还是用第一段中的例子来说明32位和64位操作系统的区别。如果32位整数是5毛钱硬币，64位整数是一元钱硬币。那么如果你的钱包是圆柱形的并且直径等于5毛钱硬币，那你就只能接受5毛硬币的找零。如果你的圆柱体钱包能放得下一枚一元硬币，那么一定也能放得下5毛的硬币。因为5毛钱硬币的直径比一元钱硬币的直径小。你的圆柱形钱包就是CPU总线。一个硬币就是一个整数的大小。所以32位OS只能运行32位APP。而64位OS不仅可以运行64位APP还能运行32位APP，却不能运行128位APP。每天你都需要工作和买东西，钱包内的资金也在不断流入流出。作为OS的你只需要负责收支平衡即可。在C语言中各种变量类型代表着各种长度的整数。大致说来，在32位C语言编译器下。char是一个byte；short int 是一个word；int是一个dword；long也是一个dword；而long long 就是一个qword。此时的byte是8位整数，word是16位整数，dword是32位整数……以此类推。在64位C语言编译器下：char还是一个byte；short int也是一个word; int 同样是一个dword。而64位的Visual C/C++编译器中(VC 2010为例)long int 是dword； long long 却是qword。与之有别：64位gnu C/C++编译器中 long long 和 long 都是一个qword（我所用的OSX平台 Xcode 8.x下是这样的情况。）至于浮点数，我前面说过计算机内所有浮点数均可以用整数表示，欲知详情请参见：https://www.0xaa55.com/forum.php?mod=viewthread&tid=462
        浮点数的规矩是IEEE制定，float和double不管位于哪个平台下均分别为：32位和64位。唯一不一样的是long double。因为VC 2010和我所使用的gcc 4.2.1所支持的IEEE标准不一样，VC下long double是64位, 我的gcc下long double是128位。如果你在嵌入式平台上开发，那么使用C编译器之前一定要查看手册。因为这些平台特殊不仅支持的IEEE标准不一样，有的时候连ANSI/ISO C标准也不能很好支持。ANSI/ISO C标准下定义整数长度的头文件分别位于 stdint.h 于stddef.h 中。我们都是老司机，才不会发生不处理的溢出呢！

cyycoish

四、暮然回首却发现，也许我们每个人也是被另一个魔术师编出来的独一无二的魔术师。
        最后的最后还是有一些东西要提及的。知识越完备经验越丰富。上台表演时才越不容易穿帮。最后关于整数的存储，也是最重要的事情是 Big endian和 Little endian之间的区别。如果你在使用一块x86架构的Intel CPU，并且这样申请了一个整数变量： int a = 0xabcdef12; 当你取得A的地址后发现内存中放的是 12 ef cd ab; 我们说这就是 Little endian （低位优先，我一直理解为小头在前或是先排LSB） 形式的整数存放。那么 Big endian 是正好与 Little endian 相反的一种情况。产生这个现象的原因是CPU从内存中读取数据方式的差异。
32-bit integer: 0xabcdef12
L   0xabcdef12
ab___|  |  |  |
cd_____|  |  |
ef _______|  |
12_________|
High Memory Address
(Big endian)
32-bit integer: 0xabcdef12
0xabcdef12   L
    |  |  |  |_12
    |  |  |___ ef
    |  |_____cd
    |_______ab
High Memory Address
(Little endian)
        如图所示，因为内存以一个Byte（8位整数）作为一个单元，在 Big endian中一个整数的Most Significant Byte存放在内存较低的地址处，而Least Significant Byte则存放在内存相对较高的地址处。而在Little endian中，情况正好相反。而绝大多数Intel CPU都像Little endian这样：CPU总线到内存地址的映射正好相反。就好像总线被扭成了X型一样。这又特别与我们的大脑相似——大脑左半球管理右半边身躯。大脑右半球管理左半边身躯。而Little endian这种内存映射方式又被Intel所普遍采用，所以Little endian 又叫做Intel 约定。（万能的CPU啊，与你定下约定的Intel 命令你，读出数据！——于是我又中二了。）计算机硬件架构的发展非一日之寒。有时候我们的研究何尝不是站在巨人的肩膀上呢？如果要我们自己一寸一寸长成一个盘古，也许只会变成一个畸形的魔鬼。有前人研究下的课题，写下的库，我们直接利用现成的这并不是不劳而获。且不说前人的劳动值不值得利用，如果前人种的树不能留给后人乘凉那么这些树都变成塞满世界的废物与垃圾。你可以造自己的CPU，也许你的CPU自己还用得很舒服。但是在你自己的架构与计算机世界中，你将永远是个徒有闭门造车本事的井底之蛙。
        好了，最后我们来根据所学的知识算一道非常简单的题：
有如下位域：
struct BitField
{
        unsigned int dd : 8;
        unsigned int cc : 8;
        unsigned int bb : 8;
        unsigned int aa : 8;
};
如果执行以下代码，试问当我输入多少时能改变int a的符号？
void main() // 空面的写法是我故意的。
{
        int i;
        int a = 0xabcdef12;
        struct BitField * p = (struct BitField *)&a;
        scanf(“%d”, &i);
        switch (i)
        {
        case 1:
                p->dd = 0;
                break;
        case 2:
                p->bb = 0;
                break;
        case 3:
                p->cc = 0;
                break;
        case 4:
                p->aa = 0;
                break;
        default:
                return;
        }
}

13*0217

这么好看的系列文章，没人抢沙发，我就占了！！（总结和分享都清晰明了，加深了补码、有无符号整数、位移运算、可移植方面的理解）。
答案：4 。

‬‫K

小兔兔萝卜，来顶个贴，回个4，不知道ID为前10的大佬们学了多久