原文链接:http://www.cnblogs.com/baiyanhuang/archive/2010/06/23/1763981.html
作者:@baiyanhuang
有 1 到 10000 共 10000 个数,如果我从中随机拿走一个数,你如何知道我拿走了哪个?
相信很多人看过这道题,并知道答案,这几天和同事聊天时听到了这个问题,因为有过自己的思考过程,不妨记录下来。 说是逻辑题,其实也算是一道算法题,同事先讲了下他被面试中的思维过程:
-
先把 10000 个数相乘,然后再将拿走一个数之后的 9999 个数相乘,两者相除即可。
这个算法是正确的,但是会有两个潜在的问题:
- 如此多的数相乘,其范围必然会超出系统提供的数据类型支持,当然你可以实现自己的大数表示的算法,但那样性能必然有影响。
- 假设扩展一下题目,提供的数组中有 0 的话,乘法就不可用了。
-
针对前面提出的问题,同事想到了使用加法,先求出 10000 个数的和,再减去 9999 个数的和。
这样数据不会溢出,而且加法的效率比乘法也要高很多,即使数据中包含 0,也没有任何问题。
然后就过关了,自己回去之后思考了一下,觉得还可以扩展,假设所有的数加起来之后仍然会溢出,那该如何处理,比如从 1 到 (2^64-1),于是想到了位操作,与、或,异或中,要数异或最为神奇,代入一看,果然合适: 先将所有的数异或起来,然后将拿走一个数之后的数异或起来,两者结果再异或,便是拿走的那个数。
我用 a,b,c,d 4 个数来做演示,因为异或符合结合律和交换律(你可以用 0,1 试一下),于是:
a^b^c^d = (a^b^c)^d
d = (a^b^c^d)^(a^b^c)
此处用异或的好处在于
- 不会溢出
- 异或的速度要快于加法
扩展一下题目,如果提供的不是整数,而是浮点数,会有问题吗? 当然没有,因为是在位级别上操作,无论是整数还是浮点数,在这个算法看来,都是一堆位,处理起来没有什么差别。
再扩展一下题目,如果提供的数本身就超出了内置类型的表示范围,如在 1 到 2^128,该如何处理? 这个问题是在写这篇文章的过程中想到的,暂时没有好的办法。
相关推荐
面试逻辑题以及答案:各大公司的面试逻辑题,本人搜索后整理的。
逻辑题 逻辑题 逻辑题 逻辑题 逻辑题 逻辑题
数字逻辑试题1模拟题自己做答案以后传20字太多了我只能写这么多太详细了我受不了啊
适用于计算机及应用专业,数字逻辑考试题123章附有答案,是一个不错的参考资料。
计算机结构与逻辑设计:第十一章 数-模和模-数转换.pdf
逻辑题
各大公司笔试常见的逻辑题,很全,对于找工作的人很有帮助的。
数字电路与逻辑设计:CH9 模数及数模转换技术.pdf
数字逻辑复习题数字逻辑复习题数字逻辑复习题数字逻辑复习题数字逻辑复习题数字逻辑复习题数字逻辑复习题
Java逻辑编程:求解完全平方数
一、填空题:(每空1分,共16分) 1.逻辑函数有四种表示方法,它们分别是( )、( )、( )和( )。 2.将2004个“1”异或起来得到的结果是( )。 3.目前我们所学的双极型集成电路和单极型集成电路的典型电路...
经典的嵌入式面试智力题 逻辑题 稀奇古怪的程序员面试题(趣味智力题)
1250题精粹 书籍目录: 第一部分历年MBA逻辑考试试题分类解析经典题库 一、加强型逻辑试题与解析 二、基本推理型逻辑试题与解析 三、削弱型逻辑试题与解析 四、解释说明型逻辑试题与解析 五、假设型逻辑试题与...
面试逻辑题
数字逻辑电路习题答案,来源自网络
java面试题 程序员面试 逻辑题 笔试题
程序元笔试中经常要遇到逻辑题,让我们来一次特训,哦也
第一章 WHY:为什么要掌握金字塔原理01 赋能表达的三大优势02 活学活用的四种应用情境职场案例:小试牛刀之协调例会时间第二章 WHAT:揭开金字塔结构的面纱