常见位运算

发表于 | 分类于

在我们查看其它程序源码（比如jdk）的过程中，经常会看到一些位运算的使用，而且有一些场景下我们使用简单常用的位运算既不会太影响可读性又能增加性能，这里列出了一些常见的位运算的使用

奇偶

1
2
// 偶数
n & 1 == 0

交换数

1
2
3
a ^= b;  
b ^= a; // b = b^(a^b) = a
a ^= b; // a = (a^b)^a = b

变换符号

变换符号就是正数变成负数，负数变成正数

由于负数使用补码，所以变换符号只需要：~a + 1

求绝对值

  1. 获取正负数（0：正数， -1：负数）
  2. 变换符号
1
2
3
// long需要移动63
int i = a >> 31;  
return i == 0 ? a : (~a + 1);

判断一个数是不是2的幂

a & (a - 1) == 0

2的N次方取模

因为2的N次-1所有的二进制低位都是1

m & ((1 << N) - 1) <==> m % 2^N

高低位交换

右移得到高位，左移得到高位，移动值为总位数的一半

1
2
// 16位数的高低位交换
a = (a >> 8) | (a << 8);

N位二进制的范围和取高低位

N位二进制的范围：0 到 (1 << N) - 1

  1. 取高16位: a >> 16
  2. 取低16位: a & 0x0000FFFF 或者 a & ((1 << 16) - 1)

二进制逆序

先2位一组进行交换，再以乘以2为一组进行交换，一直到一组数量等于总位数

  • (取高位)取16位的 a 的奇数位并将偶数位用0填充用代码实现就是：a & 0xAAAA
  • (取低位)取16位的 a 的偶数位并将奇数位用0填充用代码实现就是：a & 0x5555
1
2
3
4
5
6
7
8
9
10
// A = 1010, 5 = 0101
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
// C = 1100, 3 = 0011
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
// F0 = 11110000, 0F = 00001111
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
// FF00 = 1111111100000000, 00FF = 0000000011111111
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);
// FFFF0000, 0000FFFF
a = ((a & 0xFFFF0000) >> 16) | ((a & 0x0000FFFF) << 16);

二进制中1的个数

先2位一组进行相加，再以乘以2为一组进行相加，一直到一组数量等于总位数

1
2
3
4
5
// 高位与低位相加
a = ((a & 0xAAAA) >> 1) + (a & 0x5555);
a = ((a & 0xCCCC) >> 2) + (a & 0x3333);
a = ((a & 0xF0F0) >> 4) + (a & 0x0F0F);
a = ((a & 0xFF00) >> 8) + (a & 0x00FF);

取不小于m的最小的2的n次方的数

即：(1 << n) >= m

算法基本原理是将这个数的最高位1以下的每一位都置为1，然后+1得到2的n次方的数即可，因此：

  • 右移1位后取或至少有2个1（最高位的1 + 1）
  • 类推第二次右移2位后取或至少有4个1（2 + 2）
  • 类推…

如果这个数恰好是你所需要的2的n次方的数，就不大好，所以在实际计算的时候会先减去1

1
2
3
4
5
6
7
8
9
10
// java HashMap
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}