Question

sstream - 读取一行不知道有多少个的数字

sstream 当中的 istringstream 物件，可以以近似于 cin 的方式来读取一个 string 变数内含的资料。

sstream 的意义为 string stream，也就是说，把 string 变数看待成 stream。至于 istringstream 的 i，应该就是指 input 之意吧。

下面的程式可以读入一行不知道个数为多少个的数字，并输出这些数字的总和。

sstream - 读取不知道有多少行的输入、并且做 tokenize

UVa 483

cstdio - 数字转字串，字串转数字

C 的标准函式库提供了两个非常好用的函式，可以快速的转换字串成为数值。

UVa 10427

iostream iomaip - 八、十、十六进位数的输出入

就算使用者输入 ABC 或 abc（十六进位表示法），compiler 还是可以将之转换成十进位数字，存到 num 裡面。

十六进位时，输入的数字有 0x 或 0X 开头也可以（不要把 0 打成英文字母 o 或 O 了）。

附带一提，因为 iomanip 已经建好了 hex oct dec 等关键字，所以用 setiosflags(ios::hex) 是没有任何效果的。【有待商榷】

就算使用者输入 2e3（科学记号表示法），compiler 还是可以将之转换成十进位数字，存到 num 裡面。

UVa 537

string cstring - 字串运算

一、读字串，直到遇见空白、换行、档案结束为止。

二、读字串，直到一定数量，或者遇见空白、换行、档案结束为止。

三、读一行。

四、读全部。

五、读到特定字元为止。

六、交换。

七、长度。

八、比大小。

九、字串后面接字串。

cstring - 初始化阵列

memset 可以快速的初始化阵列的每一个 byte，让每一个 byte 都是一样的值。

algorithm - 排序

sort() 为 Intro Sort，stable_sort() 为 Merge Sort。

排序基本资料型态的方法。

排序自订资料型态的方法有两种写法。

ctime - 计时

ctime - 乱数

File

File（意义一）

档案是大家都知道的电脑常识：档案是一份电脑资料。

电脑资料其实是储存于硬碟，而不是储存于档案。为了方便处理电脑资料，所以发明了“档案”的观念。档案之于硬碟，就好比程式码之于机械码──前者是给人看的、后者是电脑实际在用的。

程式语言几乎都内建了存取档案的函式库，例如 C 的 FILE、C++的 fstream，它们可以跨平台，无论在 Windows 作业系统、Mac OS 作业系统、Linux 作业系统都可以顺利运行。

程式语言通常也内建了存取目录的函式库，不幸的是，多半不能跨平台。一种解决方式是使用更高阶的语言和环境，例如 Qt 的 QFile、Java 的 java.io.File、Python 的 file object。

利用函式库存取档案，最小单位是 1 byte = 8 bit，公认标准！

File（意义二）

电脑的功能是：输入资料、处理资料、输出资料。程式语言理所当然要有输入资料与输出资料的指令。

输入资料从哪裡来？输出资料到哪裡去？资料的来源和去处，称为档案！档案不是一个实体的东西，而是一个抽象的概念。

C 的 FILE 就是档案。stdin、stdout、stderr 是档案。想要让电脑储存的档案（意义一）当作档案（意义二），可以利用 fopen()。

C++的 stream 就是档案。取名为 stream，其实是错的。stream 的原意是：资料只能依序传递，资料只能从头处理到尾、不能从尾处理到头、不能跳著处理。

想要深入了解档案，可以参考“Linux 系统程式设计”、“作业系统”的教科书。

Bitwise Operation

Bitwise Operator

欢迎来到二进位的世界。电脑资料都是以二进位储存，想当然程式语言的变数也都是以二进位储存。在 C/C++当中有几个位元运算子：<< SHIFT LEFT、>> SHIFT RIGHT、& AND、| OR、^ XOR、~ NOT，可以对变数进行位元运算。接下来要介绍位元运算的一些用途。

UVa 10469 10264

<< SHIFT LEFT
>> SHIFT RIGHT

这两个运算子的功能主要是移动一个变数中的所有位元，位元向左/向右移动之后，最高位/最低位的位元会消失，最低位/最高位的位元补 0：

5 << 1 = 10	// 00101 的全部位元向左移动一位数变成 01010。
5 << 2 = 20	// 00101 的全部位元向左移动两位数变成 10100。
5 >> 1 = 2	// 00101 的全部位元向右移动一位数变成 00010。
5 >> 2 = 1	// 00101 的全部位元向右移动一位数变成 00001。

在十进位当中，当全部位数向左移动一位时，数值大小会变成原来的十倍，向左移动两位时，会变成原来的百倍。这种情形在二进位也是成立的，当全部位元向左移动一位时，会变成原来的两倍，向左移动两位时，会变成原来的四倍。至于往右移动也是类似道理，变成了除法而已。

由于电脑进行位元运算比乘法、除法运算快上许多，所以有很多专业的程式设计师，会利用位元运算来取代乘法、除法运算。优点是程式执行效率增加，缺点是程式码可读性变低：

& AND

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

&的功能是将两个变数对应的位元进行 AND 逻辑运算，然后产生新变数。

   00000000000000000000000001110100 -> 116
 & 00000000000000000000000000101001 -> 41
 ----------------------------------
   00000000000000000000000000100000 -> 32

&的特色，就是可以判断出位元是不是 1。例如我们想要数一个变数有几个位元是 1：

Bitwise Trick

Bitwise Trick

http://blog.kuoe0.tw/posts/2012/01/26/utlization-of-bitwise-operation

http://blog.kuoe0.tw/posts/2012/01/28/bitwise-operation-set-operation

http://www.aggregate.org/MAGIC/

http://graphics.stanford.edu/~seander/bithacks.html

实作时要特别小心运算子优先次序。没有特地括括号的情况下，次序高的先结合。

gcc 内建函式

http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

__builtin_clz        count leading 0. find leading 1. log2(n).
__builtin_ctz        count tailing 0. divide by 2^n.
__builtin_popcount   count bit 1.

交换两个 int 变数

计算有几个位元是 1（仅适用 32 位元无号整数）

颠倒位元顺序（仅适用 32 位元无号整数）

检查缺少的正整数

阵列裡放入 1 到 10 的正整数，最后发现少了一个，请找出少了哪一个。

使用 Counting Sort 虽然时间複杂度低，但是空间複杂度高。

Pointer

前言

我自己有一套简单的解读方式，儘管这不一定是 C/C++设计者的原意，但是应该能让大家确实的掌握指标的概念。

记忆体与位址

谈指标之前，必须简述一下记忆体与位址的概念。我们可以把记忆体简单地想成一条很长很长的 0 与 1 字串，总长度是固定的。

接著我们要替这条长长的字串订立位址，就像是替一条公路设立里程碑。一开始是位址是零，然后每八个字，就让位址增加一单位。

注：早期的 CPU 一次可读八个字，所以设定八个字为一单位。而现在的 CPU 一次可读三十二字，更新颖的 CPU 一次可读六十四字，但是都仍然维持八个字为一单位。

位址通常都会用 16 进位表示，数值开头再加个 0x，表示是 16 进位数字。

变数

程式当中所有宣告的变数均会存放到记忆体当中的某一段，变数的数值会转换成二进位，以 0 与 1 字串形式储存。

编译器和作业系统会帮我们安排适当的地点，让这些变数不会重叠在一起。另外，如果是宣告阵列，在记忆体当中一定是连续的一段，中间不会被隔开。

没有变数的地方，我们不能随意取值和设值，否则会让程式立刻中止。

至于有变数但是没有设定初始值的地方，无法预测是 0 或 1，我们不能随意取值，否则会产生不可预期的结果，甚至让程式当掉。

想要取得变数储存的数值，只要直接用变数名称就行了。

想要获得变数所在的位址，只要在变数名称前面加&，就能算出变数的位址。

储存位址的变数型态

我们假设 C/C++有一种变数型态叫做 address，此变数型态储存的数值，是一个位址。

C/C++的指标，概念上等同于 address 变数型态。无论是哪一种型态的指标，储存的数值，都是一个位址，没有差别。

现在我们可以把任何一个变数的位址，储存在指标之中了。这时候指标的型态发挥用处了：编译器会判断“指标型态”与“变数型态多一个*”两者一不一致，当不一致时会告知我们错误讯息。

储存位址的变数，本身也是一个变数呀，当然它也有位址了。我们也可以把这个位址，用另一个位址变数存起来。

位址进行比大小运算

我们可以让两个位址比大小，比较原则就跟一般的整数比大小一样。

位址进行加整数、减整数运算

我们可以让位址跟整数相加，让位址减掉整数（但是不能让整数减掉位址），以及使用加加与减减运算。

这时候指标的型态总算是有用处了，C/C++很聪明，会根据“指标型态少一个*”的型态所占的记忆体大小，来决定加与减的基本倍率。

位址进行减法运算

我们可以让两个位址相减，相减的结果是一个 int 变数。

指标型态再度发挥功用，C/C++会根据“指标型态少一个*”的型态所占的记忆体大小，求得两个位址之间可以储存几个该型态的变数。

注：我们无法直接让两个位址相加，除非自行将位址转型成整数。

位址进行反运算

我们可让位址进行 NOT 运算，规则与一般整数进行 NOT 运算一样，结果是一个 int 变数。

位址进行解参考运算

我们可以从一个位址开始，抓一段连续的记忆体，当作一个变数。只要在一个位址前面加上*就行了。（这个*与宣告变数时用到的*意义不同，也与乘法运算的*意义不同。）

C/C++会根据“指标型态少一个*”的型态，从该位址开始，截取该型态大小的记忆体当作一个变数，并自动设定好变数型态。

重点回顾

1. 在变数前面加&，就能得到变数所在位址。变数型态多一个*。
2. 不管是哪种指标，其实都是储存位址的变数型态。
3. 位址的运算（指标的运算）
    1. 设值运算（assign）：=
    2. 比较运算（compare）：< > == >= <= !="3." 加整数、减整数：+="" -="" 前++="" 后++="" 前--="" 后--。不能整数减位址。="" 4.="" 减法运算（subtract）：-="" 5.="" 反运算（not）：前面加!="" 6.="" 解参考（dereference）：前面加*="" 7.="" 参考（reference）：前面加&。存位址的变数也是个变数，既是变数就有位址。="" 8.="" 索引（index）:="" []，请见下面介绍。="" 其他运算，必须自行转型成整数后，才有办法算。="" 编译器会做型态检查，参考与解参考时，会拿“指标型态少一个*”的型态做判断。="" <="" pre="">

附录：Endianness

下面的程式码的执行结果，跟 0 与 1 在记忆体内排放的顺序很有关係，看你使用的电脑系统是使用 Big-Endian 还是 Little-Endian，印出来的结果会不一样。

Endianness 的详细介绍： http://libai.math.ncu.edu.tw/bcc16/pool/1.33.shtml 。

注：一般家用电脑都是採用 Little-Endian。这裡所画的图都是 Big-Endian，是为了让各位比较容易理解。

附录：memset

我们都知道 C 的标准函式库有一个函式叫做 memset，不管要被设值的资料是什麽型态，都是以 1 byte 为单位来设值。写成程式码大概是这样：

附录：void*

C 语言有一种特殊的指标是 void*。其实他也是储存一个位址，唯一的差别是它不能进行解参考。C++则已经捨弃亦没有必要使用 void*。

附录：同一行宣告许多指标

如果想在同一行宣告许多指标，则从第二个变数名称开始，都要额外加上星号才行。这是一个不太直觉的规定。既然古人发明 C 时就这样规定，我们只得依从。

附录：指标的指标的指标，解参考再解参考再解参考，取位址。

各位读过上面文章之后，应该可以轻易弄清楚这些事情背后的原理，而不是去背记*和&可以相互抵销这种东西。

注：有些面试主考官最喜欢问这样的问题，好似懂了这些东西就是会写程式。这个问题不是在考验你会不会写程式，这是在考验你眼睛好不好。

附录：动态记忆体

宣告动态记忆体，由于实用性与技术上的考量，编译器没办法直接给个变数名字，所以只好给变数的位址，凑合著用。

位址加整数、减整数后，进行解参考运算

a[x]这个语法，表面上看起来是得到 a 阵列第 x 格。事实上[]的意思是“指标加减整数后，进行解参考运算”，a[x]其实是*(a+x) 的意义，a 和 x 其中之一为整数、另外之一为位址变数。会有这种语法是因为易读、方便。

Array

阵列变数型态

阵列是一种变数型态，要宣告一个阵列变数并不困难。

C/C++宣告阵列变数的语法非常不直觉，造就许多乱象。既然事实已经无法改变，也只能接受它了。

比较特别的是，一般的变数我们都能知道变数裡所存放的值，只要使用变数的名称就能得到变数值。然而我们无法得知阵列变数裡所存放的值，事实上我们也不需要用到此值。

阵列变数的指标

阵列变数既然是一个变数，当然也拥有记忆体位址了。同样地，使用&就可以取得记忆体位址。

阵列变数会自动改变变数型态

http://c-faq.com/aryptr/aryptrequiv.html

使用阵列变数时，编译器会自动帮忙把阵列变数改变成另一种型态的变数，并且设定其数值为阵列第零格所在的记忆体位址。

只有三种情况，编译器会保留阵列变数的原本模样。

搞得这麽複杂，是因为编译器想尽办法让我们不能更动阵列变数储存的数值。毕竟阵列是用来规划大量变数的储存位置，要是随便更动阵列变数的话，牵一髮动全身，记忆体就大乱了。

另一方面，改变成指标型态之后，要存取阵列元素就方便多了。请参考前面 Pointer 章节提到的各种运算。

存取阵列元素

初始化阵列变数、初始化阵列元素

我们不能更动、也看不到阵列变数储存的数值！只有编译器和作业系统有权力初始化阵列变数，而我们只能初始化阵列元素。

附带一提，在新版本的 C/C++当中，struct、vector 也都可以使用大括号初始化元素，相当方便。这就留给读者自行研究吧。

阵列元素是字元（也就是字串）

字串是一个 char 阵列。

前面提到，阵列变数会自动改变变数型态。凡是使用 char[]型态的变数时，编译器一样会把变数型态改变为 char*。

另外一定要提的是，C++ I/O 遇到 char*变数时，会鸡婆地处理后续字元；而不是当作一个普通的记忆体位址。

附录：string literal

说到了字串，就不得不提一下 string literal。双引号括起的字串，称作 string literal，是一个阵列变数，而且编译器会把阵列元素设定成常数，我们不能更动其值。

http://c-faq.com/aryptr/aryptr2.html

阵列元素是指标

我们也可以宣告一个存位址的阵列。

这样的阵列变数，也可以用&得到记忆体位址。然而变数型态相当複杂，不实用，又难背，这裡就略过不提了。

阵列元素是阵列

这个太疯狂了。我一点也不想介绍。反正就是多维阵列。

得到阵列大小

使用 sizeof 关键字就可以得到阵列大小。注意到，回传的变数型态是 size_t，一般来说是一个无号整数；回传的变数型态绝对不是 int。

有一种情况要特别小心：函数的参数写成阵列变数的模样，但是编译器事实上会帮忙改成指标变数。此时用 sizeof 得到的不是阵列大小而是指标大小。

附录：动态记忆体

上个章节提到，宣告动态记忆体，编译器给不出变数名称，只能给个指标将就著用。不过在新版本的 C 语言当中，已经可以给出变数名称了。

附录：heap 与 stack

编译器进行记忆体管理，有两个概念称作 heap 和 stack，分别是指整个记忆体的前端、后端这两块区域。heap 通常用来存放程式当中一开始就建立好的变数，以及存放动态记忆体；stack 用来存放执行过程中新建立的变数。

然而 heap 和 stack 的实际运作情形，在不同的编译器和作业系统可能有一些差异，似乎没有一个绝对的说法。

当记忆体用量过大，造成 heap 与 stack 两块区域相撞，此时称作 stack overflow，程式会当机。

Function

http://www.newty.de/fpt/index.html

Thread

http://kheresy.wordpress.com/2012/07/06/

http://kheresy.wordpress.com/2012/07/11/

http://kheresy.wordpress.com/2012/08/20/

http://sourceware.org/pthreads-win32/

Behavior

C/C++规格书

规格书针对那些不在规范之内的语法，特别注明其执行结果为下述四类的其中一类。

Undefined Behavior

没有订立执行结果，执行结果无法预测，可能发生任何事情，包括程式异常中止。身为程式员，绝对别让程式码出现这些行为！

例如 i = i++;，一行叙述当中，一个变数改变两次。

例如 short i = 30000 + 30000;，整数溢位。

Unspecified Behavior

没有硬性规定执行结果，执行结果已知有许多种，将是其中一种。不同的机器、编译器、编译设定，可能导致不同的执行结果。一旦运用了这些语法，程式码就无法跨平台使用。

例如 f( g(), h() );，无法确定 g() 和 h() 谁先处理。

例如−1.0 * 0.0，无法确定结果是负零、或是普通的零。

编译器运用此模糊地带，最佳化程式码，提升程式执行效率。

Implementation-defined Behavior

语言规格书没有硬性规定执行结果，留待编译器规格书明确规定执行结果。

例如-1 >> 1，负数所有位元往右移，编译器必须明确规定最高位元是补 0、还是补 1。

Locale-specific Behavior

根据当时设定的语系、环境变数，决定执行结果。

例如 puts("讚");，中文语系之下，将印出一个中文字；英文语系之下，将印出两个 ASCII 符号。

C/C++

Spec

这是 C11 正式版之前的最后一个草案。

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

http://www.mers.byu.edu/docs/standardC/index.html

Note

http://www.pvv.org/~oma/DeepC_slides_oct2011.pdf

http://goo.gl/EhINxE

Application

http://www.stroustrup.com/applications.html

http://www.lextrait.com/vincent/implementations.html