个人博客

位运算总结

2020/4/20 算法

作者：duktig

博客：https://duktig.cn (opens new window)

优秀还努力。愿你付出甘之如饴，所得归于欢喜。

本文相关源码参看：

# 位运算基础

# 位运算符

运算符 中文名称 简介
& 与 两位都为1，结果为1，否则为0
| 或 两位有一位为1，结果为1
^ 异或 相同为0，不同为1
~ 非（取反） 按位取反（符号位也取反）
<< 向左移位 向左移位，右边空位补0（-4<<1=-8，向左移一位相当于乘以2）
>> 向右移位 向右移位，左边空位负数补1，正数补0（-4<<1=-2，向右移一位相当于除以2）
>>> 无符号右移 向右移位，正负数左边都补0

# 异或的规律

  1. 异或可以理解为不进位加法：
1+1=0
0+0=0
1+0=1
1
2
3
  1. 交换律。可任意交换运算因子的位置，结果不变
a ^ b = b ^ a
1
  1. 结合律
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
1
  1. 对于任何数x，（即同自己求异或为0，同0求异或为自己）
x ^ x = 0, x ^ 0 = x
1
  1. 自反性（即连续和同一个因子做异或运算，最终结果为自己）
a ^ b ^ b = a ^ 0 = a
1

# 机器数和机器数的真值

机器数

一个数在计算机中的二进制表示形式，叫做这个数的机器数。机器数是带符号的，在计算机用机器数的最高位存放符号，正数为0，负数为1。

机器数的真值

由于机器数的第一位是符号位，所以机器数的形式值就不等于真正的数值。为了区别起见，将带符号的机器数对应的真正数值成为机器数的真值。比如0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1

# 原码、反码、补码

对于计算机而言，万物皆0、1，所有的数字最终都会转换成0、1的表示，有3种机器存储一个具体数字的编码方式，分别是：原码、反码和补码。

原码

原码表示法在数字前面增加了一位符号位，即最高位为符号位，正数位该位为0，负数位该位为1。比如十进制的5如果用8个二进制位来表示就是00000101，-5就是10000101。

反码

正数的反码是其本身，负数的反码在其原码的基础上，符号位不变，其余各个位取反。5的反码就是00000101，而-5的则为11111010。

正数的反码 = 正数的原码  
负数的反码 = ~正数的原码
1
2

补码

正数的补码是其本身，负数的补码在其原码的基础上，符号位不变，其余各位取反，最后+1。即在反码的基础上+1。5的反码就是00000101，而-5的则为11111011。 在计算机中负数采用二进制的补码表示，10进制转为二进制得到的是源码，将源码按位取反得到的是反码，反码加1得到补码

正数的补码 = 正数的反码 = 正数的原码
负数的补码 = 负数的反码 + 1 = ~正数的原码 + 1
1
2

# 位运算的技巧

# 1. 判断奇偶数

String result=(num%2==0)?"偶数":"奇数";
String result=(num&1==0)?"偶数":"奇数";
1
2

# 2. 获取二进制位是1还是0

实例：判断第五位的二进制位是1还是0

//方法一——将1左移4位，判断第五位是1还是0，然后右移4位判断0还是1）
String result1 = (num & (1 << 4) >> 4) == 0 ? "0" : "1";

//方法二——第五位二级制数右移4位，&1判断0还是1
String result2 = ((num >> 4) & 1 == 0) ? "0" : "1";
1
2
3
4
5

问题：方法一中，左移4位判断为1还是0后，还有必要在右移4位吗？

其实不右移也可以判断当前这位是否为1还是0，结果为0，说明是0；结果非0说明是1。是通过逻辑推理出来的，并不是通过结果直接看出来的。

但是并不能直接得出这一位是不是1，有时候需要确切的知道这一位的结果，那就需要右移了。

# 3. 交换两个变量的值

可参考我的另一篇博客 （Java版）算法——交换两个基本数据类型的变量值和数组中元素调换位置 (opens new window)

# 代码及运算过程
int a = 50;    //二进制 110010
int b = 60;    //二进制 111100
a = a^b;   //110010，111100——>001110
b = a^b;   //001110,111100——>110010  ——>50
a = a^b;   //001110,110010——>111100  ——>60
System.out.println(f+" "+g);//输出结果是：60 50
1
2
3
4
5
6
# 利用异或的规律证明
a = a^b;   
b = a^b;   //这里 b=a^b=(a^b)^b=a^b^b=a
a = a^b;   //这里 a=a^b=(a^b)^a=b
1
2
3

# 4. 不用判断语句，求整数的绝对值

num>>31,有符号右移，正数为0，负数为-1 num>>>31，无符号右移，正数为0，负数为1 num^0，为本身（同0求异或为自己） num^-1，相当于取反；取反在+1，相当于是绝对值

int result=(num^(num>>31))+(num>>>31);
1

# 位运算实现加减乘除

# 加法

# 思路

# 十进制实现加法的思路：

13 + 9 = 22
1
  1. 不考虑进位对各个位进行相加，记结果为sum；
  2. 考虑进位，记结果为carry；
  3. 步骤为中进位结果carry != 0，以步骤1的结果（sum）为新值，重复步骤1；如果进位结果carry == 0，则结束，结果为sum。

以 13 + 9 为例：

  1. 先计算最后一位，3 + 9 = 12 ，只看最后一位的话，sum = 2；
  2. 进位了，所以carry = 10；
  3. 计算倒数第二位，10 + 0 = 1， 即sum = 10;
  4. 不进位了，所以carry = 0，所以循环结束。
  5. 所以 2(最后一位不进位和) + 10(最后一位的进位) + 10(倒数第二位的不进位和) + 0(倒数第二位不进位，结束计算)= 22

# 二进制加法思路：

其实同上述的思路一致。以3+9为例，伪代码：

a = 0011, b = 1001;
start;
1
2
first loop;
1.1 sum = 1010
1.2 carry = 0010
1.3 carry != 0 , go on;
1
2
3
4
second loop;
2.1 sum = 1000;
2.2 carry = 0100;
2.3 carry != 0, go on;
1
2
3
4
third loop;
3.1 sum = 1100;
3.2 carry = 0000;
3.3 carry == 0, stop; result = sum;
1
2
3
4
end
1

有的加法操作是有连续进位的情况的，所以这里要在第三步检测carry是不是为0，如果为0则表示没有进位了，第一步的sum即为最终的结果。

# 代码实现

/**
 * 循环实现加法
 */
public static int add(int a, int b) {
    int carry;
    while (b != 0) {
        //进位
        carry = (a & b) << 1;
        //不进位加法
        a = a ^ b;
        b = carry;
    }
    return a;
}

/**
 * 递归实现加法
 */
private static int addRecursion(int a, int b) {
    if (b == 0) {
        // 这里 b 代表进位情况，为0时说明这次没有进位，结束递归
        return a;
    }
    //进位计算。 & 两位都为1，否则为0 , 再左移一位（ 1101 & 1001 = 1001; 01001 << 1 = 10010 ） 刚好相当于进位
    int carry = (a & b) << 1;
    //不进位加法。 ^ 相同为0，不同为1（1 ^ 1 = 0; 0 ^ 0 = 0; 1 ^ 0 = 1) 刚好满足需求 。
    a = a ^ b;
    return add(a, carry);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 减法

# 思路

减法操作，可以利用加法操作实现。例如：a+b=a+(-b)。需要将b由正数转为负数（二进制方式），然后执行加法操作。

# 为什么不实现减法器的原因：

减法比加法来的复杂，实现起来比较困难。加法运算其实只有两个操作，加、 进位。而减法呢，减法会有借位操作，如果当前位不够减那就从高位借位来做减法，这里就会问题了，借位怎么表示呢？加法运算中，进位通过与运算并左移一位实现，而借位就真的不好表示了。所以我们自然的想到将减法运算转变成加法运算。

# 正数变为负数，二进制如何改变？

通过2的补码来表示负数的，将数字的正负号变号（即取反+1）

第一步，每一个二进制位都取相反值，0变成1，1变成0（即反码）。 第二步，将上一步得到的值（反码）加1。

# 代码实现

/**
 * 减法实现
 * a - b = a + (-b) 即将b转为二进制的负数形式 然后执行加法操作即可（调用上边两个加法任意一个即可）
 * 负数 = 正数取反 + 1
 * <p>
 * 反码 = 正数取反； 补码 = 反码 +1 = 正数取反 + 1
 */
public static int subtraction(int a, int b) {
    //b由正数转为负数（取反 + 1；补码）
    b = add(~ b, 1);
    return add(a, b);
}
1
2
3
4
5
6
7
8
9
10
11
12

# 乘法

# 方法一：求乘积（推荐）

以13*14为例

被乘数为13、1101

乘数为14、1110

13*14 求乘积

如果乘数当前位为1，则取 被乘数左移一位的结果 加到最终结果中；如果当前位为0，则取0加到乘积中（加0也就是什么也不做）；

实现步骤：

  1. 将乘数与1作与运算，确定末尾位为1还是为0，如果为1，则结果相加被乘数；如果为0，什么也不做；
  2. 被乘数左移一位，乘数右移一位；回到步骤1
  3. 乘数<=0则结束循环
  4. 确定符号位，输出结果；

乘法符号位的确定：异或运算，只有一正一负结果才<0。

代码实现：

/**
 * 乘法（乘积计算，推荐方式）
 *
 * @param a 被乘数
 * @param b 乘数
 * @return 两数乘积
 */
public static int multiplication(int a, int b) {
    //将乘数和被乘数都取绝对值 （负数->正数，补码：取反+1）　
    //被乘数
    int multiplicand = a < 0 ? add(~ a, 1) : a;
    //乘数
    int multiplier = b < 0 ? add(~ b, 1) : b;

    //计算绝对值的乘积　　
    int res = 0;
    while (multiplier > 0) {
        // 每次考察乘数的最后一位， n & 0x1 代表，取n的最后一位　
        if ((multiplier & 0x1) > 0) {
            res = add(res, multiplicand);
        }
        // 每运算一次，被乘数要左移一位　　　　
        multiplicand = multiplicand << 1;
        // 每运算一次，乘数要右移一位
        multiplier = multiplier >> 1;
    }

    //计算乘积的符号（只有一正一负，才会小于0）　　
    if ((a ^ b) < 0) {
        // 将结果变为负数
        res = add(~ res, 1);
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 方法二：累加实现乘法）

乘数加上乘数倍的自己，然后处理正负号的问题。

缺点：

第一步对绝对值作乘积运算我们是通过不断累加的方式来求乘积的，这在乘数比较小的情况下还是可以接受的，但在乘数比较大的时候，累加的次数也会增多，这样的效率不是很高

代码实现：

/**
 * 乘法（累加实现，不推荐）
 *
 * @param a 被乘数
 * @param b 乘数
 * @return 两数乘积
 */
private static int multiplicationByAdd(int a, int b) {
    //被乘数
    int multiplicand = a < 0 ? add(~ a, 1) : a;
    //乘数
    int multiplier = b < 0 ? add(~ b, 1) : b;
    // 计算绝对值的乘积　　
    int res = 0;
    // 计算相加的次数，要小于被乘数
    int count = 0;
    while (count < multiplier) {
        res = add(res, multiplicand);
        // 这里可别用count++，都说了这里是位运算实现加法
        count = add(count, 1);
    }
    // 确定乘积的符号　　
    // 只考虑最高位，如果a,b异号，则异或后最高位为1；如果同号，则异或后最高位为0；
    if ((a ^ b) < 0) {
        res = add(~ res, 1);
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 除法

# 方法一：累减

  1. 被除数减除数被的自己，直到被除数小于除数时，此时所减的次数就是我们需要的商，而此时的被除数就是余数。
  2. 处理符号问题。

还有优化的空间，具体看方法二。

代码实现：

/**
 * 除法（累减实现）
 *
 * @param a 被除数
 * @param b 除数
 * @return a / b
 */
private static int division2(int a, int b) {
    // 先取被除数和除数的绝对值
    //被除数
    int dividend = a > 0 ? a : add(~ a, 1);
    // 除数
    int divisor = b > 0 ? b : add(~ b, 1);
    // 商
    int quotient = 0;
    // 余数
    int remainder = 0;
    // 不断用除数去减被除数，直到被除数小于被除数（即除不尽了）
    while (dividend >= divisor) {
        dividend = subtraction(dividend, divisor);
        // 相除一次，商加 1
        quotient = add(quotient, 1);
    }
    // 确定商的符号，如果除数和被除数异号，则商为负数
    if ((a ^ b) < 0) {
        quotient = add(~ quotient, 1);
    }
    // 确定余数符号
    remainder = b > 0 ? dividend : add(~ dividend, 1);
    // 返回商
    return quotient;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 方法二：增大步长累减（推荐）

所有的int型数据都可以用[2 ^0^, 2 ^1^,…,2 ^31^]这样一组基来表示（int型最高31位）。不难想到用除数的[2 ^31^,2 ^30^,…,2 ^2^,2 ^1^,2 ^0^]倍尝试去减被除数，如果减得动，则把相应的倍数加到商中；如果减不动，则依次尝试更小的倍数。这样就可以快速逼近最终的结果。

2的i次方其实就相当于左移i位，因为int型数据最大值就是2^31^,所以从31位开始。

代码实现：

/**
 * 除法（增大步长累减，推荐）
 *
 * @param a 被除数
 * @param b 除数
 * @return a / b
 */
public static int division(int a, int b) {
    // 先取被除数和除数的绝对值
    //被除数
    int dividend = a > 0 ? a : add(~ a, 1);
    // 除数
    int divisor = b > 0 ? b : add(~ b, 1);
    // 商
    int quotient = 0;
    // 余数
    int remainder = 0;
    for (int i = 31; i >= 0; i--) {
        /*
          比较dividend是否大于divisor的(1<<i)次方，不要将dividend与(divisor<<i)比较，而是用(dividend>>i)与divisor比较，
          效果一样，但是可以避免因(divisor<<i)操作可能导致的溢出，如果溢出则会可能dividend本身小于divisor，但是溢出导致dividend大于divisor
         */
        if ((dividend >> i) >= divisor) {
            quotient = add(quotient, 1 << i);
            dividend = subtraction(dividend, divisor << i);
        }
    }
    // 确定商的符号
    if ((a ^ b) < 0) {
        // 如果除数和被除数异号，则商为负数
        quotient = add(~ quotient, 1);
    }
    // 确定余数符号
    remainder = b > 0 ? dividend : add(~ dividend, 1);
    // 返回商
    return quotient;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 位运算常见算法题

# 唯一一个重复的数

数组1-1000中（1001个数），有唯一一个重复的数，其他数只出现一次，求唯一一个重复的数。

要求：数组元素只能访问一次，不使用辅助空间

思路：

利用位运算的异或性质解题a ^ b ^ b = a ^ 0 = a。原数组1-1000并且有一个重复的数（数组长度1001），与数组1-1000进行所有元素异或，最后剩下的是唯一重复的数，其余的数都已经抵消。

代码实现：

private static int findRepetitionNum (int[] arr) {
    int x = 0;
    //将1-1000进行运算，得出结果
    for (int i = 1; i < arr.length; i++) {
        x = (x ^ i );
    }
    //将x（将1-1000进行运算的结果）和目标数组（1-1000，并且包含一个重复的数）进行^运算
    //前后抵消，只剩下那个重复的数
    for (int i = 0; i <arr.length; i++) {
        x = x ^ arr[i];
    }
    return x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 找出单独存在的数

在一个值均成对，只有一个单独存在的数组中，找出单独存在的数。

具体参看：leetcode 136. 只出现一次的数字 (opens new window)

思路：

利用异或的性质，数组所有元素进行异或，剩下的是单一的数。a ^ b ^ b = a ^ 0 = a。

代码实现：

public int singleNumber2(int[] nums) {
    int res = 0;
    for (int num : nums) {
        res ^= num;
    }
    return res;
}
1
2
3
4
5
6
7

# 交换一个整数的二进制奇偶位

交换一个整数的二进制奇偶位

思路：

假设一个数n的二进制为 xyxy xyxy xyxy ……

  1. 和 1010 1010 1010 …… 做与运算，取出奇数位 ——>x0x0 x0x0 x0x0 ……
  2. 和 0101 0101 0101 …… 做与运算，取出偶数位 ——>0y0y 0y0y 0y0y ……
  3. 偶数位左移1位，奇数位右移1位，进行异或，交换位置——>yxyx yxyx yxyx

代码实现：

int transform ( int n ) {
    //假设n, xyxy xyxy xyxy ……
    //32位太麻烦，所以用16进制来表示
    //和 1010 1010 1010 …… 做与运算，取出奇数位  ——>x0x0 x0x0 x0x0 ……
    int ji = n & 0xaaaaaaaa;
    //和 0101 0101 0101 …… 做与运算，取出偶数位  ——>0y0y 0y0y 0y0y ……
    int ou = n & 0x55555555;
    //连起来为 yxyx yxyx yxyx ……
    return (ji >> 1) ^ (ou << 1);
}
1
2
3
4
5
6
7
8
9
10

# 整数是不是2的整数次方

整数是不是2的整数次方 要求：用一条语句判断

具体查看：leetcode 231. 2 的幂 (opens new window)

思路：

整数是2的整数次方的数，二进制只有一个1

如果可以一次消除1之后变为0，说明是2的整数次方。

(n - 1) & n 可以消除二进制中最后边的一个1（详细参看《剑指Offer》15题——二进制中1的个数）

代码实现：

boolean isTwoNum(int n) {
    return n > 0 && ((n - 1) & n) == 0;
}
1
2
3

# 0-1间浮点实数的二进制表示

给定一个0-1间的实数，例如0.625，类型为double，打印二进制表示为（0.101，因为小数点后的二进制分别为0.5,0.25.0.125……） 如果该数字无法精确地用32位以内的二进制表示，则打印"ERROR"

思路：

0-1间浮点实数的二进制计算方法：**每次乘2，扣除整数，直至变为0；**若大于32位则报错。

String transform(double n) {
    StringBuilder sb = new StringBuilder("0.");
    while (n > 0) {
        //每次乘2
        double r = n * 2;
        //判断取的整数位是0还是1
        if (r >= 1) {
            sb.append("1");
            n = r - 1;
        } else {
            sb.append("0");
            n = r;
        }
        //若大于32位则报错;34 包括 “0”和“.”
        if (sb.length() > 34) {
            return "ERROR";
        }
    }
    return sb.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 出现k次和1次的数

数组中只有一个数出现了1次，其他数都出现了k次 输出只出现一次的数

思路：

2个相同的二进制数不进位相加等于0

10个相同的十进制数不进位相加等于0

k个相同的K进制数不进位相加等于0

代码实现：

int findOneNum ( int[] arr, int k ) {
    int len = arr.length;
    //存每个数组元素的k进制的每一位
    char[][] kRadix = new char[len][];
    //数字中转成k进制最长的长度
    int maxLen = 0;
    //遍历每个数字
    for (int i = 0; i < len; i++) {
        //求每个数字的k进制并反转，然后转为字符数组；
        // 反转——从低位进行不进位加法，保证位对齐
        kRadix[i] = new StringBuffer(Integer.toString(arr[i], k)).reverse().toString().toCharArray();
        //记录数字中转成k进制最长的长度
        if (kRadix[i].length > maxLen) {
            maxLen = kRadix[i].length;
        }
    }
    //进行不进位加法
    int[] resArr = new int[maxLen];
    for (int i = 0; i < len; i++) {
        //不进位加法
        for (int j = 0; j < maxLen; j++) {
            if (j >= kRadix[i].length) {
                resArr[j] += 0;
            } else {
                //char-'0'——char转为int类型
                resArr[j] += (kRadix[i][j] - '0');
            }
        }
    }
    //将出现一次的数从k进制转为10进制
    int res = 0;
    for (int i = 0; i < maxLen; i++) {
        //(int)(Math.pow(k,i))——k的i次方
        res += (resArr[i]% k) * (int) (Math.pow(k, i));
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

具体参看：190. 颠倒二进制位 (opens new window)

思路：

将 n 视作一个长为 32 的二进制串，从低位往高位枚举 n 的每一位，将其倒序添加到翻转结果 res 中

每枚举一位就将 n 右移一位，这样当前 n 的最低位就是我们要枚举的比特位。当 n 为 0 时即可结束循环。

代码实现：

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32 && n != 0; ++ i) {
        res |= (n & 1) << (31 - i);
        n >>>= 1;
    }
    return res;
}
1
2
3
4
5
6
7
8

# 剑指offer15题——二进制中1的个数

https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/ (opens new window)

# 方法一：循环检查二进制位

思路：

循环检查给定整数 n 的二进制位的每一位是否为 1 （二进制最高为2^31^-1，所以循环条件 < 32） 缺点：无论二进制有多少个1，都要循环32次，虽然时间复杂度为O(1)，但是实际上还是有很大的优化空间

代码实现：

public int hammingWeight2(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        // 这里的判断条件不能是 == 1
        if ((n & (1 << i)) != 0) {
            count++;
        }
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10

注意：

循环中的判断条件(n & (1 << i))不能是==1，必须要是!=0才行？

  • 用n=11做测试，操作：System.out.println((n & (1 << i)));，当前位为1，发现输出的结果并不是1，而是1,2,8。
  • 又根据 101 & 010 = 000 = 0 和 111 & 010 = 010 = 2，所以确定高位为1时的条件应该为(n & (1 << i)) != 0。

# 方法二：位运算优化

思路：

  1. 最后一位是0，减1后，最后一位变成0，其他不变
  2. 最后一位不是0，假设最右边1位于m位，减去1，第m为变成0，m位之后都由0变成1，m位之前不变
  3. 减去1之后的数 与 n 进行取余，第m位之后的数变成0。 即结果： n最右边为1的位变成0

所以，先减1，然后结果对n取余。

举例：

  • 1100 -1 = 1011
  • 1011 & 1100 = 1000

代码实现：

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        ++ count;
        // 可以简写为 n &= (n-1);
        n = (n - 1) & n;
    }
    return count;
}
1
2
3
4
5
6
7
8
9