又一面试题,又一伪命题 - 关于C中字符数组逆序的方法

最近土豆同学经常去参加各种面试和笔试,而我也获益不少,得以见识到这些"题目"的诡异.这次听到的,是一个关于C语言中字符串逆序的问题.问题的核心是: 用什么办法,可以最高效的把一个char[]内容的顺序逆转? 最好是不用额外的存储空间.

我陷入了沉思.土豆同学问我的时候,一再强调既不需要用"额外的存储空间,也不需要加减或者异或运算";跟算法没关系,而是与类似语言特性的特性相关.想想也是,要逆序,无论如何也要遍历整个字符数组,不可能达到比O(n)还好的下限.但是不使用"额外"的空间...

并且,假设函数原型是类似: void reverse( char* str );

于是我只想到了两种可能,要么利用了数组之前(也就是例如"array[-1]"之类)的"安全空间",要么利用数组最后的"\0".当然,前者不是语言规定要有,而是编译器特定的行为,不靠谱;后者则是C语言里字符串的标准表示方式所规定的: 字符串以'\0'表示结束,可以放心利用.想到这里,土豆点头了,说面试官提出的就是这么一种使用结束位置上的0来完成交换的,"既没有使用额外的存储空间,又比加减或者异或运算快的方法".

...
我随即表示了反对.我从一开始就觉得这个方法很糟糕,所以没纳入考虑范围.不过面试官的思路我们也琢磨不透就是了.下面将说明我反对这种方法的理由.

把问题稍微简单化,将上面涉及的三种方案都写成代码如下.foo1()是面试官的建议版,foo2()是使用额外临时变量版,foo3()是运算版.

#include <stdio.h>
#include <string.h>

/*
 * reverse string via the terminating zero
 */
void foo1(char* a) {
    int len = strlen(a);
    int i;
    
    for (i = 0; i < len / 2; i++) {
        a[len] = a[i];
        a[i] = a[len - i - 1];
        a[len - i - 1] = a[len];
    }
    
    a[len] = 0;
}

/*
 * reverse string via a temp variable
 */
void foo2(char* a) {
    char temp;
    int len = strlen(a);
    int i;
    
    for (i = 0; i < len / 2; i++) {
        temp = a[i];
        a[i] = a[len - i - 1];
        a[len - i - 1] = temp;
    }
}

/*
 * reverse string via XORs
 */
void foo3(char* a) {
    int len = strlen(a);
    int i;
    
    for (i = 0; i < len / 2; i++) {
        a[len - i - 1] ^= a[i];
        a[i] ^= a[len - i - 1];
        a[len - i - 1] ^= a[i];
    }
}

void main(void) {
    /* declare few strings to be put into test */
    char* a = "abcd";
    char* b = "abcde";
    char* c = "abcdef";

    /* reverse the strings above */
    foo1(a);
    foo2(b);
    foo3(c);

    /* print results */
    printf("%s\n%s\n%s\n", a, b, c);
}

光从C语言的表象上看上面的代码,一时还真会觉得: foo1()与foo3()几乎一样,只是没有了"运算";而这两者又比foo2()要节省空间,因为没有多用一个"临时变量".

那么让我们来看看特定于一个编译器上,上面的代码实际表达了怎样的意思:
将上面的代码(str.c)以VC8的编译器编译,命令用的是: cl /Og /Ot /Ox str.c

foo1():

00401000  /$  8B4C24 04           mov ecx,dword ptr ss:[esp+4]
00401004  |.  55                  push ebp
00401005  |.  56                  push esi
00401006  |.  57                  push edi
00401007  |.  8BF9                mov edi,ecx
00401009  |.  8D57 01             lea edx,dword ptr ds:[edi+1]
0040100C  |.  8D6424 00           lea esp,dword ptr ss:[esp]
00401010  |>  8A07                /mov al,byte ptr ds:[edi]
00401012  |.  83C7 01             |add edi,1
00401015  |.  84C0                |test al,al
00401017  |.^ 75 F7               \jnz short str.00401010
00401019  |.  2BFA                sub edi,edx
0040101B  |.  8BC7                mov eax,edi
0040101D  |.  99                  cdq
0040101E  |.  2BC2                sub eax,edx
00401020  |.  8BE8                mov ebp,eax
00401022  |.  D1FD                sar ebp,1
00401024  |.  33F6                xor esi,esi
00401026  |.  85ED                test ebp,ebp
00401028  |.  7E 23               jle short str.0040104D
0040102A  |.  8D540F FF           lea edx,dword ptr ds:[edi+ecx-1]
0040102E  |.  8BFF                mov edi,edi
00401030  |>  0FB6040E            /movzx eax,byte ptr ds:[esi+ecx]
00401034  |.  88040F              |mov byte ptr ds:[edi+ecx],al
00401037  |.  0FB602              |movzx eax,byte ptr ds:[edx]
0040103A  |.  88040E              |mov byte ptr ds:[esi+ecx],al
0040103D  |.  0FB6040F            |movzx eax,byte ptr ds:[edi+ecx]
00401041  |.  8802                |mov byte ptr ds:[edx],al
00401043  |.  83C6 01             |add esi,1
00401046  |.  83EA 01             |sub edx,1
00401049  |.  3BF5                |cmp esi,ebp
0040104B  |.^ 7C E3               \jl short str.00401030
0040104D  |>  C6040F 00           mov byte ptr ds:[edi+ecx],0
00401051  |.  5F                  pop edi
00401052  |.  5E                  pop esi
00401053  |.  5D                  pop ebp
00401054  \.  C3                  retn

foo2():

00401060  /$  53                  push ebx
00401061  |.  56                  push esi
00401062  |.  57                  push edi
00401063  |.  8B7C24 10           mov edi,dword ptr ss:[esp+10]
00401067  |.  8BC7                mov eax,edi
00401069  |.  8D50 01             lea edx,dword ptr ds:[eax+1]
0040106C  |.  8D6424 00           lea esp,dword ptr ss:[esp]
00401070  |>  8A08                /mov cl,byte ptr ds:[eax]
00401072  |.  83C0 01             |add eax,1
00401075  |.  84C9                |test cl,cl
00401077  |.^ 75 F7               \jnz short str.00401070
00401079  |.  2BC2                sub eax,edx
0040107B  |.  8BD8                mov ebx,eax
0040107D  |.  99                  cdq
0040107E  |.  2BC2                sub eax,edx
00401080  |.  8BF0                mov esi,eax
00401082  |.  D1FE                sar esi,1
00401084  |.  33C9                xor ecx,ecx
00401086  |.  85F6                test esi,esi
00401088  |.  7E 1A               jle short str.004010A4
0040108A  |.  8D543B FF           lea edx,dword ptr ds:[ebx+edi-1]
0040108E  |.  8BFF                mov edi,edi
00401090  |>  8A1A                /mov bl,byte ptr ds:[edx]
00401092  |.  8A0439              |mov al,byte ptr ds:[ecx+edi]
00401095  |.  881C39              |mov byte ptr ds:[ecx+edi],bl
00401098  |.  8802                |mov byte ptr ds:[edx],al
0040109A  |.  83C1 01             |add ecx,1
0040109D  |.  83EA 01             |sub edx,1
004010A0  |.  3BCE                |cmp ecx,esi
004010A2  |.^ 7C EC               \jl short str.00401090
004010A4  |>  5F                  pop edi
004010A5  |.  5E                  pop esi
004010A6  |.  5B                  pop ebx
004010A7  \.  C3                  retn

foo3():

004010B0  /$  53                  push ebx
004010B1  |.  56                  push esi
004010B2  |.  8B7424 0C           mov esi,dword ptr ss:[esp+C]
004010B6  |.  8BC6                mov eax,esi
004010B8  |.  57                  push edi
004010B9  |.  8D50 01             lea edx,dword ptr ds:[eax+1]
004010BC  |.  8D6424 00           lea esp,dword ptr ss:[esp]
004010C0  |>  8A08                /mov cl,byte ptr ds:[eax]
004010C2  |.  83C0 01             |add eax,1
004010C5  |.  84C9                |test cl,cl
004010C7  |.^ 75 F7               \jnz short str.004010C0
004010C9  |.  2BC2                sub eax,edx
004010CB  |.  8BD8                mov ebx,eax
004010CD  |.  99                  cdq
004010CE  |.  2BC2                sub eax,edx
004010D0  |.  8BF8                mov edi,eax
004010D2  |.  D1FF                sar edi,1
004010D4  |.  33C9                xor ecx,ecx
004010D6  |.  85FF                test edi,edi
004010D8  |.  7E 20               jle short str.004010FA
004010DA  |.  8D5433 FF           lea edx,dword ptr ds:[ebx+esi-1]
004010DE  |.  8BFF                mov edi,edi
004010E0  |>  0FB60431            /movzx eax,byte ptr ds:[ecx+esi]
004010E4  |.  3002                |xor byte ptr ds:[edx],al
004010E6  |.  8A02                |mov al,byte ptr ds:[edx]
004010E8  |.  300431              |xor byte ptr ds:[ecx+esi],al
004010EB  |.  8A0431              |mov al,byte ptr ds:[ecx+esi]
004010EE  |.  3002                |xor byte ptr ds:[edx],al
004010F0  |.  83C1 01             |add ecx,1
004010F3  |.  83EA 01             |sub edx,1
004010F6  |.  3BCF                |cmp ecx,edi
004010F8  |.^ 7C E6               \jl short str.004010E0
004010FA  |>  5F                  pop edi
004010FB  |.  5E                  pop esi
004010FC  |.  5B                  pop ebx
004010FD  \.  C3                  retn

总体看看这三份代码,可以看到strlen函数都被inline进来了,所以三份代码的开头部分都有一个小循环,用于计算数组的长度(题外话: 我见的最多的strlen实现是用rep实现的啊...这里为什么是显式循环,怪哉).
接下来,先对比foo1()与foo3().主要关注靠近代码尾部的循环,发现内容几乎是一样的,除了foo3()里出现了3个xor,而foo1()里的对应位置上指令是mov.查阅x86的手册可以知道,在i486,i586等机器上mov mem, reg需要1个时钟周期,而xor mem, reg需要3个.确实,在这里运算与否有那么点细微的性能差距,但是根据80/20法则,这点差距是否真的能体现在程序的实际运行里值得疑问.
然后,再看上面那对与foo2()的比较.在C源代码中,可以看到我们声明了一个临时变量char temp,按照土豆同学所说的"一般常识",这个变量应该被分配在栈上了.可是事实上呢? 从编译出来的结果,可以看到这个temp从来没有被保存在栈上,而是直接分配在了寄存器上.有人要问"具体分配到哪个寄存器了呢?",答案更有趣:其实是分配到2个寄存器,al与bl上了;换句话说,"temp"这个变量就像存在有两份一样,分别储存了被交换的数据的两边.要说"占用了额外的存储空间",那也只能说是多用了个寄存器(仔细观察会发现其实也没多用),而这其实是个好事.在如此简单的函数中,寄存器不会不够用,而是有多的没用到;能有效分配寄存器,实际上让程序更高效了.
硬要比较这3个编译结果,应该能看出,foo2()才是最快而且不浪费(栈)空间的版本,另外两个都差不多.当然这是吹毛求疵了,实际运行的话很可能看不出什么性能差别.
需要重申的是,上面给出的结果是基于特定的编译器(VC8)与特定平台(Win32/i586)的组合下的结果,并不代表所有编译器的特性或所有平台的特性.

本来,只需要交换两个变量的值的话,用异或的方法是个相当不错的选择(本来xor reg, reg只需要1个时钟周期),但这里不巧遇上了数组而需要间接寻址,就(细微得)慢了.把结束标记的0(一个必须要分配,平时却没显著作用的空间)作为临时变量也是个不错的方案,但同样是遭遇到数组访问的问题而受到了拖累.反而在源代码里用了"额外的临时变量"的foo2()得到了不错的优化.这里的启示是: 没必要的时候,不要乱做优化.首先,凭"一般常识"而不是profile做出的优化决定很可能并不会给程序带来显著的性能提升.其次,耍小聪明的优化反而可能干扰编译器的判断,从而阻挠了一些优化,反而使代码变得更慢.那就得不偿失了.

面试官们的水平也还需要加强啊...那是哪间公司来着? 反正我没记住名字,算了.

说到这里倒是想起我以前用过的BlowfishJ,一个Java的Blowfish算法实现.它做了些极端的优化来试图克服Java本身性能上的缺陷.其中,在编码与解码的方法里,它都是先把一个长度为18的int[] (也就是那个P box)全部赋值给局部变量,然后再进入循环运算.在寄存器比较多的机器上,这确实有助于JITter的优化,尽可能利用寄存器而减少间接寻址.
所以说我实在挺不理解,在一些trivial的地方用尽心思去减少局部变量的使用,到底能有什么好处... = =

=================================================================

另外,既然提到这个话题,希望能引起注意的是异或交换方法的简写形式.相信有一定C++经验的人都会见过这个:

inline void swap(int& a, int& b) {
    a ^= b ^= a ^= b;
}

好吧,用异或运算本来就很难支持泛型(因为不是什么都能拿来算--除非cast成指针,那没话说了),所以这里只是简单的用了int型而没用template.这么写在C++里是(很可能)没问题,但并不意味着能广泛应用到其它C-like语言中.就不提C++的pass-by-reference语法不能在C或者Java里用,关键是中间的那句:

a ^= b ^= a ^= b;

要是在Java或者C#执行这句,就会发现b虽然正确的得到了a原本的值,但a在结束时却总是0.所以同一个简写,换到Java与C#中得这样写:

a = (b ^= a ^= b) ^ a;

原因也是与运算顺序的规定相关.C/C++中虽然没规定表达式的运算顺序,不过规定了赋值顺序一定是右结合的,所以那个简单版的简写(多半能)行得通(行不通的例子请参考这里).但Java/C#严格定义了表达式的运算顺序一定是从左向右,赋值顺序是从右向左,所以在遇到^=运算符时,需要首先将左操作数装载,再装载右操作数.这么做的后果是最左边的^=的左操作数的值是"旧"的,因而在简单版简写中等同于与自身做了异或,结果自然是0.
以JVM bytecode来说明,简单版简写编译出来是这样:

iload_1 // 关键差异
iload_2
iload_1
iload_2
ixor
dup
istore_1
ixor
dup
istore_2
ixor
istore_1

而带括号的版本是这样:

iload_2
iload_1
iload_2
ixor
dup
istore_1
ixor
dup
istore_2
iload_1 // 关键差异
ixor
istore_1

可以观察到注释为"关键差异"的行出现的位置的不同,导致了最终运算结果的不同.

下面具体举几个例子:
·可以用简单版简写的:
C/C++: (Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42 for 80x86测试)

#include <stdio.h>

void main(void) {
    int i = 1, j = 2, k = 3, l = 4;
        
    i ^= j ^= i ^= j;
    k = (l ^= k ^= l) ^ k;
    
    printf("i = %d, j = %d\nk = %d, l = %d",
        i, j, k, l); // i = 2, j = 1, k = 4, l = 3
}

D: (DMD 2.004测试)

void main(char[][] args) {
    int i = 1, j = 2, k = 3, l = 4;
        
    i ^= j ^= i ^= j;
    k = (l ^= k ^= l) ^ k;
    
    printf("i = %d, j = %d\nk = %d, l = %d",
        i, j, k, l); // i = 2, j = 1, k = 4, l = 3
}

TJS2: (KiriKiri 2.29测试)

[iscript]
tf.i = 1, tf.j = 2, tf.k = 3, tf.l = 4;
tf.i ^= tf.j ^= tf.i ^= tf.j;
tf.k = (tf.l ^= tf.k ^= tf.l) ^ tf.k;
[endscript]
tf.i = [emb exp="tf.i"], tf.j = [emb exp="tf.j"][r]
tf.k = [emb exp="tf.k"], tf.l = [emb exp="tf.l"][l][r]
; tf.i = 2, tf.j = 1, tf.k = 4, tf.l = 3

·需要用括号版简写的:
Java: (JRE 1.5.0/1.6.0测试)

public class Swap {
    public static void main(String[] args) {
        int i = 1, j = 2, k = 3, l = 4;
        
        i ^= j ^= i ^= j;
        k = (l ^= k ^= l) ^ k;
    
        System.out.printf("i = %d, j = %d\nk = %d, l = %d",
            i, j, k, l); // i = 0, j = 1, k = 4, j = 3
    }
}

C#: (.NET Framework 2.0测试)

using System;

public class Swap {
    public static void Main(string[] args) {
        int i = 1, j = 2, k = 3, l = 4;
        
        i ^= j ^= i ^= j;
        k = (l ^= k ^= l) ^ k;
    
        Console.WriteLine("i = {0}, j = {1}{2}k = {3}, l = {4}",
            i.ToString(), j.ToString(), Environment.NewLine,
            k.ToString(), l.ToString()); // i = 0, j = 1, k = 4, j = 3
    }
}

JavaScript: (IE6/IE7/FF2测试)

<html>
<body>
<script type="text/javascript">
var i = 1, j = 2, k = 3, l = 4;
i ^= j ^= i ^= j;
k = (l ^= k ^= l) ^ k;
document.write("i = " + i + ", j = " + j + "<br />k = " + k + ", l = " + l);
// i = 0, j = 1, k = 4, j = 3
</script>
</body>
</html>

评论

5 楼 lin5161678 2016-04-17  

    char* a = "abcd";  
    char* b = "abcde";  
    char* c = "abcdef";  

说一点 和 主题无关的事情
函数会修改 传入的字符串
但是 C/C++ 里面的字符串字面量 "abcd" 是不允许修改的
涉及到未定义行为
运行的时候 可能会崩溃 也可能什么事都没有

4 楼 lwwin 2011-11-15  

无聊来看看=w=

其实号称不分配空间，无论怎样都会需要int的临时空间－ －，个人感觉应该有可能仅使用1byte的空间来实现，没细细想了=3=，肯定不高效……

3 楼 zhoujianghai 2011-10-13  

#include <stdio.h> 
#include <string.h> 
 
void foo1(char* a)；

void main(void) { 
    /* declare few strings to be put into test */ 
    char* a = "hello"; 

    /* reverse the strings above */ 
    foo1(a); 
 
    /* print results */ 
    printf("%s\n", a); 
} 

/*
* reverse string via the terminating zero
*/ 
void foo1(char* a) { 
    int len = strlen(a); 
    int i; 
     
    for (i = 0; i < len / 2; i++) { 
        a[len] = a[i]; 
        a[i] = a[len - i - 1]; 
        a[len - i - 1] = a[len]; 
    } 
     
    a[len] = 0; 
} 

为什么这段代码在fedora14下却运行提示段错误啊。用gdb调试，好像是访问了未分配的内存。
刚在网上看到有人说把char *a = "hello"换成char c[] = "hello"; char *a = c;
char * c = "hello";告诉编译器，请求开辟一段空间放指针c，指向字符串常量“hello”，此时“hello”位于常量区，因而不能修改，如果修改发生则会发生错误。
char s[] = "hellp";这个是告诉编译器，请求开辟一段空间放字符数组s，并把字符串常量“hello”的值拷贝到字符数组中，此时该数组的值是可以修改的，但是修改的并不是原来的字符串常量“hello”。想想觉得也有些道理 ，不过为什么在公司的cygwin模拟环境下能正常编译运行呢~~这几天刚学c，不太明白其中的具体原因。请指教~~

2 楼 RednaxelaFX 2007-10-22  

恩,正是.不通过profile而是凭感觉就做的优化经常是糟糕的...

1 楼 Colorful 2007-10-21  

看的出来，楼主下功夫钻研了一番，:-)。
偶首先想到的就是foo2()，在我看来执着于这些细微的优化是舍本逐末的做法，过早的优化在C/C++是很大的问题。而且优化也要根据编译器特点来进行优化。
foo1,foo3我均不赞成。