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

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

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

相关文章

来自专栏Vamei实验室

纸上谈兵: 排序算法简介及其C实现

排序的目标是将一组数据 (即一个序列) 重新排列,排列后的数据符合从大到小 (或者从小到大) 的次序。这是古老但依然富有挑战的问题。Donald Knuth的经...

2529
来自专栏后端技术探索

常见算法面试题

这几天在网上看到一篇关于算法面试题的博客,归纳的很好,有不少经典的题目,大部分来自《编程珠玑》、《编程之美》、《代码之美》三本书。这里给出书上的解答以及一些思考...

3082
来自专栏编程直播室

读书笔记:《算法图解》第三章 递归

1625
来自专栏Danny的专栏

面向对象三大特征

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

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

[每日一题]矩阵问题

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

3287
来自专栏落影的专栏

程序员进阶之算法练习(二十五)

前言 算法题是锻炼思维的好工具,在解决问题的层面考察思考能力。 正文 1. Compote 题目链接 题目大意: 给出a、b、c三种材料,可以1:2:4组成...

3879
来自专栏编舟记

函数式编程简介

1900年,Hilbert 提出了数学界悬而未决的10大问题,后续陆续添加成了23个问题,被称为著名的 Hilbert 23 Problem。针对其中第2个决定...

2084
来自专栏大数据文摘

正则表达式太慢?这里有一个提速100倍的方案(附代码)

2464
来自专栏架构说

折半查找部分有序

部分有序 本周qq群有人咨询 Search in Rotated Sorted Array 来源: https://leetcode.com/proble...

2899
来自专栏绿巨人专栏

Category Theory: 01 One Structured Family of Structures

\(G = \{ G, +, e \}\),一个数据集\(G\),一个二元操作符\(+\),和一个幺元\(e\)。

1313

扫码关注云+社区

领取腾讯云代金券