一个交换两寄存器内容的技巧

[Atommann]

Dear all,

上周去一家公司面试，其中一问题是：写一个函数，判断一个 unsigned long int
整数是不是一个回文数(palindrome)。比如 123454321 是回文数，而 123456789 则不是。

一开始，我考虑有没有什么巧妙的数学方法可以解决这个问题。花了很多时间思考，没有结果(要知道，在上机面试时这样干是致命的！)。还是回到回文数的性质上来(顺读反读都一样)，一个可行的算法是这样的：

1. 把整数转换成字符串
2. 起始端和尾端挨个字符相比较，一旦发现字符不相等就退出循环(不是回文数)

本来上机操作是在面试公司的 Windows 机器上操作，自己带了电脑，习惯 Linux 命令行和
vim，就开始在自己的电脑上做题。立即就发现 Linux 上没有 ltoa
函数(长整型转字符串)，一时半会儿又写不出这个函数，sprintf 也忘记了。这个题就做不下去了。

自然，面试没有通过（因为我的 C 语言基础知识学得并不扎实，又很长一段时间都没有写代码了，再加上面试前未作准备）。从公司出来已是正午，准备去
McDonald 吃个饭，却发现人满为患，室外又酷热难当，心想，很好，我可以找个咖啡厅再研究一下面试的题目，这样正好可以避开这个人多的时间段，稍后再回来吃饭。

前行几步就是一个咖啡厅，要了一杯 Espresso，便坐下来打开电脑开始研究面试题。研究了一会儿又想到了老朋友们，遂打开 IRC
#szdiy 频道和 Mitch, Terry, NalaGinrut 又是一阵神聊(还好他们都在线)，也问了一些问题。时间差不多了，又回到
McDonald，很快吃完了午餐，然后又开始研究面试题/IRC，半个小时的免费上网时间很快就 times up
了，决定收工回家，oops，走着走着，快到地铁口时居然发现自己的水杯落在咖啡厅了，只得回去。

店员见我回来，立即把杯子递过来，连声道谢后决定再呆一会儿(因为还想着那些问题)，又要了一杯
Espresso(一是这个最便宜，二是我有点强迫症，以前在餐厅吃饭每次都吃同一种，直到吃到不想吃……)。搜索网络，Aha，发现今天面试我的题目居然来自正面这篇文章：

A ‘C’ Test: The 0×10 Best Questions for Would-be Embedded Programmers
http://www.rmbconsulting.us/a-c-test-the-0x10-best-questions-for-would-be-embedded-programmers

怪不得这家公司的面试题和另一家公司有很多雷同之处 :)

这封邮件写得越来越偏题了，又回到最初的回文数判断问题，另一个算法是：

1. 把整数转换成字符串
2. 反转字符串(用 strrev 函数)
3. 比较反转后和反转前的字符串(用 strcmp 函数)

GCC 的标准库里没有 strrev 函数，google 到下面这个实现(来自
http://blog.csdn.net/turingo/article/details/8124432 )

char* strrev(char* s)
{
/* h指向s的头部 */
char* h = s;
char* t = s;
char ch;

/* t指向s的尾部 */
while(*t++){};
t--; /* 与t++抵消 */
t--; /* 回跳过结束符'\0' */

/* 当h和t未重合时，交换它们所指向的字符 */
while(h < t)
{
ch = *h;
*h++ = *t; /* h向尾部移动 */
*t-- = ch; /* t向头部移动 */
}

return(s);
}

有意思。很快，google 把我带到了 http://www8.cs.umu.se/~isak/snippets/ 里的 strrev.c

char *strrev(char *str)
{
char *p1, *p2;

if (! str || ! *str)
return str;
for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
{
*p1 ^= *p2;
*p2 ^= *p1;
*p1 ^= *p2;
}
return str;
}

一看，傻眼了。for 循环里三句话就搞定了头和尾的字符交换，心想，这个是神马招式？晚上回到家，到一个字符串实例 "hello"
按这个算法推了一番，果然可以反转字符串。问题想不通，就连陪孩子去超市逛街都在想这个问题。最终还是在冲凉的时候把这个算法想通了 :)

这是个妙招啊，一定在某个地方有记录，翻开 "Hacker's Delight"
中文版《高效程序的奥秘》(顺便吐槽：中文版翻译质量堪忧！欲购请慎重！http://book.douban.com/subject/1159177/
)，果然，在第 30 页找到了这个 hack，其历史至少可以追溯到 1961 年 IBM 的一个编程课程的内容。

随便提及，以前读 "Hackers: Heroes of the Computer Revolution - 25th
Anniversary Edition" 中文版《黑客:计算机革命的英雄》25周年版(
http://book.douban.com/subject/6860890/ 柴火创客空间 www.chaihuo.org 有 4
本该书供出售)里面提到 MIT AI Lab 那帮传奇 hacker 们的各种 hacks，顺书搜索，他们的工作(称为
HAKMEM)居然全部记录在案，见 http://en.wikipedia.org/wiki/HAKMEM

--
Best regards,
Atommann
http://www.atommann.com

[crquan]

2013/7/16 Atommann <atom...@gmail.com>:

就是不用中间temp变量地 交换两个变量的值。

Search for "swap variables without temp"

http://en.wikipedia.org/wiki/XOR_swap_algorithm
http://betterexplained.com/articles/swap-two-variables-using-xor/

Would you really use this?

No way. This is a cool trick, but don’t write this as an actual swap function.

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.

不过就判断回文数而言，它只需要一个结果 true or false, 你加入 strrev 和 strcmp 岂不是增加了计算量吗？ 还需要额外的内存复制字条串用于反转。 判断回文数有这个for 循环里面写上 if 语句判断，如果不相等直接返回 false; 在判断全部结束后 for 循环外面返回 true

[Yuan Yijun]

想了一下，一个 unsigned long int 的长度是 10 个数位，那么用 BCD 编码，可以存到 5 个字节里。操作这种字节数组的代码怎么写？有没有更省空间的做法？

rae 真是很有经验，先搞清楚需求，比埋头写代码要好。 atom 想到字符串，有些杀鸡用牛刀的感觉，因为字符串的回文可以处理无限长度，而 int 不需要

[taocp]

这种数还有一个特点点，旋转后与原来是一样的。 循环取模10的余数，由余数重新构造一个数，与原来的数相比

send by my HTC G12 .

--
您收到此邮件是因为您订阅了 Google 网上论坛的“Shenzhen (深圳) Linux Unix User Group”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 szlug+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。

[Atommann]

在 2013年7月17日上午8:18，taocp <mojied...@gmail.com> 写道：
> 这种数还有一个特点点，旋转后与原来是一样的。 循环取模10的余数，由余数重新构造一个数，与原来的数相比

你说的应该是下面这个方法：

bool is_pal(unsigned long val)
{
unsigned long temp, reverse = 0;

temp = val;

// reverse the number
while (temp != 0)
{
reverse = reverse * 10;
reverse = reverse + temp%10;
temp = temp/10;
}

if (val == reverse) // compare it with the original number
return 1;
else
return 0;

[Nala Ginrut]

这个算法并不需要strrev，不需要任何拷贝操作，只要判断1和n，2和n-1...直到n/2就可以，不必考虑奇偶。
回文数判定转成字符串是高效简洁的方法，使用动态类型的语言来做的话，一个非常大的整数(超过20位)只要0.007秒，可以看做是个足够好的方法

--
--
You received this message because you are subscribed to the Google
Groups "Shenzhen DIY community" group.
To post to this group, send email to sz...@googlegroups.com
To unsubscribe from this group, send email to
szdiy+un...@googlegroups.com
For more options, visit this group at
http://www.szdiy.org
http://groups.google.com/group/szdiy?hl=zh-CN
---
您收到此邮件是因为您订阅了 Google 网上论坛的“Shenzhen DIY community”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 szdiy+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。

[mjxian]

�� 2013-7-17 1:43, crquan ���������:

> ����˼���ܿ죬google ���Ҵ��� http://www8.cs.umu.se/~isak/snippets/ ��� strrev.c

>
> char *strrev(char *str)
> {
>       char *p1, *p2;
>
>       if (! str || ! *str)
>             return str;
>       for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
>       {
>             *p1 ^= *p2;
>             *p2 ^= *p1;
>             *p1 ^= *p2;

���Dz����м�temp������ ��������������ֵ��

Search for "swap variables without temp"

http://en.wikipedia.org/wiki/XOR_swap_algorithm
http://betterexplained.com/articles/swap-two-variables-using-xor/

Would you really use this?

No way. This is a cool trick, but don��t write this as an actual swap function.

�Ҽǵ�CSAPP���ᵽ�����ַ���������Ҳָ�������������ܰ����ֻ������˼���ѡ�����ë��Ӧ������ֲ�ϲ���ȫ������һЩ��Դ�dz����ŵ� ��Ƭ��ϵͳ���ܻ������õġ�

[gmail]

使用awk也可以测试一个简单的字符串是否为回文

#!/bin/bash

echo $1 |awk -F '' '

BEGIN {_isPal=1}

{

for(i=1;i<=NF/2;i++)

{

        if($i!=$(NF-i+1))

        {

                _isPal=0

 exit

        }

}

}

END { 

        if(_isPal==1)

                print "It is a palindrome"

        else

                print "It is not palindrome"

}

'

 

---

gmail

 

发件人： Atommann

发送时间： 2013-07-17 00:28

收件人： Shenzhen DIY Lab; szlug

主题： [szlug] 一个交换两寄存器内容的技巧

[Weiguo Zhu]

反转会溢出，在该题中不影响结果，但是总让人觉得...写一个与溢出无关的

 1 bool helper(int x, int d) {
 2     if (x<10) return true;
 3     if (x%10 != x/d) return false;
 4 
 5     x /= d;
 6     d /= 10;
 7     return helper(x%d, d/10);
 8 }
 9 bool isPalindrome(int x) {
10     int d;
11     for (d=1; x/d>9; d*=10);
12     return x>=0 && helper(x, d);
13 }

[Atommann]

在 2013年7月17日上午8:47，Nala Ginrut <nalag...@gmail.com> 写道：
> 这个算法并不需要strrev，不需要任何拷贝操作，只要判断1和n，2和n-1...直到n/2就可以，不必考虑奇偶。

回文数判断确实不需要 strrev，我去研究 strrev
的动机是这样的：因为看到一个判断方法是把整数反转，然后比较原始数和反转后的数，这自然会让人想到“嗯，我把数字转成字符串后也可以用
string.h 中的库函数把字符串反转，再比较，这也是一个可行的方法”，于是就 #include <string.h> 调用
strrev，编译器提示我 undefined reference to `strrev'

这表明标准 glibc 里面没有 strrev
这个函数，既然没有，那如果以后当我要反转字符串的时候怎么实现一个呢？这里的学习研究源自面试这个事件，但已经走得更远。

> 回文数判定转成字符串是高效简洁的方法，使用动态类型的语言来做的话，一个非常大的整数(超过20位)只要0.007秒，可以看做是个足够好的方法

[Atommann]

在 2013年7月17日上午1:43，crquan <crq...@gmail.com> 写道：
>
> 就是不用中间temp变量地 交换两个变量的值。
>
> Search for "swap variables without temp"
>
> http://en.wikipedia.org/wiki/XOR_swap_algorithm
> http://betterexplained.com/articles/swap-two-variables-using-xor/

谢谢，好资料。

> Would you really use this?
>
> No way. This is a cool trick, but don’t write this as an actual swap
> function.
>
>> Debugging is twice as hard as writing the code in the first place.
>> Therefore, if you write the code as cleverly as possible, you are, by
>> definition, not smart enough to debug it.
>
>
>
> 不过就判断回文数而言，它只需要一个结果 true or false, 你加入 strrev 和 strcmp 岂不是增加了计算量吗？

在给 NalaGinrut 那个回复里说明了这样做的动机，just for fun.

> 还需要额外的内存复制字条串用于反转。 判断回文数有这个for 循环里面写上 if 语句判断，如果不相等直接返回 false; 在判断全部结束后 for
> 循环外面返回 true

在尝试用 strrev, strcmp 来解决回文数问题时，反复尝试，确实要复制字符串才行。

[Nala Ginrut]

On Wed, 2013-07-17 at 00:28 +0800, Atommann wrote:
> for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
> {
> *p1 ^= *p2;
> *p2 ^= *p1;
> *p1 ^= *p2;
> }
> return str;
> }

话说我经常用另一个更装B的写法：

#define XCHG(a,b) ((a)^=(b)^=(a)^=(b))

XCHG(*p1, *p2);

[Weiguo Zhu]

aha！没过多久逮到这个算式了

如果p1==p2怎么办，所以需要调用者自己来保证不等？

[Nala Ginrut]

On Wed, 2013-07-17 at 12:58 +0800, Weiguo Zhu wrote:
> aha！没过多久逮到这个算式了
> 如果p1==p2怎么办，所以需要调用者自己来保证不等？
>

你是说*p1==*p2？
那个应该没有关系，不影响计算

不过发现新问题了，如果直接交换两个int是没有问题的，但是用这种连等式带指
针的写法发现有问题：
int a=1,b=2;
int *p1=&a, *p2=&b;
XCHG(*p1,*p2)的话，p1指向的内容会变成0，
而
XCHG(a,b)就没有问题
另外，展开写是没问题的，写成连等式就有问题，看了下汇编，有十几行的差异

分析了一下，搞不好是gcc的bug，因为加一个优化参数 -O (随便O几)都可以出正
确结果

大家都来测测看，我的环境是opensuse-12.2, gcc-4.7


atommann你又发现新大陆了 （哥伦布去哪里了？）

[Nala Ginrut]

On Wed, 2013-07-17 at 13:30 +0800, Nala Ginrut wrote:
> On Wed, 2013-07-17 at 12:58 +0800, Weiguo Zhu wrote:
> > aha！没过多久逮到这个算式了
> > 如果p1==p2怎么办，所以需要调用者自己来保证不等？
> >
>
> 你是说*p1==*p2？
> 那个应该没有关系，不影响计算
>
> 不过发现新问题了，如果直接交换两个int是没有问题的，但是用这种连等式带指
> 针的写法发现有问题：
> int a=1,b=2;
> int *p1=&a, *p2=&b;
> XCHG(*p1,*p2)的话，p1指向的内容会变成0，
> 而
> XCHG(a,b)就没有问题
> 另外，展开写是没问题的，写成连等式就有问题，看了下汇编，有十几行的差异
>
> 分析了一下，搞不好是gcc的bug，因为加一个优化参数 -O (随便O几)都可以出正
> 确结果
>
> 大家都来测测看，我的环境是opensuse-12.2, gcc-4.7
>
>
> atommann你又发现新大陆了 （哥伦布去哪里了？）
>

这个问题被atommann自己揪出来了，
http://en.wikipedia.org/wiki/XOR_swap_algorithm
-------------------------ref------------------------------
The body of this function is sometimes seen incorrectly shortened to if
(x != y) *x^=*y^=*x^=*y;. This code has undefined behavior, since it
modifies the lvalue *x twice without an intervening sequence point.
-------------------------end------------------------------

果然装B遭雷劈

[mjxian]

在 2013年7月17日上午12:28，Atommann <atom...@gmail.com>写道：

自然，面试没有通过（因为我的 C 语言基础知识学得并不扎实，又很长一段时间都没有写代码了，再加上面试前未作准备）。

另外，面试前的准备确实很重要。有些题目的知识点虽然很基础，但如果一段时间的工作没涉及过，又没有准备过的话，还是难免手忙脚乱。

[ken chow]

看了你们的程序，我想问一下，有什么方法可以测试，这个程序的执行花了多少时间；

这个时间是不是可以判定，这个程序是否效率；

在抢占式内核中执行，是不是每次执行的时间都是一样的呢？

--

[Nala Ginrut]

On Thu, 2013-07-18 at 10:57 +0800, ken chow wrote:
> 看了你们的程序，我想问一下，有什么方法可以测试，这个程序的执行花了多少时间；
> 这个时间是不是可以判定，这个程序是否效率；
> 在抢占式内核中执行，是不是每次执行的时间都是一样的呢？
>
>

1、是指异或交换的这个方法的效率吗？如果是的话，其实这个方法并不能显著提
高效率，主要是用来吓唬人的 ;-)

2、测试程序的执行时间方法很多，粗略测试的话在shell下用time就行了，精细一
点的话要用gettimeofday，不过只能到ms级别

3、抢占式内核是否保证每次执行时间一样的问题，个人认为如果在较大数据规模
的情况下，考虑到缓存命中率的问题，我觉得是无法保证的。有这方面经验的朋友
可以分享下

[ken chow]

1.主要是用来吓唬人的;呵呵，哈哈；

2.我在main函数的开始结束部分用gettimeofday，但每次执行的时间不一样，我用的虚拟机，这个肯定跟主机工作性能有关，我就迷惑了，所有才有我第3个问题；

[孑影]

你这中写法不一定对了来着，这种写法c标准完全没有规定执行顺序，看编译器的，而且应该是不安全的写法，原来就是用异或运算来做的，x^x^y=y 的原理 简单来说就是与自己异或为0

#风起看云涌，叶落品人生#

[bc Ho]

这个从左到右还是从右到左执行都是 ok 的吧……反正是对偶的结构

[Nala Ginrut]

On Wed, 2013-07-24 at 23:59 +0800, 孑影 wrote:
> 你这中写法不一定对了来着，这种写法c标准完全没有规定执行顺序，看编译器的，而且应该是不安全的写法，原来就是用异或运算来做的，x^x^y=y 的原理
> 简单来说就是与自己异或为0
>

你提到的这点当时已经讨论过了，请看当时的邮件

[Ashi]

我觉得可以从数据依赖性上分析这两个算法的性能问题，正常方法没有Read after Write(RAW)型[0]的数据依赖，而异或写法有RAW数据依赖。因RAW会导致CPU流水线利用率下降，也就是指令级并行减少([1]中也提到了)，因此执行效率会低。

附上我的测试代码，下面是我在x86的平台上用gcc-4.7.2 -O2 -lrt选项的结果：
 10000000 normal swap cost: 18171
10000000 inplace swap cost: 46266
异或写法要慢2.5倍左右。

--
[0]http://en.wikipedia.org/wiki/Data_dependency
[1]http://en.wikipedia.org/wiki/XOR_swap_algorithm

2013/7/18 ken chow <kench...@gmail.com>

[Nala Ginrut]

On Mon, 2013-07-29 at 16:06 +0800, Ashi wrote:
> 我觉得可以从数据依赖性上分析这两个算法的性能问题，正常方法没有Read after
> Write(RAW)型[0]的数据依赖，而异或写法有RAW数据依赖。因RAW会导致CPU流水线利用率下降，也就是指令级并行减少([1]中也提到了)，因此执行效率会低。
>
> 附上我的测试代码，下面是我在x86的平台上用gcc-4.7.2 -O2 -lrt选项的结果：
> 10000000 normal swap cost: 18171
> 10000000 inplace swap cost: 46266
> 异或写法要慢2.5倍左右。
>

一般这个用法不会使用函数，而是用宏，一旦你用了指针hold住变量，最后编译器
（至少GCC会这样）就不得不使用间接寻址(RAW的问题就来了)，而你如果用宏的
话，编译器可以利用标量演化(scalar evolution)将数值处理成立即数，同时也没
有RAW的问题（因为是xor相当于half-xchg then mov，算是原子操作）.注意这个
跟宏展开的提速没有关系，如果用指针，即便你用inline，优化效果几乎没有，因
为只展开了一次。测试结果一目了然：

--------------------result--------------------
10000000 normal swap cost: 20184
10000000 inplace swap cost: 48538
10000000 new swap cost: 9764
---------------------end-----------------------

不过代码就没法用函数指针来写通用的测试函数了，测试函数要重写


PS: 贴出这个测试结果希望不要让同学们误会，这不过是一个讨论贴，千万千万*
不要*在你的生产代码里玩这个奇技淫巧！

[bc Ho]

赞！干货出现了！

[Ashi]

2013/7/29 Nala Ginrut <nalag...@gmail.com>

On Mon, 2013-07-29 at 16:06 +0800, Ashi wrote:
> 我觉得可以从数据依赖性上分析这两个算法的性能问题，正常方法没有Read after
> Write(RAW)型[0]的数据依赖，而异或写法有RAW数据依赖。因RAW会导致CPU流水线利用率下降，也就是指令级并行减少([1]中也提到了)，因此执行效率会低。
>
> 附上我的测试代码，下面是我在x86的平台上用gcc-4.7.2 -O2 -lrt选项的结果：
>  10000000 normal swap cost: 18171
> 10000000 inplace swap cost: 46266
> 异或写法要慢2.5倍左右。
>

一般这个用法不会使用函数，而是用宏，一旦你用了指针hold住变量，最后编译器
（至少GCC会这样）就不得不使用间接寻址(RAW的问题就来了)，而你如果用宏的
话，编译器可以利用标量演化(scalar evolution)将数值处理成立即数，同时也没
有RAW的问题（因为是xor相当于half-xchg then mov，算是原子操作）.注意这个
跟宏展开的提速没有关系，如果用指针，即便你用inline，优化效果几乎没有，因
为只展开了一次。测试结果一目了然：

--------------------result--------------------
10000000 normal swap cost: 20184
10000000 inplace swap cost: 48538
10000000 new swap cost: 9764
---------------------end-----------------------

不过代码就没法用函数指针来写通用的测试函数了，测试函数要重写


PS: 贴出这个测试结果希望不要让同学们误会，这不过是一个讨论贴，千万千万*
不要*在你的生产代码里玩这个奇技淫巧！

多谢指出，但是我看到用宏的代码生成的x86汇编中没有了读写memory，这样的优化只是针对这个测试例子的，和实际的应用还是不一样。（这是我之前写的测试的问题）。
我改了一下测试，把它换成对一个大的数组内的元素进行交换。结果如下：
--------------------result--------------------
20000000 long array:
normal swap cost: 26601
inplace swap cost: 30236
new swap macro cost: 28168
---------------------end-----------------------

另外之前没有看生成的汇编代码，看了之后才发现有临时变量的交换方法的指令要少一些。尤其是在ARM平台上与异或交换方法相比要少3条比较费时的load和store指令。这可能才是影响性能的关键。数据依赖在这里对性能应该没有产生主要影响。有空了可以写一个只交换寄存器的交换函数，测试一下数据依赖对性能的影响。

[Nala Ginrut]

所以说要加一个警告，免得有人看到这个优化效果以后就拿去用，因为这个优化效
果跟编译器版本、硬件架构和计算数值本身都有关联，只能说是一个特例而已

[Nala Ginrut]

On Wed, 2013-07-31 at 09:44 +0800, Nala Ginrut wrote:
>
> 所以说要加一个警告，免得有人看到这个优化效果以后就拿去用，因为这个优化效
> 果跟编译器版本、硬件架构和计算数值本身都有关联，只能说是一个特例而已
>

索性再回复全面点，之前我对ken chow说这个方法并不能显著提高性能，原因也就
是“这事儿根本说不准” ;-)

[Nala Ginrut]

今天特地把这个帖子翻出来告诫大家，用这个xor的方法一定要注意size，对于较大的类型，可能会失效的，如果在嵌入式设备上确实需要节省一个交换空间的话一定要看下生成的汇编，对于x86计算较大size的数据的话千万不要用这个方法，不值得花时间去处理问题。

今天我自己写了个求最大公约数的gcd函数，因为c++自带那个会算成浮点数，如果写成这样就会出问题：
size_t gcd(size_t n, size_t m)
{
while(m%=n) m^=n^=m^=n;
return n;
}

测试了一个显然的数10000000000000000001 和 1238123981209381900183，结果是5

换成常规的exchange方式就不会出问题


2014-02-08 11:03 GMT+08:00 cicero ma <mawe...@gmail.com>:
> 不用第三个变量交换两个int是个很经典的技巧了，一般c语言课上都会讨论到
>
> 另一个容易理解的写法是
> a = a+b;
> b = a-b;
> a = a-b;
>
> 两次xor同一个数，变量的值还是原始值，这个技巧经常在加密算法里用到

>
>
>
> On Wednesday, July 17, 2013 12:28:56 AM UTC+8, atommann wrote:
>>
>> Dear all,
>>
>> 上周去一家公司面试，其中一问题是：写一个函数，判断一个 unsigned long int
>> 整数是不是一个回文数(palindrome)。比如 123454321 是回文数，而 123456789 则不是。
>>
>>

>> 有意思。很快，google 把我带到了 http://www8.cs.umu.se/~isak/snippets/ 里的 strrev.c

>>
>> char *strrev(char *str)
>> {
>> char *p1, *p2;
>>
>> if (! str || ! *str)
>> return str;

>> for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
>> {
>> *p1 ^= *p2;
>> *p2 ^= *p1;
>> *p1 ^= *p2;
>> }
>> return str;
>> }
>>

>> 一看，傻眼了。for 循环里三句话就搞定了头和尾的字符交换，心想，这个是神马招式？晚上回到家，到一个字符串实例 "hello"
>> 按这个算法推了一番，果然可以反转字符串。问题想不通，就连陪孩子去超市逛街都在想这个问题。最终还是在冲凉的时候把这个算法想通了 :)
>>
>> 这是个妙招啊，一定在某个地方有记录，翻开 "Hacker's Delight"
>> 中文版《高效程序的奥秘》(顺便吐槽：中文版翻译质量堪忧！欲购请慎重！http://book.douban.com/subject/1159177/
>> )，果然，在第 30 页找到了这个 hack，其历史至少可以追溯到 1961 年 IBM 的一个编程课程的内容。
>>
>> 随便提及，以前读 "Hackers: Heroes of the Computer Revolution - 25th
>> Anniversary Edition" 中文版《黑客:计算机革命的英雄》25周年版(
>> http://book.douban.com/subject/6860890/ 柴火创客空间 www.chaihuo.org 有 4
>> 本该书供出售)里面提到 MIT AI Lab 那帮传奇 hacker 们的各种 hacks，顺书搜索，他们的工作(称为
>> HAKMEM)居然全部记录在案，见 http://en.wikipedia.org/wiki/HAKMEM
>>

>> --
>> Best regards,
>> Atommann
>> http://www.atommann.com
>