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

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

许多编程语言也提供了这四个位运算符(一般表示为'&','|','!'和'^'),再加上移位运算符(<<和>>),在计算的时候比算术运算要快很多,不过现在的编译器和解释器已经会将乘以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 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

统计师的Python日记【第3天:Numpy你好】

本文是【统计师的Python日记】第3天的日记 回顾一下,第1天学习了Python的基本页面、操作,以及几种主要的容器类型;第2天学习了python的函数、循环...

38712
来自专栏CSDN技术头条

Apache Spark 1.5新特性介绍

Apache Spark社区刚刚发布了1.5版本,大家一定想知道这个版本的主要变化,这篇文章告诉你答案。 DataFrame执行后端优化(Tungsten第一阶...

1869
来自专栏Grace development

一道看似简单的面试题

这样看似简单的一个面试题, 实际牵出了很多基础知识,本章在为大家补习基础知识的情况下来解答这道题。先亮出答案

362
来自专栏数据结构与算法

BZOJ3693: 圆桌会议(Hall定理 线段树)

我的思路:对于区间分两种情况讨论,一种是完全包含,另一种是部分包含。 第一种情况非常好判断,至于计算对于一个区间[l, r]的$\sum a[i]$就可以了,但...

782
来自专栏数据结构与算法

一个例子教你如何与出题人斗智斗勇

我以前出过一道题,卡了10种贪心,但还是被第11种贪心A了,  一道题不会做?贪嘛,能怎么贪怎么贪,想怎么贪怎么贪! 现在NOIP题目的数据给的不...

2646
来自专栏深度学习与计算机视觉

算法-1到n中所有和为m的组合

题目: 输入两个整数 n 和 m,从数列1,2,3…….n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来。 解题思路: 好未来笔试题...

1935
来自专栏海天一树

约瑟夫环的循环链表解法和数学公式解法

约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的,他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法...

1203
来自专栏WindCoder

最大流量和线性分配问题

这里有一个问题:你的业务分配给承包商来履行合同。您可以浏览您的名单,并决定哪些承包商可以参与一个月的合同,你可以查看你的合同,看看哪些合同是一个月的任务。鉴于你...

662
来自专栏YG小书屋

ES中文分词器之精确短语匹配(解决了match_phrase匹配不全的问题)

2034
来自专栏C语言及其他语言

[每日一题]矩阵问题

今天给大家分享的是二维数组的基本用法,主要是利用数组对行列的控制 题目描述 求一个3×3矩阵对角线元素之和。 输入 矩阵 输出 主对角线 副对角线 元素和 ...

3017

扫码关注云+社区