淮安网站网站建设,企业网址搭建,化妆品网站建设需求问卷调查,网站设计软件手机版本篇文章主要回顾一下计算机的位运算#xff0c;处理一些位运算的巧妙操作。
特别提醒#xff1a;实现位运算要注意溢出和符号扩展等问题。
先看一个好玩的问题#xff1a;
$Problem1 $ 黑白球概率问题
袋子里一共a个白球#xff0c;b个黑球#xff0c;每次从袋子里拿…本篇文章主要回顾一下计算机的位运算处理一些位运算的巧妙操作。
特别提醒实现位运算要注意溢出和符号扩展等问题。
先看一个好玩的问题
$Problem1 $ 黑白球概率问题
袋子里一共a个白球b个黑球每次从袋子里拿2个球每个球每次被拿出的机会均等。如果拿出的是2个白球、或者2个黑球那么就往袋子里重新放入1个白球如果拿出的是1个白球和1个黑球那么就往袋子里重新放入1个黑球那么最终袋子里一定会只剩1个球请问最终是黑球的概率是多少用a与b来表示这个概率。
问题分析
细心的同学会发现袋子中的黑球每次要么取出2个要么取出0个。所以如果袋子里的初始黑球个数是奇数的话最后一个球一定是黑球如果是偶数的话最后一个球一定是白球。我们可以用异或运算来清晰地体现。
异或运算性质 [!NOTE] 异或运算就是无进位相加。 异或运算满足交换律、结合律也就是同一批数字不管异或顺序是什么最终结果都是一个。 0^n n , n^n 0 整体异或和如果是x整体中某个部分的异或和如果是y那么剩下部分的异或和是x^y。【区间上异或和】 通过异或运算来交换两个数不用新开辟空间 a a ^ b b a ^ b a a ^ b 三行代码即可交换a 与 b 证明一下第4条性质
若 a^bc 则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个0b个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 ca−b如果 c 0 c0 c0则 a a a大如果 c 0 c0 c0则 b b b大。不用能判断那我们考虑一下位运算
如果 c 0 c 0 c0则 c c c的符号位为1对其进行无符号位移向右移动31位最终得到结果1。
如果 c 0 c0 c0则 c c c的符号位为0对其进行无符号位移向右移动31位最终得到结果0。
我们记较大值为 m a x max max c 0 c 0 c0时 m a x a ∗ 0 b ∗ 1 max a*0 b*1 maxa∗0b∗1 c 0 c 0 c0时 m a x a ∗ 1 b ∗ 0 max a*1 b*0 maxa∗1b∗0。现在我们把无符号位移之后的 c c c与 a , b a,b a,b 两个数的系数的关系表建立起来
cAB101010
很容易看出B CA 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_castunsigned 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_{i1},...,a_n a1,...,ai−1,ai1,...,an 数组中所有数字的异或和为 A a 1 ∧ a 2 ∧ . . . ∧ a n A a_1 \wedge a_2 \wedge ...\wedge a_n Aa1∧a2∧...∧an 缺失了一个数字之后的数组中所有数字异或和为 B a 1 ∧ . . . ∧ a i − 1 ∧ a i 1 ∧ . . . ∧ a n B a_1 \wedge ... \wedge a_{i-1} \wedge a_{i1}\wedge...\wedge a_n Ba1∧...∧ai−1∧ai1∧...∧an 异或运算满足结合律所以我们很容易知道 A B ∧ a i A B \wedge a_i AB∧ai 所以 a i A ∧ B a_i A \wedge B aiA∧B 以上过程就能直接利用异或运算的性质找出缺失的数字了。
我们直接给出代码
int findMissingNumber(vectorint Numbers,vectorint 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 n∧n0所以偶数次的数对最终异或和并没有贡献只有奇数次的数会对异或和有影响题目中说明了奇数次的数只有一种所有最终异或和就是出现奇数次的数本身。
很简单的以下是解题代码
int findOddTimesNumber(vectorint 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之前的数和取反之后的数做与运算能得到 0...0 0...0 0...0。对于最右侧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 ai∧aj但是我们要的是 a i a_i ai与 a j a_j aj该怎么找呢
已知 a i ∧ a j a_i \wedge a_j ai∧aj是求不出来 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同理。
详细代码
pairint,int findTwoOddTimesNumbers(vectorint 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 };
}
