探究C语言中循环的实现方式
开篇
几乎每种程序设计语言的语法中都会有语句的循环,跳转。像最为熟知的C语言便有 for 、 while 、 do---while 等等。这些循环一般都很容易理解和使用,对于程序中逻辑的实现也很有帮助。
只是很多人不曾知道,这些循环、跳转在计算机内部、在底层是如何实现的,于是在出现问题时还是没有好的解决办法,或者是虽然写出来程序,对于内部的逻辑,却还是隔了一层迷雾。
比如有人对这样一个问题:
for( i=0 ; i< 10 ; i++)
{
printf(”%i“,i);
}
for语句里面的 i++ 是什么时候执行的呢? 当循环开始时,是先执行括号里的 i++ 还是printf(”%i“,i)? 也就是说 ,第一个打印的数字是0 还是 1?
我相信这个问题很多人都遇到过,就是当for 循环结束后 i 的值到底是多少不是很确定,在这个问题上犯难,是在不值得。如果你也曾有过这种疑问,那么这篇文章就很值得继续看下去。
这篇文章将拨开迷雾,让你看到循环的本质。
这篇文章主要谈一下C中的这些循环, 跳转语句的内部实现机制。通过深入了解他们的内在,将让你在编程的时候逻辑更加清晰,出现问题的时候也更容易排查。
注:这篇文章中会涉及到一些基本的汇编知识,我们将通过分析 for 、 while 、 do---while 等的汇编表示形式,来弄清楚他们的实现机理。
if--else
if--else是基本的条件转移控制指令,也可以说是程序循环跳转实现的基础。
先看一个具体的例子,函数absdiff()比较两个参数x,y 的大小,返回他们差的绝对值。
我们创建了对于的C语言版本(a)、goto形式的版本(b)、 以及其对应的汇编形式(c):
创建goto版本是为了能更好的理解他的汇编形式。因为里面的goto语句很类似于汇编中的跳转语句。
(a)中 的C代码应该不用多做解释了吧,大家应该都能看懂。
(b)中的got0语句形式:第4 行是一个跳转语句,跳转到执行第8 行。也就是说当第3 行的条件满足的时候,跳转到第8 行执行。如果第3 行的条件不满足,则执行第 5 行的语句。 然后无条件跳转到代码的结尾:“ goto done;” 使用goto 语句通常被认为是一种不好的 编程风格,因为这样的语句通常难于调试和阅读,这里使用goto语句是为了构造出一种类似汇编实现的C语句。
(c)就是我们要讨论的重点了。其实条件跳转指令的汇编形式和他的goto形式有一定的相似之处。有语句跳转的时候都是这样的过程:先判断是否满足某个条件,如果满足,则跳到一个指定的的代码段继续执行程序,如果不满足,则执行另一条语句。
为了弄清楚它内部是如何实现的,现在我们来详细看一下他的汇编指令形式(c)
程序的 1 、2 行取得x y 的值。放在寄存器 edx eax 中,第三行比较x y 的大小(也就是比较edx eak 的大小)如果x > y 则跳到 .L2的地方执行(8 、9 行)执行x - y ,并将结果放在返回值中,然后程序顺序执行到程序结束处 .L3,反之,如果第三行判断结果是x<y ,则语句不会跳转,顺序执行y-x,并跳转到程序结束处 .L3.
现在,我们基本了解if --else 的执行机理了。主要是先判断条件值,从这个例子出发就是第 3 条语句: cmpl %eax,%edx。学过汇编的同学应该知道,cmpl是一条比较指令,他的执行会影响标志位。做个简单的假设: cmpl A,B 是比较A,B两个数的大小,比较结果存放在标志位 F 中,当A>B时,F为0,A<BF为1。 后面的jge .L是跳转语句,他的执行是和上一步比价的结果相关的,这里也就反映在标志位F 当中。当F 为1时(A<B),则跳转到 .L2执行 B-A。当比较结果为A>B 查看后标志位为0,则jge不跳转, 程序继续往下执行。
C中的if --else 的通用模板是这样的:
这里的 test-expr 是一个整数表达式,它的值为真(1、>0)则会执行第一个分支语句 , 否则执行第二个。但不管怎么样,都只会执行其中的一个。
对于这种模板,汇编的实现通常会用下面的形式:(这里用C语言描述)
汇编器会为 then-statement 和else-statement产生各自的代码快 ,通过条件跳转来执行相应的代码。
注意:程序并不是智能的,执行跳转的时候只会有两种判断(真和假),而且内部的跳转形式都是基于 go to 模式。所以说虽然goto 在编程中要少用,但在理解程序跳转的时候还是很重要的。我想因为goto 的实现方式和程序最终的实现方式如此的相似,才在C中引入goto 吧。
do---while
C中提供了多中循环结构,do-while while 和 for ,然而汇编中没有相应的指令存在。通过上面对 if -else 的分析, 已经知道了 C 中条件跳转在汇编中的基本实现方式(goto),现在要讨论的这些循环,在循环中都有一个条件判断的环节,当条件满足时,继续循环体, 如果条件不满足,则跳出循环体。和if-else 不同的在于这里的条件表达式可能会有改变,也就是每次判断的条件和上次不同。
只要理解了上面的if-else 的内容 ,其他的循环都能通过对if -else 的改进来实现。先给出这些循环的goto 形式,就能很快推测出其内部的实现方式。
通用形式:
do-while的通用形式如下:
do
body-staement
while(test-expr)
这个循环的效果就是反复执行 body-staement,对test-expr进行求值,如果求值结果不是0 则继续执行。可以看到,body-statement至少会被执行一次。
do-while 的通用形式可翻译为 如下所示的goto 语句:
loop:
body-statement
t=test-expr;
if(t)
goto loop;
对于上面的goto形式, 可以先想想汇编会是如何实现的:把loop里的代码放在一个单独的代码段里面(包含if 的判断跳转部分)程序顺序执行下来,第一次执行不用判断条件。执行玩body-statement后判断条件,如果满足,则继续这个循环。
好了,下面看一个具体的例子:
这是一个计算阶乘的函数实现,
(a)是c代码,
(c)是对应的汇编形式
(b)是汇编中寄存器和变量的映射关系
(a)中的代码比较简单就不在解释了。现在看(c)中的代码:
第 1 行是获得函数参数n的值,放在寄存器 edx 中,第 2 行设置 result =1 第 3 行的 L2 表明这是一个循环体。 (c) 中的第 4、 5 行实现了 (a)中 5、 6 行的功能。
(c)中的第6 行判断循环的条件,如果条件满足,则执行第 7 行 的跳转语句。
和do- while的通用形式所描述的一样,body-staement至少会被执行一次,这从汇编代码中也有体现,观察循环体 L2,在L2 没有关于L2 的跳转代码,也就是说在程序顺序往下执行的情况下,L2 至少会被执行一次,然后在 L2 内部判断是否继续执行循环体 L2。
while
whil循环和do-while类似,他的通用形式如下:
while(test-expr)
body-statement
和do-while不同的是,他先对test-expr求值,所以body-statement可能一次都不被执行。将while翻译为机器码有多种方法,其中一种常见的方式i就是把他翻译成do-while的形式。在第一次执行循环体之前加一个判断条件,如果条件满足,则进入do-while的循环体,如果不满足,直接跳过循环体。也就是上面说的:body-statement可能一次都不被执行。
下面先把while转换为do-while循环:
if(!test-expr)
goto done;
do
body-statement
while(test-expr);
done;
接下来可以吧这个do-while循环转换为goto语句:
t=test-expr;
if(!t)
goto done;
loop:
body-statement
t=test-expr;
if(t)
goto loop;
done
这个goto的版本和do-while的版本只是在循环体loop的前面加上了一个判断条件,如果条件满足, 就执行上面中的do-while循环体,如果不满足,直接跳过循环。
通过上面的goto版本,现在应该可以想一下while 的 汇编是如何实现了吧:
现在就可以猜测,while 的汇编只是在do-while汇编的基础上做出一些改动:在循环体loop之前加一个判断条件,如果条件成立,则执行loop,不成立则跳过loop。
下面还通过一个具体例子来说:
还是计算n 的阶乘,不过这次是用while实现
下面是C代码:
这很简单,就不做解释了,下面看他的goto形式:
和上面描述的一样,在3、4 行中加入了条件判断,如果条件不满足 第5行直接跳攻loop循环体,只有当条件满足时才进入循环体loop。再看loop中,7、8 行执行计算阶乘的必要操作,9、10行通过判断test-expr 决定是否继续循环。
好,下面来看while的汇编形式:
现在看汇编代码应该比较有经验了吧,这里的3、4 行执行条件判断,决定是否进入循环体.L10,相当于goto版本中的4、5 行,如果不满足,直接跳转到.L7的位置。
再看一下.L10 循环体:6、7 行执行阶乘的必要操作,相当于goto中的 7、8 行,这里的8、9 行判断循环是否继续,相当于goto中的9、10行。
for循环
for循环的通用形式如下;
for(init-expr ; test-expr ; update-expr)
body-statement
大概在学C的时候会提到for 循环可以用while 来表示:
init-expr
while(test-expr){
body-statement
update-expr
}
程序首先初始化表达式init-expr的值,然后进入循环,再循环中先对测试值test-expr求值,如果为假,则退出循环,否则执行循环体body-statement,并更新表达式update-expr的值。
基于前面讲过的do-while到while的转换,先给出do-whle形式:
然后将它转为goto代码:
和上面一样,我们将用一个实例来说明问题:
考虑用for 循环写的阶乘函数
用for循环写的计算阶乘的函数是从2 开始,这和前面的从1开始不同,不过这并不影响其逻辑实现的结构,这段代码中,for循环的组成如下:
通过上面的分析,可以得到其goto形式:
到现在为止 ,已经在实例中给出了他的C 形式和goto形式,现在请看他的汇编形式:
上面都解释了很多,这里就不在解释这个汇编指令了,通过上面应该都能看懂。
开始的问题
到现在,应该弄清楚文章开头所说的问题了吧
for( i=0 ; i< 10 ; i++)
{
printf(”%i“,i);
}
现在应该了解什么时候执行 i++ 设么时候执行printf(”%i“,i); 了吧。
按照我们的分析,执行顺序应该是这样的:
1、 初始化 i=0
2、判断条件是否满足 i<10 是否成立
3、如果成立则执行循环体printf(”%i“,i); 并执行自加运算 i++
可以这段代码在自己的编译器中运行一下,看首先打印出来的是0 还是1 (按照我们的分析,应该从0 开始答应哦)
小结
其实这篇文章阐述的道理很简单,就是C 语言中循环的实现问题。如果你在linux环境下操作的话,要理解这一部分就更容易了,在linux下可以直观的看到一个程序编译后的汇编形式,在自己电脑上分析自己的程序,这样学起来才更有兴趣,更深刻。
简单介绍:
linux下编译器:GCC、
可执行文件查看器:objdump、还有一个好像是 elfread,不确定了。
如果调试上面的for语句的话,可以用gdb调试器,这样能让程序一步步执行,并且跟踪变量的值。关于linux下的这些命令这里不是本文重点,不再介绍。
全文完。
一条鱼、yanlingyin@ 博客园
尹雁铃 2012-3-27
E-mail:yanlingyin@yeah.net
上一篇: 理解C语言中的循环结构 - 第四部分
下一篇: while循环在C语言中的应用
推荐阅读
-
探究C语言中循环的实现方式
-
C语言中循环的实现方式
-
探究C语言中的循环控制语句
-
重写的标题:在C语言中实现数字和字符串的循环位移操作
-
F#探险之旅(二):函数式编程(上)-函数式编程范式简介 F#主要支持三种编程范式:函数式编程(Functional Programming,FP)、命令式编程(Imperative Programming)和面向对象(Object-Oriented,OO)的编程。回顾它们的历史,FP是最早的一种范式,第一种FP语言是IPL,产生于1955年,大约在Fortran一年之前。第二种FP语言是Lisp,产生于1958,早于Cobol一年。Fortan和Cobol都是命令式编程语言,它们在科学和商业领域的迅速成功使得命令式编程在30多年的时间里独领风骚。而产生于1970年代的面向对象编程则不断成熟,至今已是最流行的编程范式。有道是“*代有语言出,各领风骚数十年”。 尽管强大的FP语言(SML,Ocaml,Haskell及Clean等)和类FP语言(APL和Lisp是现实世界中最成功的两个)在1950年代就不断发展,FP仍停留在学院派的“象牙塔”里;而命令式编程和面向对象编程则分别凭着在商业领域和企业级应用的需要占据领先。今天,FP的潜力终被认识——它是用来解决更复杂的问题的(当然更简单的问题也不在话下)。 纯粹的FP将程序看作是接受参数并返回值的函数的集合,它不允许有副作用(side effect,即改变了状态),使用递归而不是循环进行迭代。FP中的函数很像数学中的函数,它们都不改变程序的状态。举个简单的例子,一旦将一个值赋给一个标识符,它就不会改变了,函数不改变参数的值,返回值是全新的值。 FP的数学基础使得它很是优雅,FP的程序看起来往往简洁、漂亮。但它无状态和递归的天性使得它在处理很多通用的编程任务时没有其它的编程范式来得方便。但对F#来说这不是问题,它的优势之一就是融合了多种编程范式,允许开发人员按照需要采用最好的范式。 关于FP的更多内容建议阅读一下这篇文章:Why Functional Programming Matters(中文版)。F#中的函数式编程 从现在开始,我将对F#中FP相关的主要语言结构逐一进行介绍。标识符(Identifier) 在F#中,我们通过标识符给值(value)取名字,这样就可以在后面的程序中引用它。通过关键字let定义标识符,如: let x = 42 这看起来像命令式编程语言中的赋值语句,两者有着关键的不同。在纯粹的FP中,一旦值赋给了标识符就不能改变了,这也是把它称为标识符而非变量(variable)的原因。另外,在某些条件下,我们可以重定义标识符;在F#的命令式编程范式下,在某些条件下标识符的值是可以修改的。 标识符也可用于引用函数,在F#中函数本质上也是值。也就是说,F#中没有真正的函数名和参数名的概念,它们都是标识符。定义函数的方式与定义值是类似的,只是会有额外的标识符表示参数: let add x y = x + y 这里共有三个标识符,add表示函数名,x和y表示它的参数。关键字和保留字关键字是指语言中一些标记,它们被编译器保留作特殊之用。在F#中,不能用作标识符或类型的名称(后面会讨论“定义类型”)。它们是: abstract and as asr assert begin class default delegate do donedowncast downto elif else end exception extern false finally forfun function if in inherit inline interface internal land lazy letlor lsr lxor match member mod module mutable namespace new nullof open or override private public rec return sig static structthen to true try type upcast use val void when while with yield 保留字是指当前还不是关键字,但被F#保留做将来之用。可以用它们来定义标识符或类型名称,但编译器会报告一个警告。如果你在意程序与未来版本编译器的兼容性,最好不要使用。它们是: atomic break checked component const constraint constructor continue eager event external fixed functor global include method mixinobject parallel process protected pure sealed trait virtual volatile 文字值(Literals) 文字值表示常数值,在构建计算代码块时很有用,F#提供了丰富的文字值集。与C#类似,这些文字值包括了常见的字符串、字符、布尔值、整型数、浮点数等,在此不再赘述,详细信息请查看F#手册。 与C#一样,F#中的字符串常量表示也有两种方式。一是常规字符串(regular string),其中可包含转义字符;二是逐字字符串(verbatim string),其中的(")被看作是常规的字符,而两个双引号作为双引号的转义表示。下面这个简单的例子演示了常见的文字常量表示: let message = "Hello World"r"n!" // 常规字符串let dir = @"C:"FS"FP" // 逐字字符串let bytes = "bytes"B // byte 数组let xA = 0xFFy // sbyte, 16进制表示let xB = 0o777un // unsigned native-sized integer,8进制表示let print x = printfn "%A" xlet main = print message; print dir; print bytes; print xA; print xB; main Printf函数通过F#的反射机制和.NET的ToString方法来解析“%A”模式,适用于任何类型的值,也可以通过F#中的print_any和print_to_string函数来完成类似的功能。值和函数(Values and Functions) 在F#中函数也是值,F#处理它们的语法也是类似的。 let n = 10let add a b = a + blet addFour = add 4let result = addFour n printfn "result = %i" result 可以看到定义值n和函数add的语法很类似,只不过add还有两个参数。对于add来说a + b的值自动作为其返回值,也就是说在F#中我们不需要显式地为函数定义返回值。对于函数addFour来说,它定义在add的基础上,它只向add传递了一个参数,这样对于不同的参数addFour将返回不同的值。考虑数学中的函数概念,F(x, y) = x + y,G(y) = F(4, y),实际上G(y) = 4 + y,G也是一个函数,它接收一个参数,这个地方是不是很类似?这种只向函数传递部分参数的特性称为函数的柯里化(curried function)。 当然对某些函数来说,传递部分参数是无意义的,此时需要强制提供所有参数,可是将参数括起来,将它们转换为元组(tuple)。下面的例子将不能编译通过: let sub(a, b) = a - blet subFour = sub 4 必须为sub提供两个参数,如sub(4, 5),这样就很像C#中的方法调用了。 对于这两种方式来说,前者具有更高的灵活性,一般可优先考虑。 如果函数的计算过程中需要定义一些中间值,我们应当将这些行进行缩进: let halfWay a b = let dif = b - a let mid = dif / 2 mid + a 需要注意的是,缩进时要用空格而不是Tab,如果你不想每次都按几次空格键,可以在VS中设置,将Tab字符自动转换为空格;虽然缩进的字符数没有限制,但一般建议用4个空格。而且此时一定要用在文件开头添加#light指令。作用域(Scope)作用域是编程语言中的一个重要的概念,它表示在何处可以访问(使用)一个标识符或类型。所有标识符,不管是函数还是值,其作用域都从其声明处开始,结束自其所处的代码块。对于一个处于最顶层的标识符而言,一旦为其赋值,它的值就不能修改或重定义了。标识符在定义之后才能使用,这意味着在定义过程中不能使用自身的值。 let defineMessage = let message = "Help me" print_endline message // error 对于在函数内部定义的标识符,一般而言,它们的作用域会到函数的结束处。 但可使用let关键字重定义它们,有时这会很有用,对于某些函数来说,计算过程涉及多个中间值,因为值是不可修改的,所以我们就需要定义多个标识符,这就要求我们去维护这些标识符的名称,其实是没必要的,这时可以使用重定义标识符。但这并不同于可以修改标识符的值。你甚至可以修改标识符的类型,但F#仍能确保类型安全。所谓类型安全,其基本意义是F#会避免对值的错误操作,比如我们不能像对待字符串那样对待整数。这个跟C#也是类似的。 let changeType = let x = 1 let x = "change me" let x = x + 1 print_string x 在本例的函数中,第一行和第二行都没问题,第三行就有问题了,在重定义x的时候,赋给它的值是x + 1,而x是字符串,与1相加在F#中是非法的。 另外,如果在嵌套函数中重定义标识符就更有趣了。 let printMessages = let message = "fun value" printfn "%s" message; let innerFun = let message = "inner fun value" printfn "%s" message innerFun printfn "%s" message printMessages 打印结果: fun value inner fun valuefun value 最后一次不是inner fun value,因为在innerFun仅仅将值重新绑定而不是赋值,其有效范围仅仅在innerFun内部。递归(Recursion)递归是编程中的一个极为重要的概念,它表示函数通过自身进行定义,亦即在定义处调用自身。在FP中常用于表达命令式编程的循环。很多人认为使用递归表示的算法要比循环更易理解。 使用rec关键字进行递归函数的定义。看下面的计算阶乘的函数: let rec factorial x = match x with | x when x < 0 -> failwith "value must be greater than or equal to 0" | 0 -> 1 | x -> x * factorial(x - 1) 这里使用了模式匹配(F#的一个很棒的特性),其C#版本为: public static long Factorial(int n) { if (n < 0) { throw new ArgumentOutOfRangeException("value must be greater than or equal to 0"); } if (n == 0) { return 1; } return n * Factorial (n - 1); } 递归在解决阶乘、Fibonacci数列这样的问题时尤为适合。但使用的时候要当心,可能会写出不能终止的递归。匿名函数(Anonymous Function) 定义函数的时候F#提供了第二种方式:使用关键字fun。有时我们没必要给函数起名,这种函数就是所谓的匿名函数,有时称为lambda函数,这也是C#3.0的一个新特性。比如有的函数仅仅作为一个参数传给另一个函数,通常就不需要起名。在后面的“列表”一节中你会看到这样的例子。除了fun,我们还可以使用function关键字定义匿名函数,它们的区别在于后者可以使用模式匹配(本文后面将做介绍)特性。看下面的例子: let x = (fun x y -> x + y) 1 2let x1 = (function x -> function y -> x + y) 1 2let x2 = (function (x, y) -> x + y) (1, 2) 我们可优先考虑fun,因为它更为紧凑,在F#类库中你能看到很多这样的例子。 注意:本文中的代码均在F# 1.9.4.17版本下编写,在F# CTP 1.9.6.0版本下可能不能通过编译。 F#系列随笔索引页面
-
探究C语言中实现大顶堆的方法:第二部分-入堆操作