贵阳网站开发人员工资,如何做一个自己的网站,千锋前端培训班,微信公众号功能介绍一、概述
在C语言中#xff0c;表达式和语句是构成程序的基本元素。本节和下一章节我们就围绕它们展开讲一讲其中的C语言基础语法。
首先#xff0c;让我们区分这两个概念#xff1a;
语句(statement)#xff0c;语句是代码中的一个完整的#xff0c;可以执行的步骤。 …一、概述
在C语言中表达式和语句是构成程序的基本元素。本节和下一章节我们就围绕它们展开讲一讲其中的C语言基础语法。
首先让我们区分这两个概念
语句(statement)语句是代码中的一个完整的可以执行的步骤。 语句要么以;“分号结尾(简单语句)要么以”{}代码块结尾(复合语句语句的作用复杂多样常用于构建程序逻辑如循环语句、条件判断语句、跳转语句等。 表达式(expression)表达式是由**变量、常量(称之为操作数)和运算符(也叫操作符)**组成的序列它总是会计算出一个值。 表达式可以非常简单如一个单独的常量或变量或者非常复杂如包含多个运算符和函数调用的组合。表达式的作用就是计算值、赋值、函数调用等。
在C语言中语句和表达式实际上并没有明显的绝对界限它们的关系是
任何表达式只要直接加上一个分号立刻就会成为一条语句。比如a 10是一个赋值表达式但只要加上;就会变成一个赋值语句。表达式语句是语句最简单的形式。语句不仅限于表达式比如选择、循环等语句语句可以更多的影响程序的逻辑。
在表达式中最重要、最核心的就是连接表达式中常量、变量的运算符了所以本小节我们主要研究C语言的运算符。
C 语言拥有异常丰富的运算符比较常见和常用的有以下运算符
算术运算符赋值运算符关系运算符逻辑运算符位运算符三目运算符
这些运算符又可以根据操作数的多少分为
一元运算符只需要一个操作数的运算符二元运算符需要两个操作数的运算符多数运算符都属于二元运算符。三目运算符自然就是需要三个操作数的运算符。
下面逐一学习一下。
二、表达式的主要作用和副作用
为了更好的描述C语言当中运算符组成的表达式作用我们引入两个重要的概念
表达式的主要作用。表达式的一个特点就是必然会得到一个结果表达式的主要作用就是表达式会计算出一个结果值。表达式的副作用。**表达式在计算结果值之外产生的效果都可以称得上是副作用。**比如说 修改了变量的值(最常见的)执行了某些I/O操作如打印到控制台或从文件读取数据。调用函数函数中执行了一些操作…
举几个例子
比如表达式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 的结果为 0 而不是 0.5。 % 取模运算要求两个操作数都是整数而其它的算术运算符可以用于浮点数。 在C语言中%运算的结果符号总是和被除数保持一致。取模运算的结果遵循以下公式 (a % b) a - (a / b) * b
四、运算符的优先级和结合性
鉴于算术运算符比较简单所以我们放在最开始讲下面我们要讲C语言运算符的两个非常重要的性质
优先级当一个表达式当中存在多个运算符时优先级决定了运算符的计算顺序。结合性结合性决定了多个相同优先级的运算符共同组成一个表达式时的运算顺序结合性非常重要。结合性可以是左结合或右结合的 左结合性意味着具有相同优先级的运算符将从左到右进行计算。右结合性意味着具有相同优先级的运算符将从右到左进行计算。
搞清楚它们对于分析清楚一个复杂的C语言的表达式至关重要。
下面这张表格就罗列出了常见的运算符的优先级以及它的结合性其中优先级数字越小代表优先级越高越先进行计算。 表 1. C语言常见运算符的优先级和结合性
优先级运算符描述结合性0小括号()最高优先级从左到右1 --后缀自增与自减即a这种从左到右小括号()函数调用的小括号[]数组下标.结构体与联合体成员访问-结构体与联合体成员通过指针访问2 --前缀自增与自减即–a这种从右到左 -一元加与减表示操作数的正负! ~逻辑非与按位非(type_name)强制类型转换语法*解引用运算符取地址运算符sizeof取大小运算符3* / %乘法、除法及取余运算符从左到右4 -二元运算符的加法及减法5 左移及右移位运算符6 分别为 与 ≤ 的关系运算符 分别为 与 ≥ 的关系运算符7 !分别为 与 ≠ 的关系运算符8按位与9^按位异或10按位或11逻辑与1213?:三目运算符从右到左14简单赋值 -和及差复合赋值* / %积、商及余数复合赋值 左移及右移复合赋值 ^ 按位与、异或及或复合赋值15,逗号从左到右
现在根据这张表格我们尝试来分析几个复杂表达式的运算过程
移位运算和算术运算结合
对于表达式a (b - a 1)该表达式是如何进行计算的呢分析如下
()具有最高优先级所以(b - a 1)最先计算。右移位运算符的优先级低于二元运算符-再加上小括号的存在所以b - a最先计算。随后将b - a结果右移。最后将 a 加上上述计算的结果。
解引用运算符和自增自减运算符结合
p是一个指向int变量的指针类型对于表达式int num *p该表达式是如何进行计算的呢分析如下
后缀自增自减符号在表达式中拥有最高的计算优先级所以整个表达式中p最先进行计算。但后缀形式的p它的主要作用是直接返回当前p的值副作用是将p的值加1。所以*(p)就是*p也就是对指针p执行解引用运算。最后执行赋值运算符将*p的结果赋值给变量num。整个表达式执行完毕。当然整个表达式执行完毕后p会自增1。这是表达式p带来的副作用。整个表达式的运算过程是将*p的结果赋值给变量num并且p指针自增1。
对于表达式int num *p该表达式是如何进行计算的呢分析如下
在表达式 *p 中前缀自增运算符 和解引用运算符 * 都作用于指针 p。虽然前缀自增运算符优先级要比解引用运算符高但它必须结合一个操作数才能计算根据书写的位置前缀运算符只能结合*p。所以整个表达式最先计算的是*p前缀形式意味着主要作用是返回自增自减后的结果副作用是自增自减1。所以会将*p的结果自增1后再赋值给变量num。整个表达式的运算过程是将*p的结果自增1后赋值给变量num。
关于运算符优先级和结合性的建议
运算符的优先级和结合性显然是运算符非常核心的重要概念但强行把这张表格记下来显然是不现实的所以我们给出以下总结和建议
一元运算符的优先级总是高于二元运算符。算术运算符的优先级仅次于单目运算符是二元运算符中优先级最高的。赋值运算符(包括复合赋值运算符)的优先级几乎是最低的。这很好理解如果运算还没结束赋值就完成了这不是想看到的。当不确定优先级或者为了代码清晰时使用括号来明确运算顺序。这不仅可以避免优先级引起的错误还可以使代码更易于理解。在实践中不要写出非常长非常复杂、可读性非常差的的表达式。优秀的程序员不应以写出别人不理解的代码为荣 如果表达式有过长的趋势不妨改成两个式子表达式中即便优先级没问题也最好用合适的小括号括起来关键位置明确代码意图增强代码可读性。 C语言经历了漫长的发展有很多关于复杂表达式的惯用法除此接触它们你可能会很头疼但基于习惯我们还是建议程序员记住它们。
以上。
五、赋值运算符
表达式的主要作用是计算出一个结果如果想要将这个结果保存下来以便接下来使用就需要用到赋值运算符了。
下面我们将赋值运算符分为两类来详细讲解赋值运算符
简单赋值运算符。也就是这里建议把它称为赋值号而不要直接叫等号。复合赋值运算符。包含, -, *, %等一系列复合赋值运算符。
1. 简单赋值运算符
在C语言中简单赋值操作符 是最基本的赋值运算符用于将右侧表达式的值赋给左侧的变量。这种操作是C语言中最常见的操作之一几乎出现在每个程序中。
赋值运算符组成的赋值表达式也具有两个作用即主要作用和副作用。
主要作用表达式的主要作用是计算值赋值表达式也不例外。但赋值表达式的值比较特殊它计算出来的值就是那个要赋给变量的值一般就是赋值表达式的右值。副作用**对于赋值表达式我们实际上更关注它的副作用。**赋值表达式的副作用就是会改变表达式左边变量的取值。
举例
(ch getchar()) ! \n这个表达式是我们前面讲基本数据类型时给出的一个惯用法现在我们来分析一下这个表达式
由于小括号的存在我们先分析表达式ch getchar() getchar()是函数调用表达式它的优先级最高先执行。函数调用会返回一个从stdin读取到的字符然后将该字符赋值给ch变量整个赋值表达式的值就是getchar()函数的返回值也就是这一次读到的字符 (ch getchar()) ! \n整体就是 判断getchar()函数的返回值也就是这一次读到的字符是否是换行符如果不是换行符则执行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 语言提供了一种更简洁的方式
自增运算符–自减运算符
自增自减都有前缀运算符(如i, --i)和后缀运算符(如 i, i–)两种不同的形式前后缀不同组成的表达式运算也不同。
大多数C语言学习者都会对前缀和后缀的不同运算方式头疼这里我们将彻底给大家讲明白这个语法。
我们以两个简单的例子来说明前缀和后缀运算符的区别
前缀自增自减具有右结合性
对于一个简单的前缀运算表达式--a
对于表达式--a我们先分析它的主要作用和副作用。 主要作用是返回变量a自减1后的结果这就是此表达式计算出来的一个值。副作用是变量a自减1。 前缀运算符的优先级非常高如果--a处于一个复杂的表达式当中那么它的主要作用就发挥作用。在整个表达式中它代表a自减1后的值。比如表达式是--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
表达式a同样具有主要作用和副作用 主要作用是直接返回变量a的值这就是此表达式计算出来的一个值。副作用是变量a自加1。 后缀运算符的优先级同样很高如果a处于一个复杂的表达式当中那么它的主要作用就发挥作用。在整个表达式中它代表a变量原本的值。比如表达式是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语言语法陷阱的考量。对于自增自减符号的使用我们给出以下建议
在for循环中使用自增自减符号是最常见的、且最清晰、稳定准确不出错的用法。自增自减运算符尽量不要用于连接表达式尽量单独成行这样就不会因副作用产生歧义。如果一定要将自增自减符号写在表达式中那么严禁被自增自减的变量在同一个表达式中出现多次。
七、关系运算符
在C语言中关系运算符用于比较两个值并根据比较的结果返回一个布尔值在C语言中1表示true0表示false。
C语言中的关系运算符包括
等于 ()C语言中把判等符号直接称之为等于这就是前面我们建议大家把赋值运算符称之为赋值号的原因。不等于 (!)大于 ()小于 ()大于或等于 ()小于或等于 ()
关系运算符都是比较简单的我们不再赘述。一些小的注意事项细节如下
关系运算符组成的表达式的主要作用是返回一个布尔值也就是两个操作数比较的结果。且它一般没有副作用关系运算符经常和逻辑运算符一起组成一个逻辑表达式(或称布尔表达式)结果返回一个布尔值。
八、逻辑运算符
C语言的逻辑运算符非常简单只有三个
短路与()当且仅当两个操作数都为真非零时结果为真。短路或(||)如果至少一个操作数为真非零结果为真。逻辑非(!)一元运算符只对单个操作数取反。如果操作数为真非零结果为假0如果操作数为假0结果为真非零。
注意C 语言会把任何零值当作 false任何非零值当作 true。
所谓的短路指的是
短路与()如果左操作数的值已经是假(零值)了那么右操作数则不进行计算直接返回false。短路或(||)如果左操作数的值已经是真(非零值)了那么右操作数则不进行计算直接返回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是一个正整数
i j将 i 的位模式向左移动 j 位。 移出去的高位丢弃并在低位补0。实际上该操作相当于将i乘以 2j如果没有溢出的话此表达式的主要作用是返回i移位运算后的结果此表达式一般没有副作用不会改变i变量的取值移位运算符没有赋值的作用 i j将 i 的位模式向右移 j 位。 移出去的低位丢弃如果i是无符号数或者非负值则在左边补 0。如果 i 是负值其结果会根据编译器平台实现不同而不同一些实现会在左边补 0一些实现会在左边补 1。在i是非负数的情况下实际上该操作相当于将i除以2j注意整数除法的结果还是整数此表达式的主要作用是返回i移位运算后的结果此表达式一般没有副作用不会改变i变量的取值移位运算符没有赋值的作用
注意事项/细节/建议
右移位运算符会根据平台实现不同会在左边补0或者补1这是非常坑爹的一个设计。因为当你尝试对一个负整数做右移运算时
有些平台(左边补0的)可能会将负整数右移后得到一个正数。而有些平台(左边补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 变成 11 变成 0。
i j对 i 和 j 的每一位进行逻辑与运算。只有两个数的相应位都为1时结果位才为1否则为0。
i | j对 i 和 j 的每一位进行逻辑或运算。只要两个数的相应位中有一个为1结果位就为1否则为0。
i ^ j对 i 和 j 的每一位进行异或运算。如果两个数的相应位一个为0另一个为1则结果位为1否则为0。(对应位不同结果是1)
注意
这些表达式的主要作为是返回位运算后得到的结果没有副作用不会改变任何一个操作数的值在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整除那就一直除以2while (n 1 n % 2 0) {n / 2;}// 判断最终结果是不是1return n 1;
}这种解法可以用左移位运算符稍作优化逆向思维一下。参考代码如下 代码块 16. 判断是否是2的幂-参考代码2
bool is_power_2(int n) {int x 1;// 只要x比n小就左移1位乘以2while (x n){x 1;} // 结束while的条件是x n// 如果n是2的幂那么x和n相等return n x;
}但这些解法都还不是最优的下面我们先观察一下2的幂整数的位模式
10001
20010
40100
81000
…
很显然一个整数如果它是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的最低有效位就是它。
举例
81000 值为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)那么它的相反数的补码就是
last set bit保持不变从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;这种方式也要求大家掌握因为它具有以下优点
代码可读性很强任何程序员一眼都能看明白。不限制被交换元素的类型可以交换任何类型的两个元素。
当然它的缺点是需要一个临时变量tmp这可能会导致额外的内存空间占用。
所以在早期出于节省内存空间简化代码的考量出现了下面利用异或位运算符交换两个元素的编程技巧(惯用法) 代码块 21. 实现两个数的交换-参考代码2
int a 100, b 200;a a ^ b;
b a ^ b;
a a ^ b;这种写法之所以能够完成两个数的交换利用的是异或运算符^的性质。计算过程分析如下
我们将原始的a 和 b的值记为a0b0
第一个表达式执行后的a和b的值记为a1和b1
…
于是整个计算过程为
第一个表达式执行完毕后a1 a0 ^ b0b1 b0第二个表达式执行完毕后 b2 a1 ^ b1 a0 ^ b0 ^ b1 a0 ^ b0 ^ b0 a0 ^ (b0 ^ b0) a0 ^ 0 a0。于是第二个表达式执行完毕后b的结果就等于原始a了。a2 a1 a0 ^ b0 第三个表达式执行完毕后 a3 a2 ^ b2 a0 ^ b0 ^ a0 (a0 ^ a0) ^ b0 0 ^ b0 b0。于是第三个表达式执行完毕后a的结果就等于原始b了。b3不变b的值仍然等于原始a的值。
以上三个表达式执行完毕后a和b在不利用额外空间的前提下就完成了交换nice
总结
交换元素是程序中特别常见和重要的操作在大多数情况下我们还是建议大家用临时变量的形式交换元素。因为它可读性更好且不受元素类型限制并且效率几乎没有差异只是占用了一些额外空间罢了。
而且用^交换元素还可能导致交换两个相同元素导致结果为0的情况出现这也为程序带来了极大的风险。
下一题
给定一个非空的整数数组nums已知某个元素只出现了一次其余元素均出现两次那么请你找出这个只出现一次的元素。
怎么做呢
使用异或运算即可因为异或运算有以下性质
自己和自己异或为00和别人异或都是别人。异或运算还满足交换律和结合律。
于是只需要将数组中的所有元素全部用^运算符链接起来这样最终的结果就是那个唯一的元素。
例如
数组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已知有两个元素只出现了一次其余元素均出现两次那么请你找出这两个只出现一次的元素。
既然有两个元素只出现一次那么求解这个问题就稍微复杂一些了。有两个比较好的手段可以参考
使用哈希表以元素-元素出现次数的形式存储键值对记录每一个元素出现的次数。 一次遍历数组填充哈希表再遍历一次哈希表即可找到只出现一次的两个元素。利用哈希表实现逻辑清晰直观代码也比较简洁是一个比较好的手段。时间复杂度和空间复杂度都是O(n)由于需要额外的哈希表数据结构空间复杂度比较高。 利用异或运算分组从而求解两个只出现一次的元素。 这种方式代码可能没有那么直观易懂但由于不占用额外内存空间复杂度是O(1)当然时间复杂度都是一样的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的算法即可。
于是我们的分组是这样的
a和b是不同的两个整数那么它们在last set bit位必然是不同的一个为0一个为1利用这个特点将数组分为两两组。
但是需要注意的是该分组不需要物理上分组只需要逻辑分组就可以了
找到last set bit位后遍历整数数组每个元素都和last set bit值做按位与运算
结果为0的是一组说明这组元素last set bit为0将它们都用^链接起来。最终结果就是一个只出现一次的元素。结果为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位的值是1a ^ nums[i];}else {// 此组元素在lsb位的值是0b ^ nums[i];}
}// 循环结束后a和b的值就是数组中两个唯一的元素以上。
