ACM-位运算技巧和原理

本文最后更新于:April 26, 2022 pm

积土成山,风雨兴焉;积水成渊,蛟龙生焉;积善成德,而神明自得,圣心备焉。故不积跬步,无以至千里,不积小流无以成江海。齐骥一跃,不能十步,驽马十驾,功不在舍。面对悬崖峭壁,一百年也看不出一条裂缝来,但用斧凿,能进一寸进一寸,能进一尺进一尺,不断积累,飞跃必来,突破随之。

目录

今天碰到一题,让求一个数的二进制中1的个数。这个很明显的要用位运算。题目链接

然后看了一下之前写的博客,也有博客是整理了一些这方面的技巧。但是没有专门的一篇用来写位运算的,然后这一篇博客就打算专为位运算技巧而写。

有些内容在《ACM-拓展知识点 》 中,这里就没写了。

0. 位运算预知识

优先级别由高到低依次为:按位取反( ~ ),按位与( & ),按位异或( ^ ),按位或( | )。
一些特殊的重要知识点,记着,怕忘了。

  • 任何数与 0 异或等于它本身,即 n ^ 0 = n。

理论简单说一下。

0.1 按位取反(~)

这是最简单的,将0变1,1变0。

1
~15 ===> ~0b0000_1111 ===>1111 0000

0.2 按位与(&)

总结:同时为1结果才为1,否则结果为0。
0 & 0 = 0 0 & 1 = 0 1 & 0 = 0 1 & 1 =1

1
2
3
4
0000 1111
1111 1111
--------------------
0000 111115&255 = 1111

0.3 按位异或(^)

总结:不同为1,相同为0。
0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0

1
2
3
4
0000 1111
1111 1111
---------------------
1111 000015^255 = 1111 0000;

在博弈论中的尼姆博弈中会用到 。任何数与 0 异或等于它本身,即 n ^ 0 = n。

0.4 按位或(|)

总结:只要有1结果就为1,否则为0。
0 | 0 = 0 0 | 1 = 1 1 | 0 = 1 1 | 1 = 1

1
2
3
4
0000 1111
1111 1111
---------------------
1111 111115|255 = 11111111

0.5 原码、补码

在计算机中,整数是按原码(二进制)存的, 负数是按补码存的, 整数的补码和原码相同, 负数的补码等于原码取反后再加一。如:

1
2
3
4
5
6
7
3(正数的补码和原码相同)
原码:0000 0011
补码:0000 0011
-3(负数的补码等于原码取反后再加1,符号位不反!)
原码:1000 0011
反码:1111 1100
补码:1111 1101int型的-3可以表示为0b11111111_11111111_11111111_11111101

0.6 移位

左移(<<):

右移(>>):

无符号右移(>>>)

详解见《星星之火-JAVA中的>>>与>>区别》 。这里不写了。

位运算技巧

1. 判断奇数

1
2
3
if(n&1){
// n 是个奇数。
}

1.1 解释

待补充。记住即可。

2. 交换两数

1
2
3
4
int a=23;int b=7;
a=a^b; //(1)
b=a^b; //(2)
a=a^b; //(3)

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
2
3
4
5
6
7
public static int find(int[] arr){
int tmp = arr[0];
for(int i = 1;i < arr.length; i++){
tmp = tmp ^ arr[i];
}
return tmp;
}

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
2
3
4
5
6
7
8
9
10
11
12
public static int pow(int n){
int sum = 1;
int tmp = 3; //3的n次方,也可以改为其他数
while(n != 0){
if(n&1){
sum *= tmp;
}
tmp *= tmp;
n = n >> 1;
}
return sum;
}

有很多人看到这,可能觉得这不是快速幂嘛,对,就是快速幂的思想。其实自己只要明白原理,怎么理解都行。

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
2
3
4
5
6
7
public static int findN(int n){
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;// 整型一般是 32 位,这里是假设 8 位。
return (n + 1) >> 1; //加1右移
}

5.1 解释

例如 N = 19,那么转换成二进制就是 00010011(这里为了方便,我采用8位的二进制来表示)。那么我们要找的数就是,把二进制中最左边的 1 保留,后面的 1 全部变为 0。即我们的目标数是 00010000。这个数也就是不大于N多最大的2的幂指数。那么如何获得这个数呢?解法如下:

  1. 找到最左边的 1,然后把它右边的所有 0 变成 1(注意,这里没有写错!不是上面说的将1变0,而是将0变1,具体往后看。)。

  2. 把得到的数值加 1,即 00011111 + 1 = 00100000。可以得到 00100000。这里是不是就和我们要求的数差不多了,就只是差一个位置而已。

  3. 把 得到的 00100000 向右移动一位,即 00100000 >> 1 = 00010000。即可得到 00010000。

代码实现:

1
2
3
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;

就是通过把 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
2
3
4
5
6
7
8
int a=1;
int b=422;
out.println((a&b) + ((a^b) >> 1));

//正常求两个数的平均数为相加除以2,但如果是两个很大的数呢?以至于相加的结果超出了所有整数类型的范围?相加的结果超出了数据的最大范围值时。这时为防止这样的两个很大的数相加的结果超出数据类型的最大值。采用新的求法。
int a=100,b=62;
int mid2=(b-a)/2+a; //技巧算法,防止爆int
int mid3=((b-a)>>1)+a; //等价于上面

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
2
1^1  ==> 0
2^2 ==> 0

从数组中找出落单的数示例:

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
int[] arr = {1,1,1,1,2,3,3,5,6,6,2};
int x = 0;//空二进制,此处可以理解为0000 0000, 任何数与0异或结果都是其本身
for (int i : arr) {//与数组中的每一个元素异或->两个相同的数异或消除->最后只保留剩下的数
x = x ^ i;
}
System.out.println(x);
}

从数组中找出成对的数示例:
注意:此种方法有一个特殊的点,就是给的数组必须是1-n连续的数,并且只有唯一一个数重复,且这个重复的数还要在最后一个位置。
思想为是首先把数组中1~n-1的数与0异或一遍,然后再用这个数与数组异或。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    public static void main(String[] args){

int[] arr = {1,2,3,4,5,6,7,8,9,7}; //特殊点
int flag = 0;
int len = arr.length;
for (int i = 0; i < len; i++) {
flag = flag ^ i;
}
for (int i = 0; i < len; i++) {
flag = flag ^ arr[i];
}
System.out.println(flag);
}

//输出
7

解释:(网上找的)
这里使用的原理是连续的数字异或可以消除重复,A ^ A=0,( A ^ A ) ^ B ^ ( C ^ C ) =B,但是有两个元素重复,假如使用一次异或那么这个重复的元素就会被消掉了。所以这里有一个小技巧,就是使用两次异或,先对不包含重复值数组进行异或,在对包含重复值的数组进行异或,这样下来,就相当于除了重复值每个值都异或了两次,而重复的值异或了三次,这样异或下来,就只剩一个重复的值了,就成功找出来了。这里有一个特殊的点,就是这里给出了数组是1-n连续的数并且只有唯一一个元素值重复,所以才能构造进行异或两次的解法。

9. 判断一个数是否为2的整数次幂

注意:如果是负数和0需要特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n=1024,m=1023;
if((n&(n-1))==0){
System.out.println("YES");
}else {
System.out.println("NO");
}
if((m&(m-1))==0){
System.out.println("YES");
}else {
System.out.println("NO");
}

//输出
YES
NO

9.1 方法二

如果 n 是正整数并且 n & (-n) = n,那么 n 就是 2 的幂。自行验证。
此方法具体原理见《星星之火-判断一个数是否是2的幂 》

10. 英文字符大小写转换

以下操作能够产生奇特效果的原因在于 ASCII 编码。字符其实就是数字,恰巧这些字符对应的数字通过位运算就能得到正确的结果,有兴趣的读者可以查 ASCII 码表自己算算,本文就不展开讲了。

10.1 利用或操作 | 和空格将英文字符转换为小写

1
2
('a' | ' ') = 'a'
('A' | ' ') = 'a'

示例:

1
2
3
4
5
6
7
8
9
10
char ch = 'T';
char ch1 = 't';
char tch = (char) (ch | ' ');
char tch1 = (char) (ch1 | ' ');
System.out.println(tch);
System.out.println(tch1);

//输出
t
t

10.2 利用与操作 & 和下划线将英文字符转换为大写

1
2
('b' & '_') = 'B'
('B' & '_') = 'B'

示例:

1
2
3
4
5
6
7
8
9
10
char ch = 'T';
char ch1 = 't';
char tch = (char) (ch & '_');
char tch1 = (char) (ch1 & '_');
System.out.println(tch);
System.out.println(tch1);

//输出
T
T

10.3 利用异或操作 ^ 和空格进行英文字符大小写互换

1
2
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'

示例:

1
2
3
4
5
6
7
8
9
10
char ch = 'T';
char ch1 = 't';
char tch = (char) (ch ^ ' ');
char tch1 = (char) (ch1 ^ ' ');
System.out.println(tch);
System.out.println(tch1);

//输出
t
T

11. 判断两个数是否异号

利用的是补码编码的符号位。

1
2
3
4
5
int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true

int x1 = 3, y1 = 2;
boolean f1 = ((x1 ^ y1) < 0); // false

12. 实现加1和减1、绝对值

12.1 加1

1
2
3
int n = 8;
n = -~n;
System.out.println(n); //9

12.2 减1

1
2
3
int n = 12;
n = ~-n;
System.out.println(n); //11

12.3 绝对值

1
2
int n = -13;
System.out.println(~n+1); //13

13. 消除二进制中的最后一个1

即最右边的1。
使用:

1
n&(n-1)

解释如下:

1
2
3
n:      1001101100
n-1: 1001101011
n&(n-1):1001101000

14. 从低位到高位,取n的第m位

1
2
3
4
5
6
7
8
9
int n = 13;
int m = 2;
System.out.println(Integer.toBinaryString(n));
int q = (n >> (m-1)) & 1;
System.out.println(q);

//输出
1101
0

15. 从低位到高位,将n的第m位变为1

1
2
3
4
5
6
7
8
9
10
11
int n = 13;
int m = 2;
System.out.println(Integer.toBinaryString(n));
int q = n | (1 << (m-1));
System.out.println(Integer.toBinaryString(q));
System.out.println(q);

//输出
1101
1111
15

16. 从低位到高位,将n的第m为变为0

1
2
3
4
5
6
7
8
9
10
11
int n = 15;
int m = 2;
System.out.println(Integer.toBinaryString(n));
int q = n & ~(1 << (m-1));
System.out.println(Integer.toBinaryString(q));
System.out.println(q);

//输出
1111
1101
13

本文作者: 墨水记忆
本文链接: https://tothefor.com/DragonOne/2411476097.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!