源:http://www.cnblogs.com/baiyanhuang/archive/2010/06/23/1763981.html
评:
有1到10000共10000个数,如果我从中随机拿走一个数,你如何知道我拿走了哪个?
相信很多人看过这道题,并知道答案,这几天和同事聊天时听到了这个问题,因为有过自己的思考过程,不妨记录下来。说是逻辑题,其实也算是一道算法题,同事先讲了下他被面试中的思维过程:
先把10000个数相乘,然后再将拿走一个数之后的9999个数相乘,两者相除即可。
这个算法是正确的,但是会有两个潜在的问题:
如此多的数相乘,其范围必然会超出系统提供的数据类型支持,当然你可以实现自己的大数表示的算法,但那样性能必然有影响。
假设扩展一下题目,提供的数组中有0的话,乘法就不可用了。
针对前面提出的问题,同事想到了使用加法,先求出10000个数的和,再减去9999个数的和。
这样数据不会溢出,而且加法的效率比乘法也要高很多,即使数据中包含0,也没有任何问题。
然后就过关了,自己回去之后思考了一下,觉得还可以扩展,假设所有的数加起来之后仍然会溢出,那该如何处理,比如从1到(2^64-1),于是想到了位操作,与、或,异或中,要数异或最为神奇,代入一看,果然合适: 先将所有的数异或起来,然后将拿走一个数之后的数异或起来,两者结果再异或,便是拿走的那个数。
我用a,b,c,d4个数来做演示,因为异或符合结合律和交换律(你可以用0,1试一下),于是:
a^b^c^d = (a^b^c)^d
d = (a^b^c^d)^(a^b^c)
此处用异或的好处在于
不会溢出
异或的速度要快于加法
扩展一下题目,如果提供的不是整数,而是浮点数,会有问题吗?当然没有,因为是在位级别上操作,无论是整数还是浮点数,在这个算法看来,都是一堆位,处理起来没有什么差别。
再扩展一下题目,如果提供的数本身就超出了内置类型的表示范围,如在1到2^128,该如何处理?这个问题是在写这篇文章的过程中想到的,暂时没有好的办法。
(异或的确是挺神奇的一个操作,之后打算写一个memory-transaction管理的系列文章,也会提到用这个神奇的异或来实现undo-redo算法。)
分享到:
相关推荐
计算机组成原理实验-数字逻辑---运算器设计(HUST)-11个题
数字逻辑---交通灯系统设计(HUST),全部12个关卡的答案,绝对正确,麻烦下载后感觉好的家人们给个好评。另外博主还有这个课程其他两个关卡的答案,若有需要可自行下载,保证绝对正确。有任何问题都可以私信我,随时...
计算机组成原理实验-数字逻辑---交通灯系统设计(HUST)-12个题
75道逻辑题-没有答案,要答案只有百度了
数字逻辑电路-CH4.PPT 数字逻辑电路第四章标准课件加题目
头歌教学实践平台计算机组成原理数字逻辑---交通灯系统设计(HUST),第1关—第12关。源代码circ格式,用记事本打开即可。 本实训将提供一个完整的数字逻辑实验包,从Logisim新手实验,到真值表方式构建7段数码管驱动...
数字逻辑试题及答案数字逻辑试题及答案数字逻辑试题及答案数字逻辑试题及答案数字逻辑试题及答案数字逻辑试题及答案数字逻辑试题及答案
MBA考试-逻辑2009-2019 真题-年份2007.10.pdf
逻辑考题--帮你应付一些公司的笔试。有备无患!
数字逻辑试题及答案 1、设计一个带控制端的组合逻辑电路 2、分析电路与设计电路 3、用D触发器设计一个0110序列检测器,X为序列输入,Z为检测输出 4、同步时序逻辑电路与异步时序逻辑电路设计与分析
现代逻辑设计-第二版-课后习题答案
西门子样题--逻辑控制,西门子样题--逻辑控制
哈工大数理逻辑2006-2007试卷A+答案
2012-2013-2《数字逻辑设计及应用》期末考试题-A参考解答.pdf
数字逻辑电路历年试题97-02
《数字逻辑与系统设计》 习题-答案 需要的师弟师妹可以下载参考