赶紧上mitbbs的JobHunting版去找以前有关Qualcomm的面试题，还真看见一个有用的：
－－－
发信人: Zhuimeng1314 ( 追梦一生), 信区: JobHunting
标 题: Qualcomm 电面面经
发信站: BBS 未名空间站 (Fri Mar 11 21:31:21 2011, 美东)
问简历
如何测试一个DVD player
第二题
int x=20; int y=35;
x=y+++x++;
y=++y+++x;
问之后x 和y 是多少
第三题
怎样交换两个数而不用temp （XOR）
哎。。简历被问得SB了。。
发信人: luckyseeker (lucky), 信区: JobHunting
标 题: Re: Qualcomm 电面面经
发信站: BBS 未名空间站 (Fri Mar 11 23:33:28 2011, 美东)
我靠，第一题我用C和java分别run了一下，居然结果不一样。
java的结果（run in eclipse 3.6.1）
x=55, y=36 //第一步
x=56, y=93 //第二步
C的结果（cygwin + gcc）
x=56, y=36 //第一步
x=57, y=94 //第二步
顺便说一下，y=++y+++x;两个都报错，至少要空一格写成：y=++y+ ++x;
觉得java下面，第一步算出来x=20+55 = 55，后面的x++不运行。
但是C下面，x=55之后，x++还要先加再用一次，就变成了56。
跟内存模式有关么？是不是java下面的left side构造了一个新地址for x?
发信人: Zhuimeng1314 ( 追梦一生), 信区: JobHunting
标 题: Re: Qualcomm 电面面经
发信站: BBS 未名空间站 (Sat Mar 12 01:09:42 2011, 美东)
我问用来播放什么，用来干什么。。他不说。。。
不过我倒是没想到遥控器什么的
还有什么是bt测试？我完全不知道。。
盗版盘用英文怎么说？
【 在 HanSolo7 (隼) 的大作中提到: 】
: 如何测试一个DVD player:
: 先询问对方： 用来做什么？播放什么？谁使用？接什么电视？在哪个国家？
: 测试项目： DVD机器本身，遥控器，连接线
: 然后测试各种功能：普通测试，极限测试，bt测试（比如同时操作遥控器和DVD机
: 器上的按钮，盗版盘测试）。。。。
发信人: done (折埋), 信区: JobHunting
标 题: Re: Qualcomm 电面面经
发信站: BBS 未名空间站 (Sat Mar 12 01:10:49 2011, 美东)
以前版上有无数人说过，这++的题不同编译器的结果是不一样的
发信人: done (折埋), 信区: JobHunting
标 题: Re: Qualcomm 电面面经
发信站: BBS 未名空间站 (Sat Mar 12 01:15:42 2011, 美东)
我认为凭自己的理解知道i++和++i的区别去计算结果就好了。
或者如牛人说的，直接答"如果谁敢写这种code就马上炒了他/她"
【 在 Zhuimeng1314 ( 追梦一生) 的大作中提到: 】
: 哦~~那他拿来折磨我。。。
－－－
对这个帖子，我所关心的是第三个题：如何交换两个数而不用临时变量。
正如楼主说用，用xor可以做到。参见Bit Twidding Hacks上面的文章：http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesXOR
Swapping values with XOR
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
This is an old trick to exchange the values of the variables a and b without using extra space for a temporary variable.
On January 20, 2005, Iain A. Fleming pointed out that the macro above doesn't work when you swap with the same memory location, such as SWAP(a[i], a[j]) with i == j. So if that may occur, consider defining the macro as (((a) == (b))
(((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))). On July 14, 2009, Hallvard Furuseth suggested that on some machines, (((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b))) might be faster, since the (a) ^ (b) expression is reused.
还有一种方法是用加减法：http://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd
Swapping values with subtraction and addition
#define SWAP(a, b) ((&(a) == &(b)) \
(((a) -= (b)), ((b) += (a)), ((a) = (b) - (a))))
This swaps the values of a and b without using a temporary variable. The initial check for a and b being the same location in memory may be omitted when you know this can't happen. (The compiler may omit it anyway as an optimization.) If you enable overflows exceptions, then pass unsigned values so an exception isn't thrown. The XOR method that follows may be slightly faster on some machines. Don't use this with floating-point numbers (unless you operate on their raw integer representations).
Sanjeev Sivasankaran suggested I add this on June 12, 2007. Vincent Lefèvre pointed out the potential for overflow exceptions on July 9, 2008
这种方法更易于理解，不过有overflow的危险，且不能用于浮点数的交换。话说回来，异或算法也不是没有缺点。比如当两个要交换的值相同的时候，用这种方法会使之成为零（因为A^A == 0）。
对于这两种算法的证明和分析，可以参考wikipedia上面的链接：http://en.wikipedia.org/wiki/XOR_swap_algorithm
核心在于异或几条类似于加法的性质。
The binary operation XOR over bit strings of length N exhibits the following properties (where denotes XOR):
L1. Commutativity: A ^ B = B ^ A （中文名称：交换律）
L2. Associativity: (A ^ B) ^ C = A ^ (B ^ C) （中文名称：结合律）
L3. Identity exists: there is a bit string, 0, (of length N) such that for any A ^ 0 = A （这个性质中文该怎么讲？）
L4. Each element is its own inverse: for each A, A ^ A = 0. （这个性质和加法就有些区别了）
值得注意的是，加减swap可以看作是异或swap的一个扩展。
No comments:
Post a Comment