蓝桥杯JAVA-5.位运算技巧和原理
本文最后更新于:December 14, 2021 pm
积土成山,风雨兴焉;积水成渊,蛟龙生焉;积善成德,而神明自得,圣心备焉。故不积跬步,无以至千里,不积小流无以成江海。齐骥一跃,不能十步,驽马十驾,功不在舍。面对悬崖峭壁,一百年也看不出一条裂缝来,但用斧凿,能进一寸进一寸,能进一尺进一尺,不断积累,飞跃必来,突破随之。
目录
0. 位运算预知识
优先级别由高到低依次为:按位取反( ~ ),按位与( & ),按位异或( ^ ),按位或( | )。
一些特殊的重要知识点,记着,怕忘了。
- 任何数与 0 异或等于它本身,即 n ^ 0 = n。
理论简单说一下。
0.1 按位取反(~)
这是最简单的,将0变1,1变0。
1 |
|
0.2 按位与(&)
总结:同时为1结果才为1,否则结果为0。
0 & 0 = 0 0 & 1 = 0 1 & 0 = 0 1 & 1 =1
1 |
|
0.3 按位异或(^)
总结:不同为1,相同为0。
0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0
1 |
|
在博弈论中的尼姆博弈中会用到 。任何数与 0 异或等于它本身,即 n ^ 0 = n。
0.4 按位或(|)
总结:只要有1结果就为1,否则为0。
0 | 0 = 0 0 | 1 = 1 1 | 0 = 1 1 | 1 = 1
1 |
|
0.5 原码、补码
在计算机中,整数是按原码(二进制)存的, 负数是按补码存的, 整数的补码和原码相同, 负数的补码等于原码取反后再加一。如:
1 |
|
0.6 移位
左移(<<):
右移(>>):
无符号右移(>>>)
详解见《星星之火-JAVA中的>>>与>>区别》。这里不写了。
1. 判断奇数
1 |
|
1.1 解释
待补充。记住即可。
2. 交换两数
1 |
|
2.1 解释
两个相同的数异或之后结果会等于0,即 n ^ n = 0。并且任何数与 0 异或等于它本身,即 n ^ 0 = n。
所以,把(1)中的 x 带入 (2)中的 x,有:
y = x^y = (x^y)^y = x^(y^y) = x^0 = x。 x 的值成功赋给了 y。
对于(3),同理推导如下:
x = x^y = (x^y)^x = (x^x)^y = 0^y = y。
异或运算支持运算的交换律和结合律哦。
3. 找出没有重复的数(落单的数)
给你一组整型数据,这些数据中,其中有一个数只出现了一次,其他的数都出现了两次,让你找出这个数来 。
1 |
|
3.1 解释
因为两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身,所以我们把这一组整型全部异或一下,例如这组数据是:1, 2, 3, 4, 5, 1, 2, 3, 4。其中 5 只出现了一次,其他都出现了两次,把他们全部异或一下,结果如下(由于异或支持交换律和结合律):
1^2^3^4^5^1^2^3^4 = (1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。
也就是说,那些出现了两次的数异或之后会变成0,那个出现一次的数,和 0 异或之后就等于它本身。
4. 求一个数的n次方
这里以3的n次方为例。
1 |
|
有很多人看到这,可能觉得这不是快速幂嘛,对,就是快速幂的思想。其实自己只要明白原理,怎么理解都行。
4.1 解释
例如 n = 13,则 n 的二进制表示为 1101, 那么 3 的 13 次方可以拆解为:
3^1101 = 3^0001 * 3^0100 * 3^1000。
即:3^13 = 3^1 * 3^4 * 3^8 。
我们可以通过 & 1和 >>1 来逐位读取 1101,为1时将该位代表的乘数累乘到最终结果。
5. 找出不大于N的最大的2的幂指数
1 |
|
5.1 解释
例如 N = 19,那么转换成二进制就是 00010011(这里为了方便,我采用8位的二进制来表示)。那么我们要找的数就是,把二进制中最左边的 1 保留,后面的 1 全部变为 0。即我们的目标数是 00010000。这个数也就是不大于N多最大的2的幂指数。那么如何获得这个数呢?解法如下:
找到最左边的 1,然后把它右边的所有 0 变成 1(注意,这里没有写错!不是上面说的将1变0,而是将0变1,具体往后看。)。
把得到的数值加 1,即 00011111 + 1 = 00100000。可以得到 00100000。这里是不是就和我们要求的数差不多了,就只是差一个位置而已。
把 得到的 00100000 向右移动一位,即 00100000 >> 1 = 00010000。即可得到 00010000。
代码实现:
1 |
|
就是通过把 n 右移并且做或运算即可得到。代码解释:
假设最左边的 1 处于二进制位中的第 k 位(从左往右数),那么把 n 右移一位之后,那么得到的结果中第 k+1 位也必定为 1,然后把 n 与右移后的结果做或运算,那么得到的结果中第 k 和 第 k + 1 位必定是 1;同样的道理,再次把 n 右移两位,那么得到的结果中第 k+2和第 k+3 位必定是 1,然后再次做或运算,那么就能得到第 k, k+1, k+2, k+3 都是 1,如此往复下去….
这里以一个简单例子为例演示过程:
假如现在的这个数n的二进制为:
00010000(n)
然后将n右移一位:
00001000(n>>1)
再把右移后的与n进行或运算(有1则为1):
00011000(新n。这时,n就是这个新数了,不再是上面的原数了。)
上述过程对应的代码就是:n |= n >> 1;
现在演示右移2位:
00011000(n)
右移:
00000110(n>>2)
再把右移后的与n进行或运算(有1则为1):
00011110(新n)
上述过程对应的代码就是:n |= n >> 2;
其他的同理可得。
然后上面的过程就把最左边的1的右边全部都变成了1,然后再在其基础上加1右移即可得到最后的答案。
即:(n + 1) >> 1。
是不是很简单!!!
6. 求两个数的平均值
1 |
|
6.1 解释
a&b:a和b按照位整齐排序。正常情况下,当a和b对应为上全为1的时候相加,那么这个位置为0(满2进1),会向前进一位。但是现在不这样做,当出现对应位全为1的时候,直接在此位保留一个1,就相当两个对应位求平均值了。这就相当,两个相同数字求平均值一样,两个相同数的平均值就是本身。2和2的平均值就是2,对应位相同为0或者为1,平均值都是本身。
a^b:这种就是和上边相反的情况。对应位相反的情况,分为a的某一个位为1,对应的b的那个位为0,或者倒过来。这个时候就要把他们异或的结果除以2,即异或的结果右移1位,这又好比两个不同的数求平均值,需要加起来除2。其中异或结果就是两个数不带进位加起来的结果。
最后,把两种结果加起来就行了。
以一个简单示例为了演示过程:
a=2; (0010)
b=6; (0110)
a&b:0010。结果为2。
a^b:0100。
(a^b)>>1:0010。结果为2。
最后结果为0100,即为4。
7. 位运算实现加减乘除
详见《星星之火-位运算实现加减乘除 》
8. 两个相同数异或
利用异或的这个特性来消除重复的数, 例如找出一个数组中落单的数(数量为奇数的某个数), 相反我们也可以利用这个特性来找出数组中唯一成对的数。结合:任何数与 0 异或等于它本身,即 n ^ 0 = n。
1 |
|
从数组中找出落单的数示例:
1 |
|
从数组中找出成对的数示例:
注意:此种方法有一个特殊的点,就是给的数组必须是1-n连续的数,并且只有唯一一个数重复,且这个重复的数还要在最后一个位置。
思想为是首先把数组中1~n-1的数与0异或一遍,然后再用这个数与数组异或。
1 |
|
解释:(网上找的)
这里使用的原理是连续的数字异或可以消除重复,A ^ A=0,( A ^ A ) ^ B ^ ( C ^ C ) =B,但是有两个元素重复,假如使用一次异或那么这个重复的元素就会被消掉了。所以这里有一个小技巧,就是使用两次异或,先对不包含重复值数组进行异或,在对包含重复值的数组进行异或,这样下来,就相当于除了重复值每个值都异或了两次,而重复的值异或了三次,这样异或下来,就只剩一个重复的值了,就成功找出来了。这里有一个特殊的点,就是这里给出了数组是1-n连续的数并且只有唯一一个元素值重复,所以才能构造进行异或两次的解法。
9. 判断一个数是否为2的整数次幂
注意:如果是负数和0需要特判。
1 |
|
9.1 方法二
如果 n 是正整数并且 n & (-n) = n,那么 n 就是 2 的幂。自行验证。
此方法具体原理见《星星之火-判断一个数是否是2的幂 》
10. 英文字符大小写转换
以下操作能够产生奇特效果的原因在于 ASCII 编码。字符其实就是数字,恰巧这些字符对应的数字通过位运算就能得到正确的结果,有兴趣的读者可以查 ASCII 码表自己算算,本文就不展开讲了。
10.1 利用或操作 | 和空格将英文字符转换为小写
1 |
|
示例:
1 |
|
10.2 利用与操作 & 和下划线将英文字符转换为大写
1 |
|
示例:
1 |
|
10.3 利用异或操作 ^ 和空格进行英文字符大小写互换
1 |
|
示例:
1 |
|
11. 判断两个数是否异号
利用的是补码编码的符号位。
1 |
|
12. 实现加1和减1、绝对值
12.1 加1
1 |
|
12.2 减1
1 |
|
12.3 绝对值
1 |
|
13. 消除二进制中的最后一个1
即最右边的1。
使用:
1 |
|
解释如下:
1 |
|
14. 从低位到高位,取n的第m位
1 |
|
15. 从低位到高位,将n的第m位变为1
1 |
|
16. 从低位到高位,将n的第m为变为0
1 |
|
本文作者: 墨水记忆
本文链接: https://tothefor.com/DragonOne/e1490b96.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!