谈谈Java中的位运算

技术

  1. 我们为什么要了解使用位运算？

    1. 某些场景下使用位运算比普通计算使计算机运算效率更高，更节约内存。
    2. 位运算某些场景比普通方法写出来会更简洁。
    3. 看很多比较底层的实现源码时，很多已经用了位运算，所以为了更好的了解底层实现，需要懂这相关的知识。

  2. 有关位运算的基本概念。

    1. 原码，反码，补码的概念及其意义。

      二进制机器码即可认为是原码，原码的首位是正负位。

      正数的反码与补码是其本身，负数的反码是在其原码的基础上, 符号位不变，其余各个位取反，负数的补码是在其反码上加1。

      反码与补码的意义是为了尽量简单的解决计算机做减法的问题。

    2. 位运算的六个运算符号。

      • & 与运算 两个位都是 1 时，结果才为 1，否则为 0

      • | 或运算 两个位都是 0 时，结果才为 0，否则为 1

      • ~ 异或运算，两个位相同则为 0，不同则为 1

      • ^ 取反运算，0 则变为 1，1 则变为 0

      • >> 右移运算，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位

      • << 左移运算，向左进行移位操作，高位丢弃，低位补 0

      • >>> 无符号右移运算，若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0

  3. 常用示例

  • 位操作实现乘除法

    数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2

1
2
3
int a = 2;
a >> 1; ---> 1
a << 1; ---> 4

  • 位操作交货两数

    位操作交换两数可以不需要第三个临时变量，虽然普通操作也可以做到，但是没有其效率高

1
2
3
4
5
6
7
8
9
10
11
12
13
//普通操作
void swap(int &a, int &b) {
  a = a + b;
  b = a - b;
  a = a - b;
}

//位与操作
void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}

​ 位与操作解释：第一步：a ^= b —> a = (a^b);

​ 第二步：b ^= a —> b = b^(a^b) —> b = (b^b)^a = a

​ 第三步：a ^= b —> a = (a^b)^a = (a^a)^b = b

  • 位操作判断奇偶数

    只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数。

1
2
3
if(0 == (a & 1)) {
 //偶数
}

  • 位操作交换符号

    交换符号将正数变成负数，负数变成正数

1
2
3
int reversal(int a) {
  return ~a + 1;
}

​ 整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数

  • 位操作求绝对值

    整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff），然后根据符号进行相应的操作

1
2
3
4
int abs(int a) {
  int i = a >> 31;
  return i == 0 ? a : (~a + 1);
}

​ 上面的操作可以进行优化，可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况，即 i = 0 为正，i = -1 为负。对于任 何数与 0 异或都会保持不变，与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i)，即整数时 a 与 0 异或得到本身，再减去 0，负数时与 0xffffffff 异或将 a 进行取反，然后在加上 1，即减去 i(i =-1)

1
2
3
4
int abs2(int a) {
  int i = a >> 31;
  return ((a^i) - i);
}