1-08运算符和表达式

一、概述

在C语言中，表达式和语句是构成程序的基本元素。本节和下一章节我们就围绕它们展开讲一讲其中的C语言基础语法。

首先，让我们区分这两个概念：

1. 语句(statement)，语句是代码中的一个完整的，可以执行的步骤。
   1. 语句要么以";“分号结尾(简单语句)，要么以”{}"代码块结尾(复合语句）
   2. 语句的作用复杂多样，常用于构建程序逻辑，如循环语句、条件判断语句、跳转语句等。
2. 表达式(expression)，表达式是由**变量、常量(称之为操作数)和运算符(也叫操作符)**组成的序列，它总是会计算出一个值。
   1. 表达式可以非常简单，如一个单独的常量或变量，或者非常复杂，如包含多个运算符和函数调用的组合。
   2. 表达式的作用就是计算值、赋值、函数调用等。

在C语言中，语句和表达式实际上并没有明显的绝对界限，它们的关系是：

1. 任何表达式只要直接加上一个分号，立刻就会成为一条语句。比如a = 10是一个赋值表达式，但只要加上";"，就会变成一个赋值语句。表达式语句是语句最简单的形式。
2. 语句不仅限于表达式，比如选择、循环等语句，语句可以更多的影响程序的逻辑。

在表达式中，最重要、最核心的就是连接表达式中常量、变量的运算符了，所以本小节我们主要研究C语言的运算符。

C 语言拥有异常丰富的运算符，比较常见和常用的有以下运算符：

1. 算术运算符
2. 赋值运算符
3. 关系运算符
4. 逻辑运算符
5. 位运算符
6. 三目运算符

这些运算符，又可以根据操作数的多少，分为：

1. 一元运算符，只需要一个操作数的运算符
2. 二元运算符，需要两个操作数的运算符，多数运算符都属于二元运算符。
3. 三目运算符，自然就是需要三个操作数的运算符。

下面逐一学习一下。

二、表达式的主要作用和副作用

为了更好的描述C语言当中运算符组成的表达式作用，我们引入两个重要的概念：

1. 表达式的主要作用。表达式的一个特点就是必然会得到一个结果，表达式的主要作用就是表达式会计算出一个结果值。
2. 表达式的副作用。**表达式在计算结果值之外产生的效果都可以称得上是副作用。**比如说：
   1. 修改了变量的值(最常见的)
   2. 执行了某些I/O操作，如打印到控制台或从文件读取数据。
   3. 调用函数，函数中执行了一些操作
   4. …

举几个例子：

比如表达式5 + 2，其主要作用是计算得出了一个结果值，也就是7，当然它没有副作用。

但假如是表达式int x = 7，**这是一个赋值表达式，赋值表达式也是表达式，也会计算出一个值，这个值就是赋值后变量的值，也就是表达式的右值。**在这个表达式中就是7。赋值表达式显然是有副作用的，副作用就是改变了变量x的值。

函数调用也是一个典型的表达式，比如test()，假如这次函数调用返回值是100，那么这个表达式的主要作用就是100这个返回值。再假如函数内部进行了I/O操作，将数据打印到了屏幕上，那么I/O操作就是表达式的副作用。

副作用是表达式非常重要的一个效果，它使得表达式可以进行计算值之外的操作，这在很多时候都是非常有用的。

但过于依赖副作用也会导致程序的执行具有更多的不可预测性，使得代码可读性下降，比如：

代码块 1. 依赖副作用会导致代码可读性下降-演示代码

int arr[] = {1, 2, 3, 4, 5};
int i = 0;
while (i < 5) {
    printf("%d ", arr[i++]);  // 这行代码的执行需要依赖i++的副作用
}

循环控制变量i的增加，就需要依赖i++的副作用，这无疑增加了复杂性，降低了可读性。如果改成下面：

代码块 2. 依赖副作用会导致代码可读性下降-演示代码2

printf("%d ", arr[i]);
i++;

代码可读性明显更好。

三、算术运算符

算术运算符包含最常见的+, -, *, /, %，它们分别表示加，减，乘，除以及取余(取模)。这些运算符比较简单，只需要注意：

1. 它们都是二元运算符，需要两个操作数。

2. 如果 / 的两个操作数都是整数，那么结果也是整数 (向零取整)。因此，1 / 2 的结果为 0 而不是 0.5。

3. % 取模运算要求两个操作数都是整数，而其它的算术运算符可以用于浮点数。

4. 在C语言中，%运算的结果符号总是和被除数保持一致。取模运算的结果遵循以下公式：

   (a % b) = a - (a / b) * b

四、运算符的优先级和结合性

鉴于算术运算符比较简单，所以我们放在最开始讲，下面我们要讲C语言运算符的两个非常重要的性质：

1. 优先级，当一个表达式当中存在多个运算符时，优先级决定了运算符的计算顺序。
2. 结合性，结合性决定了多个相同优先级的运算符共同组成一个表达式时的运算顺序，结合性非常重要。结合性可以是左结合或右结合的：
   1. 左结合性：意味着具有相同优先级的运算符将从左到右进行计算。
   2. 右结合性：意味着具有相同优先级的运算符将从右到左进行计算。

搞清楚它们，对于分析清楚一个复杂的C语言的表达式至关重要。

下面这张表格就罗列出了常见的运算符的优先级，以及它的结合性，其中优先级数字越小，代表优先级越高，越先进行计算。

表 1. C语言常见运算符的优先级和结合性

优先级	运算符	描述	结合性
0	小括号()	最高优先级	从左到右
1	++ --	后缀自增与自减，即a++这种	从左到右
小括号()	函数调用的小括号
[]	数组下标
.	结构体与联合体成员访问
->	结构体与联合体成员通过指针访问
2	++ --	前缀自增与自减，即–a这种	从右到左
+ -	一元加与减，表示操作数的正负
! ~	逻辑非与按位非
(type_name)	强制类型转换语法
*	解引用运算符
&	取地址运算符
sizeof	取大小运算符
3	* / %	乘法、除法及取余运算符	从左到右
4	+ -	二元运算符的加法及减法
5	<< >>	左移及右移位运算符
6	< <=	分别为 < 与 ≤ 的关系运算符
> >=	分别为 > 与 ≥ 的关系运算符
7	== !=	分别为 = 与 ≠ 的关系运算符
8	&	按位与
9	^	按位异或
10	`	`	按位或
11	&&	逻辑与
12	`		`
13	?:	三目运算符	从右到左
14	=	简单赋值
+= -=	和及差复合赋值
*= /= %=	积、商及余数复合赋值
<<= >>=	左移及右移复合赋值
&= ^= `	=`	按位与、异或及或复合赋值
15	,	逗号	从左到右

现在根据这张表格，我们尝试来分析几个复杂表达式的运算过程：

移位运算和算术运算结合：

对于表达式a + (b - a >> 1)，该表达式是如何进行计算的呢？分析如下：

1. "()"具有最高优先级，所以(b - a >> 1)最先计算。
2. 右移位运算符>>的优先级低于二元运算符-，再加上小括号的存在，所以b - a最先计算。
3. 随后将b - a结果右移。
4. 最后，将 a 加上上述计算的结果。

解引用运算符和自增自减运算符结合：

p是一个指向int变量的指针类型，对于表达式int num = *p++，该表达式是如何进行计算的呢？分析如下：

1. 后缀自增自减符号在表达式中拥有最高的计算优先级，所以整个表达式中p++最先进行计算。
2. 但后缀形式的p++，它的主要作用是直接返回当前p的值，副作用是将p的值加1。
3. 所以*(p++)就是*p，也就是对指针p执行解引用运算。
4. 最后执行赋值运算符=，将*p的结果赋值给变量num。整个表达式执行完毕。
5. 当然，整个表达式执行完毕后，p会自增1。这是表达式p++带来的副作用。
6. 整个表达式的运算过程是：将*p的结果赋值给变量num，并且p指针自增1。

对于表达式int num = ++*p，该表达式是如何进行计算的呢？分析如下：

1. 在表达式 ++*p 中，前缀自增运算符 ++ 和解引用运算符 * 都作用于指针 p。
2. 虽然，前缀自增运算符优先级要比解引用运算符高，但它必须结合一个操作数才能计算，根据书写的位置，前缀运算符只能结合*p。所以整个表达式最先计算的是*p
3. 前缀形式意味着主要作用是返回自增自减后的结果，副作用是自增自减1。
4. 所以=会将*p的结果自增1后再赋值给变量num。
5. 整个表达式的运算过程是：将*p的结果自增1后赋值给变量num。

关于运算符优先级和结合性的建议

运算符的优先级和结合性显然是运算符非常核心的重要概念，但强行把这张表格记下来显然是不现实的，所以我们给出以下总结和建议：

1. 一元运算符的优先级总是高于二元运算符。
2. 算术运算符的优先级仅次于单目运算符，是二元运算符中优先级最高的。
3. 赋值运算符(包括复合赋值运算符)的优先级几乎是最低的。这很好理解，如果运算还没结束，赋值就完成了，这不是想看到的。
4. 当不确定优先级或者为了代码清晰时，使用括号来明确运算顺序。这不仅可以避免优先级引起的错误，还可以使代码更易于理解。
5. 在实践中不要写出非常长，非常复杂、可读性非常差的的表达式。优秀的程序员不应以"写出别人不理解的代码"为荣：
   1. 如果表达式有过长的趋势，不妨改成两个式子
   2. 表达式中即便优先级没问题，也最好用合适的小括号括起来关键位置，明确代码意图，增强代码可读性。
6. C语言经历了漫长的发展，有很多关于复杂表达式的惯用法，除此接触它们你可能会很头疼，但基于习惯，我们还是建议程序员记住它们。

以上。

五、赋值运算符

表达式的主要作用是计算出一个结果，如果想要将这个结果保存下来，以便接下来使用，就需要用到赋值运算符了。

下面，我们将赋值运算符分为两类，来详细讲解赋值运算符：

1. 简单赋值运算符。也就是=，这里建议把它称为"赋值号"，而不要直接叫"等号"。
2. 复合赋值运算符。包含+=, -=, *=, %=等一系列复合赋值运算符。

1. 简单赋值运算符

在C语言中，简单赋值操作符 = 是最基本的赋值运算符，用于将右侧表达式的值赋给左侧的变量。这种操作是C语言中最常见的操作之一，几乎出现在每个程序中。

=赋值运算符组成的赋值表达式也具有两个作用，即主要作用和副作用。

1. 主要作用：表达式的主要作用是计算值，赋值表达式也不例外。但赋值表达式的值比较特殊，它计算出来的值就是那个要赋给变量的值，一般就是赋值表达式的右值。
2. 副作用：**对于赋值表达式，我们实际上更关注它的副作用。**赋值表达式的副作用就是会改变表达式左边变量的取值。

举例：

(ch = getchar()) != '\n'

这个表达式是我们前面讲基本数据类型时，给出的一个惯用法，现在我们来分析一下这个表达式：

1. 由于小括号的存在，我们先分析表达式ch = getchar()
   1. getchar()是函数调用表达式，它的优先级最高，先执行。
   2. 函数调用会返回一个从stdin读取到的字符，然后将该字符赋值给ch变量
   3. 整个赋值表达式的值，就是getchar()函数的返回值，也就是这一次读到的字符
2. (ch = getchar()) != '\n'整体就是：
   1. 判断getchar()函数的返回值，也就是这一次读到的字符是否是换行符
   2. 如果不是换行符，则执行xxx

除此之外，以下细节也需要稍微注意下：

赋值的过程中如果右值和左边类型不匹配，会自动进行隐式类型转换，当然这个过程中往往伴随精度损失。如下：

代码块 3. 赋值过程中的隐式类型转换-示例代码

int i;
float f;

i = 72.99f;   /* i is now 72 */
f = 136;    /* f is now 136.0 */

由于赋值表达式的主要作用存在，所以可以用=串联几个变量一起进行赋值，但这种方式可读性差，不推荐：

i = j = k = 0;    // 三个变量的取值都是0

由于赋值运算符是右结合的，上述表达式等价于：

i = (j = (k = 0));

课堂小练习

代码块 4. 课堂练习题1

int i;
float f;
f = i = 33.3f;

请问变量 f 的值是多少？

2. 复合赋值运算符

利用变量原有的值去计算新的值，这在程序中是非常普遍的。例如：

i = i + 2;

C 语言的复合赋值运算符可以将上面的表达式简写为：

i += 2;     /* same as i = i + 2 */

类似地，还有：

代码块 5. 复合赋值运算符-演示代码

i -= 2;     /* same as i = i - 2 */
i *= 2;     /* same as i = i * 2 */
i /= 2;     /* same as i = i / 2 */
i %= 2;     /* same as i = i % 2 */
...

复合赋值运算符组成的表达式同样存在主要作用和副作用，但一般它主要作用我们很少去使用，更多的还是关注它的副作用，即给变量赋值的作用。

六、自增运算符和自减运算符

自增 (加 1) 和自减 (减 1）是C语言编程中非常常见的基础操作。当然，这个操作可以用赋值运算符来完成，比如：

代码块 6. 用赋值运算符完成自增自减-参考代码

1

i = i + 1;

2

i = i - 1;

3

i += 1;

4

i -= 1;

但这样肯定是比较麻烦的，C 语言提供了一种更简洁的方式：

1. ++：自增运算符
2. –：自减运算符

自增自减都有前缀运算符(如++i, --i)和后缀运算符(如 i++, i–)两种不同的形式，前后缀不同组成的表达式运算也不同。

大多数C语言学习者都会对前缀和后缀的不同运算方式头疼，这里我们将彻底给大家讲明白这个语法。

我们以两个简单的例子，来说明前缀和后缀运算符的区别：

前缀自增自减，具有右结合性

对于一个简单的前缀运算表达式：--a

1. 对于表达式--a我们先分析它的主要作用和副作用。
   1. 主要作用是：返回变量a自减1后的结果，这就是此表达式计算出来的一个值。
   2. 副作用是：变量a自减1。
2. 前缀运算符的优先级非常高，如果--a处于一个复杂的表达式当中，那么它的主要作用就发挥作用。在整个表达式中它代表a自减1后的值。
3. 比如表达式是--a * 10 + 10这样，--a会优先计算，并且它在整个表达式中代表a自减1后的值。

所以我们可以对前缀自增自减运算符做一个总结：

前缀运算符总会先进行自增自减，表达式的主要作用是返回自增自减后的结果。副作用则是变量自增自减1。

小练习

代码块 7. 前缀自增自减-演示代码

int a = 1;
int b = ++a;

printf("%d\n", --b);

printf("a is %d now.\n", a);
printf("b is %d now.\n", b);

输出的结果分别是什么呢？

下面，我们可以用同样的手段来分析后缀运算符：

后缀自增自减，具有左结合性

对于一个简单的后缀运算表达式：a++

1. 表达式a++同样具有主要作用和副作用：
   1. 主要作用是：直接返回变量a的值，这就是此表达式计算出来的一个值。
   2. 副作用是：变量a自加1。
2. 后缀运算符的优先级同样很高，如果a++处于一个复杂的表达式当中，那么它的主要作用就发挥作用。在整个表达式中它代表a变量原本的值。
3. 比如表达式是a++ * 10 + 10这样，a++会优先计算，并且它在整个表达式中就代表a的值。

所以我们可以对后缀自增自减运算符做一个总结：

后缀运算符总会先直接返回被运算变量的值，表达式的主要作用是返回原本变量的值。副作用则是变量自增自减1。

1. 课堂练习

课堂小练习

代码块 8. 自增自减符号课堂练习代码

int i = 1;
int j = 2;
int k = ++i + j++;

int x = 4;
int y = 5;
int z = x++ + ++y * 10;

请指出上述代码中，各变量的最终结果分别是什么。

2. 注意事项(重要)

首先我们来看一段代码：

代码块 9. 自增自减运算符陷阱-演示代码

int a = 1;
// a = a++;
// int b = a++ + --a;

分别释放两段注释处的代码，结果是什么呢？符合上述我们对自增自减符号的理解吗？

实际上，上述代码在不同平台编译器运行的结果，可能是不一样的。这又涉及到C语言的一个坑爹的语法陷阱。

在C语言中，类似表达式i = i++这样，被自增自减的变量在同一个表达式中出现多次，会引发未定义行为。这意味着不同平台编译器可以选择任意方式来处理这种情况，包括但不限于返回任何值、程序错误崩溃或其余难以预测的结果。

那么为什么这种代码会导致未定义的行为呢？

这是因为同一个变量 i 在同一条语句中被修改了多次。

而按照 C 语言标准，同一个变量在同一个条语句之间只能被修改一次，如果多次修改会引发未定义行为。

于是不同的编译器平台，就可以自由地决定，同一变量多次修改的执行顺序(执行顺序不同结果必然不同)，甚至可以返回任意值或者程序崩溃。

总之，基于程序员日常开发的经验以及出于规避C语言语法陷阱的考量。对于自增自减符号的使用，我们给出以下建议：

1. 在for循环中使用自增自减符号是最常见的、且最清晰、稳定准确不出错的用法。
2. 自增自减运算符尽量不要用于连接表达式，尽量单独成行，这样就不会因副作用产生歧义。
3. 如果一定要将自增自减符号写在表达式中，那么严禁被自增自减的变量在同一个表达式中出现多次。

七、关系运算符

在C语言中，关系运算符用于比较两个值，并根据比较的结果返回一个布尔值（在C语言中，1表示true，0表示false）。

C语言中的关系运算符包括：

1. 等于 (==)：C语言中把判等符号直接称之为"等于"，这就是前面我们建议大家把赋值运算符"="称之为"赋值号"的原因。
2. 不等于 (!=)
3. 大于 (>)
4. 小于 (<)
5. 大于或等于 (>=)
6. 小于或等于 (<=)

关系运算符都是比较简单的，我们不再赘述。一些小的注意事项细节如下：

1. 关系运算符组成的表达式的主要作用是返回一个布尔值，也就是两个操作数比较的结果。且它一般没有副作用！
2. 关系运算符经常和逻辑运算符一起，组成一个逻辑表达式(或称布尔表达式)，结果返回一个布尔值。

八、逻辑运算符

C语言的逻辑运算符非常简单，只有三个：

1. 短路与(&&)：当且仅当两个操作数都为真（非零）时，结果为真。
2. 短路或(||)：如果至少一个操作数为真（非零），结果为真。
3. 逻辑非(!)：一元运算符，只对单个操作数取反。如果操作数为真（非零），结果为假（0）；如果操作数为假（0），结果为真（非零）。

注意：C 语言会把任何零值当作 false，任何非零值当作 true。

所谓的短路指的是：

1. 短路与(&&)，如果左操作数的值已经是假(零值)了，那么右操作数则不进行计算，直接返回false。
2. 短路或(||)，如果左操作数的值已经是真(非零值)了，那么右操作数则不进行计算，直接返回true。

短路的好处不仅仅是减少运算次数，提高效率，更重要的是避免程序中的一些错误，比如：

1

(i != 0) && (j / i > 0)

如果没有短路计算，上面的表达式可能就会出现除零错误，导致程序崩溃。

一个非常经典的问题是：

表达式i < j < k在 C 语言中是合法的，但可能不是你所期望的含义。

比较运算符是左结合性的，所以i < j < k等价于(i < j) < k，换句话说，该表达式首先检测 i 是否小于 j，然后用比较后产生的结果 (0 或者 1) 和 k 进行比较。

若要测试 j 是否位于 i 和 k 之间，我们应该使用：i < j && j < k。

九、位运算符

位运算符在系统编程、嵌入式系统、加密程序、图形处理等需要底层数据控制和快速运算的领域中非常有用。

但是在偏向业务逻辑开发的应用级领域则不太需要使用，因为可读性和代码维护的重要性往往大于微小的性能提升。总得来说，在以后的学习工作中，位运算符不算是一个频繁使用的语法点，但考虑到面试常考常问，我们仍然把位运算符当成学习的重点看待。

在C语言中，一共提供了6个位运算符，它们都可以对整数数据进行位运算操作。

首先，我们讨论两个移位运算符(因为它们最常用)，然后再讨论其他 4 个按位运算符 (按位取反~，按位与&，按位异或^，按位或|)。

为了更好的描述位运算符，这里给出一个概念定义：

**位模式：**某个变量的位模式，指的是该变量在计算机中的二进制存储形式。对于整数变量来说，位模式也就是该整数在内存中的补码形式。

1. 移位运算符

在C语言中，有两种类型的移位运算符，它们分别是左移位运算符（<<）和右移位运算符（>>）。

移位运算符，可以通过将整数数据的二进制位向左或向右移动，来变换整数的二进制表示，从而改变整数值。

下面用两个表达式来描述移位运算符的基本作用，其中i是整数，j是一个正整数：

1. i << j：将 i 的位模式向左移动 j 位。
   1. 移出去的高位丢弃，并在低位补0。
   2. 实际上该操作相当于将i乘以 2j（如果没有溢出的话）
   3. 此表达式的主要作用是返回i移位运算后的结果
   4. 此表达式一般没有副作用，不会改变i变量的取值，移位运算符没有赋值的作用！！
2. i >> j：将 i 的位模式向右移 j 位。
   1. 移出去的低位丢弃，如果i是无符号数或者非负值，则在左边补 0。
   2. 如果 i 是负值，其结果会根据编译器平台实现不同而不同：一些实现会在左边补 0，一些实现会在左边补 1。
   3. 在i是非负数的情况下，实际上该操作相当于将i除以2j（注意整数除法的结果还是整数）
   4. 此表达式的主要作用是返回i移位运算后的结果
   5. 此表达式一般没有副作用，不会改变i变量的取值，移位运算符没有赋值的作用！！

注意事项/细节/建议

右移位运算符会根据平台实现不同，会在左边补0或者补1，这是非常坑爹的一个设计。因为当你尝试对一个负整数做右移运算时：

1. 有些平台(左边补0的)，可能会将负整数右移后得到一个正数。
2. 而有些平台(左边补1的)，会保持右移后数值的符号不变。

所以我们给出关于关于位运算符使用的第一个建议：

在实际开发中，进行移位运算的数据往往是内存地址、数组长度、某个数据结构的容量等非负数数值，所以为了更好的平台移植性，我们建议大家最好仅对无符号数进行移位运算。

一个参考的代码示例如下：

代码块 10. 移位运算符的使用-参考代码

unsigned short i, j;

i = 10;   // 0000 0000 0000 1010
j = i << 2; // 0000 0000 0010 1000 十进制40
j = i >> 2; // 0000 0000 0000 0010 十进制2

总结：

从上面的例子可以看出，对无符号整数左移 j 位，相当于乘以 2j (不发生溢出的情况下)；对无符号整数右移 j 位，相当于除以 2j。

左移时如果发生了溢出将产生未定义行为，所以程序员在执行左移位运算时，需要认真思考移位的极限，避免溢出产生。

2. 按位运算符

按位位运算符包含：按位取反~，按位与&，按位异或^，按位或|。其中按位取反是一元运算符，其余都是二元运算符。

对于以下表达式：

~a：对a进行按位取反运算。也就是将 a 的每一位进行取反操作。即 0 变成 1，1 变成 0。

i & j：对 i 和 j 的每一位进行逻辑与运算。只有两个数的相应位都为1时，结果位才为1，否则为0。

i | j：对 i 和 j 的每一位进行逻辑或运算。只要两个数的相应位中有一个为1，结果位就为1，否则为0。

i ^ j：对 i 和 j 的每一位进行异或运算。如果两个数的相应位一个为0，另一个为1，则结果位为1，否则为0。(对应位不同结果是1)

注意：

1. 这些表达式的主要作为是返回位运算后得到的结果，没有副作用，不会改变任何一个操作数的值！！
2. 在C语言中，&、|不是逻辑运算符，而是位运算符，不要搞混淆了。

下面的代码示例演示了这些运算符的作用：

代码块 11. 按位运算符的作用-演示代码

unsigned short i, j, k;

i = 21;   /* 0000_0000_0001_0101 */
j = 56;     /* 0000_0000_0011_1000 */

k = ~i;   /* 1111_1111_1110_1010 */ 
k = i & j;  /* 0000_0000_0001_0000 */ // 16
k = i | j;  /* 0000_0000_0011_1101 */   // 61
k = i ^ j;  /* 0000_0000_0010_1101 */ // 45

除了按位取反运算符外，其余的位运算符都有对应的复合赋值运算符形式：

代码块 12. 位运算符的复合赋值运算符形式-演示代码

i = 21;
j = 56;
i <<= 2;    
i >>= 2;    
i &= j;     
i |= j;
i ^= j;

按位运算符中，比较需要留意的是按位异或。它具有以下一些非常优秀的性质：

a ^ 0 = a; 任何整数异或0得到的都是它本身

a ^ a = 0; 任意整数异或自己得到的都是0

a ^ b = b ^ a; 异或运算满足交换律

(a ^ b) ^ c = a ^ (b ^ c); 异或运算满足结合律

3. 常见面试题

以下问题，请考虑使用位运算符来解决。

定义一个函数，判断某个整数是否为奇数。

这个函数在以前大家就都会写了，如下：

代码块 13. 判断奇数函数定义-参考代码

bool is_odd(int num) {
  // 整数num取余不为0就是一个奇数
  return num % 2 != 0;
}

但如果需求更好的运算效率，可以考虑用位运算符来进行奇数的判断。

原理是：

一个整数的位模式表示，如果它是偶数那么它二进制位的最后一个位必然是0，反之如果它是奇数最后一位必然是1。

为什么呢？

因为二进制的每一位代表的是2的幂次方，从右向左分别是 20,21,22,…等等。

这些组成中，只有最低位的20不是2的整数倍，所以只要最低位是0，那么这个整数就一定是偶数。(因为更高位都是2的倍数)

基于以上原理，我们就可以写出以下用位运算判断奇数的代码：

代码块 14. 判断奇数函数定义-参考代码2

bool is_odd(int num) {
  /*
  * 让num按位与...0001
  * 如果是奇数，num的最后一位是1，返回true
  * 如果是偶数，num的最后一位是0，返回false
  */ 
  return num & 1;
}

下一题：

给定一个正整数，请定义一个函数判断它是否为2的幂(1, 2, 4, 8, 16, …)。

一个非常简单易想、易实现的方式就是：

只要这个数大于1且能被2整除，就一直将它除以2，判断最终得到的结果是不是1，若是1，则是2的幂。

参考代码如下：

代码块 15. 判断是否是2的幂-参考代码

bool is_power_2(int n) {
  // 只要这个数大于1且能被2整除，那就一直除以2
  while (n > 1 && n % 2 == 0) {
    n /= 2;
  }
  // 判断最终结果是不是1
  return n == 1;
}

这种解法可以用左移位运算符稍作优化，逆向思维一下。参考代码如下：

代码块 16. 判断是否是2的幂-参考代码2

bool is_power_2(int n) {
  int x = 1;
  // 只要x比n小就左移1位，乘以2
  while (x < n){
    x <<= 1;
  } // 结束while的条件是x >= n

  // 如果n是2的幂，那么x和n相等
  return n == x;
}

但这些解法都还不是最优的，下面我们先观察一下2的幂整数的位模式：

1：0001

2：0010

4：0100

8：1000

…

很显然一个整数，如果它是2的幂，那么它的二进制位表示中仅有一位是1，其余位都是0。

利用这个性质，我们将该整数和该整数减1做按位与运算，结果是0就说明该整数是2的幂。如下：

4 (0100) & 3 (0011) = 0

8 (1000) & 7 (0111) = 0

参考代码如下：

代码块 17. 判断是否是2的幂-参考代码3

bool is_power_2(int n) {
  return (n & (n - 1)) == 0;
}

这个实现代码更简洁，效率更高。

下一题：

给定一个不为0的整数，编写函数找出它值为1的最低有效位 (称之为Last Set Bit)。

一个示例如下：

输入：n = 24

输出：8

解释：24的二进制表示为 11000，值为 1 的最低有效位为 2^3，所以输出8。

如何实现呢？

一个仍然比较易想易实现的思路是：

将该数与1、2、4、8…等整数逐一做按位与运算，当结果不为0时，该整数的值为1的最低有效位就是它。

举例：

8：1000 值为1的最低有效位是8

8 & 1 = 1000 & 0001 = 0

8 & 2 = 1000 & 0010 = 0

…

8 & 8 = 1000 & 1000 != 0

于是8，就是整数8的值为 1 的最低有效位。

参考代码如下：

代码块 18. 寻找值为1的最低有效位-参考代码

int find_last_set_bit(int n) {
  int x = 1;
  while ((n & x) == 0) {
    x <<= 1;
  }
  return x;
}

这种实现实际上已经很不错了，但它还不是最优解。

要想搞清楚最优解的思路，我们再来复习一个前面课程提到过的问题：给出一个整数的补码，请求它相反数的补码。

例如：

x的补码形式：0101 1100

-x的补码形式，可以利用补码的一个性质来实现：

x + (-x) = 1, 000…02进制补码(其中0一共有n个，高位的1溢出被舍掉) = 0

于是我们可以找到x的二进制补码中，值为1的最低有效位(也就是last set bit)，那么它的相反数的补码就是：

1. last set bit保持不变
2. 从last set bit开始，所有高位取反

于是-x的补码就是：1010 0100

通过这个案例，我们就发现：x和-x的位模式，last set bit是一致的，高于last set bit的位全部相反，低于last set bit的位全部是0。

所以只需要将x和-x进行按位与操作，就可以找到last set bit了。

参考代码如下：

代码块 19. 寻找值为1的最低有效位-参考代码2

int find_last_set_bit(int n) {
  return n & (-n);
}

这个实现就非常简洁优雅了。

下一题：

给定两个不同的整数 a 和 b，请交换它们两个的值。(这里不要定义函数)

这个题目相信大家都可会用以下代码实现：

代码块 20. 实现两个数的交换-参考代码

int a = 100, b = 200;

int tmp = a;
a = b;
b = tmp;

这种方式也要求大家掌握，因为它具有以下优点：

1. 代码可读性很强，任何程序员一眼都能看明白。
2. 不限制被交换元素的类型，可以交换任何类型的两个元素。

当然它的缺点是：需要一个临时变量tmp，这可能会导致额外的内存空间占用。

所以在早期，出于节省内存空间，简化代码的考量，出现了下面利用异或位运算符交换两个元素的编程技巧(惯用法)：

代码块 21. 实现两个数的交换-参考代码2

int a = 100, b = 200;

a = a ^ b;
b = a ^ b;
a = a ^ b;

这种写法之所以能够完成两个数的交换，利用的是异或运算符^的性质。计算过程分析如下：

我们将原始的a 和 b的值记为a0，b0

第一个表达式执行后的a和b的值，记为a1和b1

…

于是整个计算过程为：

1. 第一个表达式执行完毕后：a1 = a0 ^ b0，b1 = b0
2. 第二个表达式执行完毕后：
   1. b2 = a1 ^ b1 = a0 ^ b0 ^ b1 = a0 ^ b0 ^ b0 = a0 ^ (b0 ^ b0) = a0 ^ 0 = a0。于是第二个表达式执行完毕后，b的结果就等于原始a了。
   2. a2 = a1 = a0 ^ b0
3. 第三个表达式执行完毕后：
   1. a3 = a2 ^ b2 = a0 ^ b0 ^ a0 = (a0 ^ a0) ^ b0 = 0 ^ b0 = b0。于是第三个表达式执行完毕后，a的结果就等于原始b了。
   2. b3不变，b的值仍然等于原始a的值。

以上，三个表达式执行完毕后，a和b在不利用额外空间的前提下就完成了交换，nice！

总结：

交换元素是程序中特别常见和重要的操作，在大多数情况下，我们还是建议大家用临时变量的形式交换元素。因为它可读性更好，且不受元素类型限制，并且效率几乎没有差异，只是占用了一些额外空间罢了。

而且用^交换元素还可能导致交换两个相同元素导致结果为0的情况出现，这也为程序带来了极大的风险。

下一题：

给定一个非空的整数数组nums，已知某个元素只出现了一次，其余元素均出现两次，那么请你找出这个只出现一次的元素。

怎么做呢？

使用异或运算即可，因为异或运算有以下性质：

1. 自己和自己异或为0，0和别人异或都是别人。
2. 异或运算还满足交换律和结合律。

于是只需要将数组中的所有元素，全部用^运算符链接起来，这样最终的结果就是那个唯一的元素。

例如：

数组nums：[1, 4, 2, 1, 2]

将所有元素都^链接起来，1 ^ 4 ^ 2 ^ 1 ^ 2 = (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4

于是4就是数组中仅存在一个的元素。

参考代码如下：

代码块 22. 查找数组中出现一次的元素-参考代码

int nums[] = { 1, 4, 2 ,1, 2 };
/*
* result就是最终找出的出现一次的元素
* 对于异或运算来说，0异或其它值都是其它值本身
* 所以result的初始值设置为0
*/
int result = 0;

// 遍历将数组中的所有元素都链接起来
for (int i = 0; i < 5; i++){
  result ^= nums[i];
}

printf("数组中的唯一元素就是 %d.\n", result);

以上。

4. 一道扩展题

题目：

给定一个非空的整数数组nums，已知有两个元素只出现了一次，其余元素均出现两次，那么请你找出这两个只出现一次的元素。

既然有两个元素只出现一次，那么求解这个问题就稍微复杂一些了。有两个比较好的手段可以参考：

1. 使用哈希表，以"元素-元素出现次数"的形式存储键值对记录每一个元素出现的次数。
   1. 一次遍历数组填充哈希表，再遍历一次哈希表即可找到只出现一次的两个元素。
   2. 利用哈希表实现，逻辑清晰直观，代码也比较简洁，是一个比较好的手段。
   3. 时间复杂度和空间复杂度都是O(n)，由于需要额外的哈希表数据结构，空间复杂度比较高。
2. 利用异或运算，分组从而求解两个只出现一次的元素。
   1. 这种方式代码可能没有那么直观易懂，但由于不占用额外内存，空间复杂度是O(1)
   2. 当然时间复杂度都是一样的O(n)，因为需要遍历几轮数组。

哈希表的实现方式，其实难点更多在于如何手写一个哈希表，因为C语言没有提供相关的库来实现哈希表。关于哈希表，我们等到后续《数据结构》阶段，再来详细探究，今天先略过。

这里，我们就重点探究一下异或运算如何实现求解这个问题。

利用异或运算，求解找出数组中的两个唯一元素

对于数组nums，我们设a和b是其中的两个唯一元素。

首先，我们仍然还是将数组中的所有元素都使用^运算符链接起来，但此时我们将得到a ^ b。

那么接下来咋办呢？

接下来需要分组：

只需要将nums数组，分为a和b单独存在的两个数组即可：

[a, …]

[b, …]

分组后，再分别将两个数组中的所有元素用^链接起来，于是结果就是a和b。

那么分组如何实现呢？

我们已知a和b必然不是同一个整数，值是不一样的，那么它们的位模式必然存在某一位是不同的，如下面的例子：

a(假设a是3): 0011

b(假设b是5): 0101

a ^ b = 0011 ^ 0101 = 0110

这就说明，a ^ b结果的位模式必然有一位是1，且该位为1意味着a和b在该位取值不同。

利用这样的一个特点，我们只需要找到a ^ b的某一个为1的位，然后根据该位为1还是为0，就实现了对nums数组的分组。

那如何找到a ^ b结果位模式中为1的那个位呢？

利用前面讲的求"last set bit"的算法即可。

于是，我们的分组是这样的：

1. a和b是不同的两个整数，那么它们在"last set bit"位必然是不同的（一个为0一个为1）
2. 利用这个特点，将数组分为两两组。

但是需要注意的是，该分组不需要物理上分组，只需要逻辑分组就可以了：

找到"last set bit"位后，遍历整数数组，每个元素都和"last set bit"值做"&"按位与运算：

1. 结果为0的是一组，说明这组元素"last set bit"为0，将它们都用^链接起来。最终结果就是一个只出现一次的元素。
2. 结果为1的是一组，说明这组元素"last set bit"为1，将它们都用^链接起来。最终结果就是令一个只出现一次的元素。

参考代码如下：

代码块 23. 利用异或求解数组中的两个唯一元素-参考代码

int nums[] = { 1, 4, 3, 2 ,1, 2 };

// 第一轮异或全体数组的结果, 也就是两个唯一元素的异或结果
int xor_result = 0;
for (int i = 0; i < 6; i++) {
  xor_result ^= nums[i];
}

// 找到last set bit
int lsb = xor_result & (-xor_result);

// 再次遍历数组，根据lsb将数组逻辑上分为两组
int a = 0, b = 0; // a和b代表两个唯一的元素
for (int i = 0; i < 6; i++) {
  if (nums[i] & lsb) {
    // 此组元素在lsb位的值是1
    a ^= nums[i];
  }else {
    // 此组元素在lsb位的值是0
    b ^= nums[i];
  }
}

// 循环结束后，a和b的值就是数组中两个唯一的元素

以上。