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

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

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

相关文章

来自专栏编舟记

函数式编程简介

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

1564
来自专栏算法channel

动态规划:括号知多少

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

3557
来自专栏数说工作室

1. PRXMATCH () | 提取文本数据,分析师小王初上手!

【SAS Says·扩展篇】分析师小王初上手! | 1. PRXMATCH () 本集目录: 0. 小王初上手 1. 初始PRXMATCH() 2. metac...

2996
来自专栏小红豆的数据分析

小蛇学python(6)python实现经典排序算法并可视化分析复杂度

排序算法在算法界是一个怎么样的存在?就好像在学术界中数学的地位,说直接用好像用不上,可是不会做起事情来总会捉襟见肘,左支右绌。找工作的时候,有的面试官甚至会让我...

1802
来自专栏计算机视觉与深度学习基础

Leetcode 15 3Sum + 有趣的小BUG

Given an array S of n integers, are there elements a, b, c in S such that a + b...

2176
来自专栏chenjx85的技术专栏

leetcode-258-Add Digits

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

[每日一题]矩阵问题

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

3167
来自专栏架构说

折半查找部分有序

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

2839
来自专栏Danny的专栏

面向对象三大特征

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

1472
来自专栏七夜安全博客

从多项式相加看线性结构

1293

扫码关注云+社区