为你的变量们选择合适的数据类型将决定一个解决方案的正确与否。尤其是在几何问题上，精度问题通常导致了解决方案错误。更糟糕的是，有许多（通常不正确）关于这些问题的原因和解决方法的传闻。
  
    要能够避免这些问题，需要了解一些计算机内部工作原理。在这篇文章中， 我们将给出一些必要的事实并且来反驳一些传闻。在读完和理解这篇文章的基础上，你将能够避免上面提到的问题。

    这篇文章绝不是想要成为完整的参考书并且不是100%准确。其中有许多展示的东西都是简化过的。由于这篇文章的读者是TopCoder（TC）成员， 我们将关注与TC用来评估解决方案的基于x86架构的机器。例如，我们假设在我们的电脑中一个字节包含8个位并且机器使用32位的寄存器。

    虽然大部分文章都是宽泛的可以应用与所有的程序设计语言，这篇文章则将侧重点转向C++并且包含一些情况下在g++中的注意点。

    我们一开始将展示一张（经过一些简化的）在g++编译器上可用的整数数据类型表。你可以在任何g++的参考书中找到这张表。TC中其他所有的编译器有着类似的数据类型并且在对应的编译器文档中有着相类似的表。如果你没有用心记住，查查它们。下面我们将要解释所需要知道的每一个类型的存储大小，根据存储大小可以简单的推导出整数的范围。

Table 1: Integer data types in g++.

name	size in bits	representable range
char	8	-27to 27 - 1
unsigned char	8	0 to 28 - 1
short	16	-215 to 215 - 1
unsigned short	16	0 to 216 - 1
int	32	-231 to 231 - 1
unsigned int	32	0 to 232 - 1
long	32	-231 to 231 - 1
unsigned long	32	0 to 232 - 1
long long	64	-263 to 263 - 1
unsigned long long	64	0 to 264 - 1

 
注意点：
• int和unsigned int的存储大小是平台相关的。举个例子，在使用64位处理器的机器上，g++中的ints将具有64位。老的Borland的C编译器使用16位的整数。可以保证int总是至少具有16位。类似的，可以保证， 在任何系统上long至少具有32位。

• long long是g++的一个扩展类型， 它不是C++标准的一个部分（现在呢？）。许多C++的编译器舍弃这个数据类型或者用别的名字替代。例如MSVC++中有取而代之的__int64

---

传闻: 有符号整数存储时需要使用一个符号位和一个“数字”位
正确性: 部分正确

现在大部分电脑包括TC中使用的，以补码的形式存储整数。对于非负整数最高位是0而对于负数是1.但是这个不是一个符号位，我们不能得到一个“负0”通过翻转该位。负数以一种稍微不同的方式存储。-n存储的形式相当于n-1的按位取反。

在表2中我们将给出较小的以有符号字符型变量进行存储的位形式。
越靠右的位越是低位。

Table 2: Two's complement bit patterns for some integers.

value	two's complement form
0	00000000
1	00000001
2	00000010
46	00101110
47	00101111
127	01111111
-1	11111111
-2	11111110
-3	11111101
-47	11010001
-127	10000001
-128	10000000

注意由于负数的存储形式，两边的数并不是关于0对称的.b个位能够表示的最大整数是2^(b-1) - 1，最小的数是-2^(b-1).

一个简洁一点看补码的方法是所有的数字都是以2为基的除了最大的2的幂次是负的。举个例子， 11010001 位模式相当于1*(-128) + 1*64 + 0*32 + 1*16 + 0*8 + 0*4 + 0*2 + 1*1 = -128 + 81 = -47

---

传闻: 无符号数的存储形式就是它对应的二进制形式
正确性: 正确
一般来说，位形式包含了代表这个数的2进制表示。举个例子，11010001位形式对应于1*128 + 1*64 + 0*32 + 1*16 + 0*8+ 0*4 + 0*2 + 1*1 = 209

因此，一个b位的无符号变量，能表示的最小的数是0，最大的是2^b - 1(对应与所有的1的形式).

注意,如果最左边的位是0， 那么这个形式所对应的值不管这个数是有符号还是无符号都是相同的。如果我们有一个b位的串，并且最左边的位设置为1， 并且表示的数是无符号数x，同样的形式的有符号的数的值为x-2^b.

在我们上一个例子中，11010001形式既可以表示209(无符号变量）也可以表示-47（有符号变量）。

---

传闻: 在C++中，代码"int A[1000]; memset(A, x, sizeof(A));"在A中存储了x的1000个拷贝
正确性: 错误
memset()函数填充以字符为单位的内存，而不是整数。因此对于绝大多数的x值你会得到不期望的结果。
尽管如此， 对于两个值： 0和-1，它通常能够工作（这个经常使用）。第一个情况很简单，通过使用0来填充整个数组，每一个int的所有位都变为0， 因此代表数字0.事实上，第二个情况和前面一样，-1用char表示是11111111，因此我们用1填充了整个数组，使得数组包含-1.

（注意大多数处理器都有一个特殊的指令来用一个指定值填充一块内存。因此memset()操作比通常的用循环来填充要快）

当你知道你正在做什么的时候， memset()可以被用来使用特大或者特小数对数组进行填充，你仅仅需要提供一个合适的位的形式作为第二个参数，例如，使用x=63来在A中得到大的值（1, 061, 109, 567)。
【译者注：可以使用STL里面的fill函数进行填充，这里的63的位形式为00111111，进行填充后，int的位形式
变为了00111111001111110011111100111111，这个值既是1, 061, 109, 567。】

---

传闻: 位运算很有用
正确性: 正确
    首先，它们很快。其次，许多有用的技巧可以使用一些位运算来完成。
举一个简单的例子， x是2的幂次当且仅当(x & (x-1) == 0).(为什么呢？想想2的幂次的位形式是什么样的。) 注意x=x & (x-1)清除了最低有效位。通过重复执行这个操作（知道得到0）我们可以很简单的计算x的二进制表示中1的个数。

如果你关注与更多的此类技巧，下载Hacker's Delight的第二章的免费版并且阅读The Aggregate Magic Algorithms.

一个重要的技巧： unsigned int整数可以用来直接编码{0,1,...,31}的子集。当集合中包含数i时，变量的第i位变为1.例如 18（二进制10010 = 2^4 + 2^1)代表集合{1,4}。

当对这个集合进行运算的时候，位运算“与”对应于交集，位运算“或”对应于求并集。

在C++中，我们可以先是的通过使用x |= (1<提供了一个的处理任意大集合的类似功能。

这个技巧可以用在你的程序中来计算一个给定集合的所有子集的答案。这个技巧在SRM问题中经常使用。我们这里不深究细节，最好的方法学习它是看一些实际的实现（试着看下面问题的最好的解决方案）并且试图自己解决一些这样的问题。

  BorelSets (集合操作的一个简单联系, 生成集合直到没有新的集合产生)
  TableSeating 
  CompanyMessages 
  ChessMatch (为你的玩家们的子集找到最佳的分配方案) 
  RevolvingDoors (把你的位置和门的所有状态编码到一个整数当中)

---

传闻: 实数用浮点数表示方法进行表示
正确性: 正确
在计算机中最常用的表示“实数”的方法是使用IEEE 754标准定义的浮点数表示法。我们简单地回顾一下这个表示法。

基本上来说，“浮点数”的意思是十进制下的（更精确点，二进制下的）小数点的位置不固定。这将允许我们存储比定点数可以存储的更大范围的数字。

数字将用科学计数法表示，使用一个规格化的数字和一个指数。例如，在10进制当中，123.456可以被表示成1.23456*10^2。为了简记，我们有时使用字母E来表示“10的幂”这样的短语。例如，前面的表达式可以写作1.23456e2。

当然, 在计算机中我们使用二进制，因此5.125（二进制101.001）将表示为1.01001*2^2， -0.125（二进制-0.001）将表示为-1*2^(-3)。

注意任何（非0）实数x都可以写成(-1)^s * m * 2^e的形式，其中s∈{0，1},代表符号，m∈[1, 2)是标准化后的数而e则是（整数）指数。这个是我们将要存储的实数的一般形式。

我们到底要存储什么东西呢？基数是固定的，因此要存储的3样东西是符号位s，规格化后的数（称作尾数）m和指数e。

IEEE 754标准定义了存储实数的4种类型的精度。两个最常使用的是单精度（Single）和双精度（double）类型。在大多数程序设计语言中都有

相对应的数据类型的名称。你也许遇到过其他平台相关的数据类型（例如float），他们通常映射为上述类型之一。如果不能确定，
坚持上述两种类型就可以了。

单精度浮点数使用32位（4字节）进行存储，双精度使用64位（8个字节）进行存储。这些位像表3一样的使用：

Table 3: Organization of memory in singles and doubles.

	sign	exponent	mantissa
single precision	1	8	23
double precision	1	11	52

（这些位的顺序是按照存储的顺序给出的。也就是说，符号位处于最高位，然后紧接着的是8位或者11位的指数位再后面是23位或者52位的尾数位）

符号位
符号位很简单。0代表一个正数；1代表一个负数。翻转这个位将改变数的符号。

指数部分
指数域需要同时表示正数和负数指数。为了达到这个目的，在实际的指数e上加了一个偏移量。这个偏移量对于单精度是127，对于双精度是1023. 结果被存储为一个无符号整数。（例如，如果e=-13并且使用单精度，那么实际在内存中存储的是-13 + 127 = 114.）

这个隐含了可用指数的范围对于单精度是-127到128，而双精度是-1023到1024.这个几乎正确。由于后面谈到的某些原因，边界范围斗被保留用来存储一些特殊的数字。实际的范围分别是-126到127和-1022到1023。

尾数
尾数代表了这个数的精度位。如果我们写出这个数的二进制，这些将是前面的一些数字，而不管二进制下小数点的位置在哪里。（注意二进制小数点的位置是由指数部分指定的）

事实上我们使用2为基数使得我们可以做一些简单的优化：我们知道对于任何（非0）的数字来说，第一个数字一定是1.因此我们可以不用存储这个数字。结尾，一个b位的尾数就可以存储了一个数字的b+1个有效位。

欢迎访问最专业的网吧论坛,无盘论坛,网吧经营,网咖管理,网吧专业论坛 https://bbs.txwb.com 关注天下网吧微信/下载天下网吧APP/天下网吧小程序，一起来超精彩