[多少懂点位运算]找出唯一的数字

大家都知道现代计算机的底层是以二进制为基础的,计算机所有的操作最后都归结到了简单的二进制位运算上:与,或,非和异或。

许多编程语言也提供了这四个位运算符(一般表示为'&','|','!'和'^'),再加上移位运算符(<<和>>),在计算的时候比算术运算要快很多,不过现在的编译器和解释器已经会将乘以2的幂次和除以2的幂次转换为移位运算符了。

懂一点位运算的知识可以巧妙的解决一些特定领域的问题。

问题描述

现在看一个比较简单的问题:

有一组整数,其中出了一个数字外,其他每个数字都出现了两次,找出这个只出现了一次的数字。

比较直接的方法就是哈希表(如果语言有原生的集合数据类型更好),速度也不满,不过空间复杂的是O(n)的,但是往往面试官会让你在O(1)的空间复杂度下解决问题,这时候就需要位运算登场了。

异或运算的性质

异或运算简单来说就是或运算再取反,即a xor b = not (a or b),我们可以得到:

1 ^ 0 = 1

1 ^ 1 = 0

0 ^ 0 = 0

0 ^ 1 = 1

稍微推广一下我们可以发现一个数字异或自己为得到0,而异或0会得到自己,即a ^ 0 = a, a ^ a = 0,于是这个问题也就迎刃而解了,就是对这一组数字做一连串的异或运算,最后得到的数字就是那一个唯一只出现过一次的数字。

代码实现

请不要认为这一部分是水字数。

from functools import reduce
from operator import xor

def findUnique(numbers):
    return reduce(xor, numbers)

总结

本文简单的介绍了异或运算的性质和一个更简单的应用,希望可以给大家一点帮助和启发。

最后祝大家享受生活,享受代码。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏james大数据架构

CSS好看的按钮

好看的按钮 <style> .btn { BORDER-RIGHT: #7b9ebd 1px solid; PADDING-RIGHT: 2px; BORDE...

1997
来自专栏田超学前端

【微信小程序】c# 实现获取openid、session_key 服务端

4980
来自专栏王磊的博客

MySQL数据库工具类之——DataTable批量加入MySQL数据库(Net版)

MySQL数据库工具类之——DataTable批量加入数据库(Net版),MySqlDbHelper通用类希望能对大家有用,代码如下: using MySql....

3619
来自专栏张善友的专栏

通过SmtpClient发送Exchange会议邮件

看到C#中调用Outlook API 发起会议 ,这个完全可以用SMTP方式实现的,下面我的项目中使用的代码: 对于.NET而言,从2.0开始,发邮件已经是一件...

1939
来自专栏跟着阿笨一起玩NET

从sql server 中读取二进制图片

391
来自专栏Golang语言社区

GO语言 TCP传输实例

package main import ( "net" "fmt" ) var ( maxRead = 1100 msgStop = []byt...

3396
来自专栏王磊的博客

Net连接mysql的公共Helper类MySqlHelper.cs带MySql.Data.dll下载

MySqlHelper.cs代码如下: using System; using System.Collections.Generic; using System...

4399
来自专栏菩提树下的杨过

Silverlight:利用异步加载Xap实现自定义loading效果

关键点: 1.利用WebClient的DownloadProgressChanged事件更新下载进度 2.下载完成后,分析Xap包的程序集Assembly信息 ...

18510
来自专栏自由而无用的灵魂的碎碎念

小项目分享---混色器

编写代码的同志们一般懂美术的就少了,偶也是,什么色轮、三维加色等等。虽然看过一些书籍(如内田广由纪的《配色基础原理》),不过还是一知半解的。

963
来自专栏木宛城主

曾今的代码系列——自己的分页控件+存储过程实现分页

项目里面的测试代码,仅供参考 LoginByAjax <title>Ajax登陆</title> <script src="Scripts/c...

1855

扫码关注云+社区