异或运算的高级应用和Briankernighan算法

2024-09-06 05:36

本文主要是介绍异或运算的高级应用和Briankernighan算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本篇文章主要回顾一下计算机的位运算,处理一些位运算的巧妙操作。

特别提醒:实现位运算要注意溢出和符号扩展等问题。

先看一个好玩的问题:

$Problem1 $ 黑白球概率问题

袋子里一共a个白球,b个黑球,每次从袋子里拿2个球,每个球每次被拿出的机会均等。如果拿出的是2个白球、或者2个黑球,那么就往袋子里重新放入1个白球,如果拿出的是1个白球和1个黑球,那么就往袋子里重新放入1个黑球,那么最终袋子里一定会只剩1个球,请问最终是黑球的概率是多少?用a与b来表示这个概率。

问题分析:

细心的同学会发现,袋子中的黑球每次要么取出2个,要么取出0个。所以如果袋子里的初始黑球个数是奇数的话,最后一个球一定是黑球,如果是偶数的话,最后一个球一定是白球。我们可以用异或运算来清晰地体现。

异或运算性质

[!NOTE]

  1. 异或运算就是无进位相加。

  2. 异或运算满足交换律、结合律,也就是同一批数字,不管异或顺序是什么,最终结果都是一个。

  3. 0^n = n , n^n = 0

  4. 整体异或和如果是x,整体中某个部分的异或和如果是y,那么剩下部分的异或和是x^y。【区间上异或和】

  5. 通过异或运算来交换两个数(不用新开辟空间)

    a = a ^ b

    b = a ^ b

    a = a ^ b

    三行代码即可交换a 与 b

证明一下第4条性质:

​ 若 a^b=c ,则a = c^b b = c^a。根据异或运算满足交换律与结合律,我们能得到:若一部分的异或和为y,另一部分的异或为x^y,则这两部分的整体异或和为x

回到题目,我们把白球看成0,黑球看成1,根据题目条件,拿出1个白球和1个黑球则放入一个黑球,用数学数字表示就是 $0,1~ -> 1 $,那么全部条件如下:
0 , 1 − > 1 1 , 0 − > 1 0 , 0 − > 0 1 , 1 − > 0 0,1 -> 1\\ 1,0 -> 1\\ 0,0 -> 0\\ 1,1 -> 0\\ 0,1>11,0>10,0>01,1>0
很显然,这就是个异或运算嘛。从袋子里拿出两个数进行异或运算,再把异或运算的结果放入袋子,所以这个题目我们可以抽象成如下情况:

数集中有a个0,b个1,每次从数集中拿出两个数进行异或,再将异或的结果放回到数集中【经过一次这种操作,数集中的数的个数会减1】,经过多次操作之后,最终得到一个数,请问这个数是1的概率?

一次这种操作是一次异或,多次异或放在一起就是异或和问题,异或和符合交换律与结合律,所以最终结果只和1的个数有关,若1的个数为偶

数,最终结果为0,若1的个数为奇数,最终结果为1。

P r o b l e m 2 Problem2 Problem2 不用任何判断语句和比较操作,返回两个数的最大值
问题分析:

这个题目有意思,既然不用判断和比较,那就只能利用计算操作了。但是涉及到比大小,那必然要作差,取两个int型数据 a , b a,b a,b,作差得 c = a − b c = a -b c=ab,如果 c > 0 c>0 c>0,则 a a a大,如果 c < 0 c<0 c<0,则 b b b大。不用能判断,那我们考虑一下位运算:

如果 c < 0 c <0 c<0,则 c c c的符号位为1,对其进行无符号位移(向右移动31位),最终得到结果1。

如果 c > 0 c>0 c>0,则 c c c的符号位为0,对其进行无符号位移(向右移动31位),最终得到结果0。

我们记较大值为 m a x max max c < 0 c < 0 c<0时, m a x = a ∗ 0 + b ∗ 1 max = a*0 + b*1 max=a0+b1 c > 0 c > 0 c>0时, m a x = a ∗ 1 + b ∗ 0 max = a*1 + b*0 max=a1+b0。现在我们把无符号位移之后的 c c c a , b a,b a,b 两个数的系数的关系表建立起来:

cAB
101
010

很容易看出,B = C,A = C ^1。【注意,这里的C是 c c c向右无符号位移31位得到的结果】

详细代码:
//不用任何判断语句和比较操作,返回两个数的最大值
unsigned int sign(unsigned int C) {return C >> 31; //C最后只有0和1两个结果
}
//与1做异或
int flip(unsigned int C) {return C ^ 1;
}
int getMax(int a, int b) {int c = a - b;//强制转换为无符号整数再右移unsigned int C = static_cast<unsigned int>(c);int returnA = flip(sign(C));int returnB = sign(C);return a * returnA + b * returnB;
}

其实这个代码存在一定风险,因为int c = a - b可能会导致溢出情况,同学们可自行思考没有溢出问题的代码,实在暂时没想出来的的可以私信我【手动狗头】。

P r o b l e m 3 Problem3 Problem3 找到缺失的数字

现在存在一个长度为n的数组,也就是说这个数组里有n个数,但是小明只提取出了n-1个数,现在想知道缺失的那个数的大小是多少?

问题分析:

这个问题比较简单,很多同学会第一时间想到哈希表,先遍历这个长度为n的数组,建立数字本身:此数字出现的次数哈希表,之后再遍历一次数组,每遍历一个数字,都在哈希表中减少一次这个数字出现的次数,遍历结束之后,出现次数为-1的那个数字就是缺失的数。

但是这种方法比较复杂,需要遍历两遍数组,还要建立哈希表,查询哈希表,更改哈希表,不仅浪费时间,空间也消耗巨大【建哈希表需要空间】。所以我们想借助一下此篇文章强调的位运算的思想来找更简单的解法。

重新回顾一下这个题目,数组的数字情况有三种:完整的数组,缺失的一个数字,缺失一个数字之后的数组。由此可以联想到异或运算的第四条性质【区间上的异或和】,我们记数组中的数字如下:
a 1 , a 2 , a 3 , a 4 , . . . , a n a_1,a_2,a_3,a_4,...,a_n a1,a2,a3,a4,...,an
记缺失的数字为 a i a_i ai,则剩余的数字为
a 1 , . . . , a i − 1 , a i + 1 , . . . , a n a_1,...,a_{i-1},a_{i+1},...,a_n a1,...,ai1,ai+1,...,an
数组中所有数字的异或和为
A = a 1 ∧ a 2 ∧ . . . ∧ a n A = a_1 \wedge a_2 \wedge ...\wedge a_n A=a1a2...an
缺失了一个数字之后的数组中所有数字异或和为
B = a 1 ∧ . . . ∧ a i − 1 ∧ a i + 1 ∧ . . . ∧ a n B = a_1 \wedge ... \wedge a_{i-1} \wedge a_{i+1}\wedge...\wedge a_n B=a1...ai1ai+1...an
异或运算满足结合律,所以我们很容易知道:
A = B ∧ a i A = B \wedge a_i A=Bai
所以
a i = A ∧ B a_i = A \wedge B ai=AB
以上过程就能直接利用异或运算的性质找出缺失的数字了。

我们直接给出代码:

int findMissingNumber(vector<int> Numbers,vector<int> missingNumbers) {int A = 0;  //存储所有数字异或和for (int i : Numbers) {A = A ^ i;}int B = 0;for (int i : missingNumbers) {B = B ^ i;}return A ^ B;
}
P r o b l e m 4 Problem4 Problem4 找到出现了奇数次的数

数组中有1种数出现了奇数次,其他的数都出现了偶数次,返回出现了奇数次的数。

问题分析:

出现偶数次的数有什么特殊之处呢?我们知道 n ∧ n = 0 n\wedge n = 0 nn=0,所以偶数次的数对最终异或和并没有贡献,只有奇数次的数会对异或和有影响,题目中说明了奇数次的数只有一种,所有最终异或和就是出现奇数次的数本身。

很简单的,以下是解题代码:

int findOddTimesNumber(vector<int> Numbers) {int A = 0;  //存储所有数字异或和for (int i : Numbers) {A = A ^ i;}return A;
}
B r i a n K e r n i g h a n Brian Kernighan BrianKernighan算法

B r i a n K e r n i g h a n BrianKernighan BrianKernighan算法主要是用来获得二进制中最右侧的1,看下面这个例子你就明白了:

现在有一个二进制数(用8个位的数来作例子) 01101000 01101000 01101000,我们想得到最右侧的1,也就是 00001000 00001000 00001000,该进行哪些步骤呢?先简单思考下:

得到最右侧的1,也就是最右侧的1前面的数全部变为0(0->0,1->0),该怎么变呢?现在我们来尝试一下:

  • 与自身作任何操作(与(且),或,异或)都不能使得 01101000 01101000 01101000变成 00001000 00001000 00001000,即使与0作与运算能使 0110 0110 0110变成 0000 0000 0000,但是后面的 1000 1000 1000也会被影响成 0000 0000 0000
  • 先对数取反得到 10010111 10010111 10010111,这时前面的 1001 1001 1001 0110 0110 0110做与运算就可以得到 0000 0000 0000,但是后面的 1000 1000 1000 0111 0111 0111做与运算变成了 0000 0000 0000,我们得想办法不让 1000 1000 1000发生变化。
  • 由于 1000 1000 1000是最右侧的1,所以 1000 1000 1000取反的结果 0111 0111 0111只比 1000 1000 1000小1,因此我们把 10010111 10010111 10010111加上1再和原来的数 01101000 01101000 01101000做与运算,最后会得到 00001000 00001000 00001000

总结一下:

  1. 先对原来的数取反,以便最右侧1之前的数和取反之后的数做与运算能得到 0...0 0...0 0...0
  2. 对于最右侧1以及之后的二进制数 100..0 100..0 100..0,取反之后的数比 100..0 100..0 100..0小1,我们对取反之后的数加上1就可以得到 100..0 100..0 100..0,相同两个数求与自然得到 100..0 100..0 100..0

所以 B r i a n k e r n i g h a n Briankernighan Briankernighan算法:对原来的数取反并加1,再和原来的数做与运算,最终得到最右侧的1。

int Briankernighan(int a) {return a & (~a + 1);
}
P r o b l e m 5 Problem5 Problem5 返回2种出现了奇数次的数

数组中有两种数出现了奇数次,其他的数都出现了偶数次,返回这2种出现了奇数次的数。

问题分析:

这道题算是 P r o b l e m 4 Problem4 Problem4的拓展,我们记数组中的所有数为:
a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an
重复出现的记为1个数。

记2种出现了奇数次的数为 a i , a j a_i,a_j ai,aj,根据 P r o b l e m 4 Problem4 Problem4,我们知道,数组中所有数(算上重复的数)的异或和为 a i ∧ a j a_i \wedge a_j aiaj,但是我们要的是 a i a_i ai a j a_j aj,该怎么找呢?

已知 a i ∧ a j a_i \wedge a_j aiaj是求不出来 a i a_i ai a j a_j aj的,比如二进制数 01001100 0100 1100 01001100可以由 11110000 , 10111100 11110000,10111100 11110000,10111100异或出来,也可以由 00001100 , 01000000 00001100,01000000 00001100,01000000异或出来,但是我们发现,其中的某个1要么在 a i a_i ai中,要么在 a j a_j aj中,不可能同时出现在 a i , a j a_i,a_j ai,aj中。借助上面的 B r i a n K e r n i g h a n Brian Kernighan BrianKernighan 算法,我们拿最右侧的1作为标志来区分 a i , a j a_i,a_j ai,aj

还是拿异或和为二进制数 01001100 01001100 01001100作为例子,它的最右侧的1为 00000100 00000100 00000100,我们从右往左数,第三位为1,这个第三位为1就是标志!!!

正如刚刚讨论的,要么 a i a_i ai的第三位为1,要么 a j a_j aj的第三位为1,但是分析到现在还是求不出 a i , a j a_i,a_j ai,aj,现在我们考虑一下将所有数进行划分,很显然,原来的所有数也可以被划分为两部分:

​ 第三位为1的部分与第三位为0的部分,并且,每一部分都对应一个 a i a_i ai a j a_j aj

对含有 a i a_i ai的部分求异或和不就是 a i a_i ai么, a j a_j aj同理。

详细代码:
pair<int,int> findTwoOddTimesNumbers(vector<int> Numbers) {int eorAll = 0; //a_i ^ a_jfor (int i : Numbers) {eorAll = eorAll ^ i;}int rightOne = Briankernighan(eorAll); //得到最右侧的1int eor1 = 0; //对应位置是0的数的异或和int eor2 = 0; //对应位置是1的数的异或和for (int i : Numbers) {if (i & rightOne == 0) {eor1 = eor1 ^ i;}}eor2 = eorAll ^ eor1;return { eor1, eor2 };
}

这篇关于异或运算的高级应用和Briankernighan算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1141141

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

python中time模块的常用方法及应用详解

《python中time模块的常用方法及应用详解》在Python开发中,时间处理是绕不开的刚需场景,从性能计时到定时任务,从日志记录到数据同步,时间模块始终是开发者最得力的工具之一,本文将通过真实案例... 目录一、时间基石:time.time()典型场景:程序性能分析进阶技巧:结合上下文管理器实现自动计时

kotlin中的行为组件及高级用法

《kotlin中的行为组件及高级用法》Jetpack中的四大行为组件:WorkManager、DataBinding、Coroutines和Lifecycle,分别解决了后台任务调度、数据驱动UI、异... 目录WorkManager工作原理最佳实践Data Binding工作原理进阶技巧Coroutine