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 1111  即15&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 0000  即15^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 1111   即15|255 = 11111111

0.5 原码、补码

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

1
2
3
4
5
6
7
3(正数的补码和原码相同)
原码:0000 0011
补码:0000 0011
-3(负数的补码等于原码取反后再加1,符号位不反！)
原码:1000 0011
反码:1111 1100
补码:1111 1101 即int型的-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
ACM
ACM

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