风酥糖

fetasty

0%

位运算

发表于 分类于 阅读次数： Valine：

位运算是计算机中最常用的操作之一， 运用好位运算可以在特定情况下大幅提高计算效率

原反补码

正数的原反补码都是自身 负数的补码为原码取反，符号位不变； 补码为反码加 1, 符号位需要进位时丢弃进位符号位变 0 (进位溢出) 计算机中的数字都是以补码表示

有符号整型的二进制位

以 char (signed char, 1 字节) 为例

1
2
0 = 0000 0000 b
-1 = 1111 1111 b

移位操作

左移

以 cpp 为例，左移操作是将数据的所有二进制位都向左移动一定位数， 高位丢弃，低位补 0

左移 1 位相当于原数据乘以 \(2^1\), 左移 n 位相当于原数据乘以 \(2^n\), 高位丢弃相当于乘以 \(2^n\) 后高位溢出

‍

右移

右移操作需要分情况

  1. 有符号正数，符号位为 0, 右移低位丢弃，高位补 0
  2. 有符号负数，符号位为 1, 右移低位丢弃，高位补 1
  3. 无符号整数，右移低位丢弃，高位补 0

右移 1 位相当于数字除以 \(2^1\), 右移 n 位相当于除以 \(2^n\), 低位丢弃的数字相当于整数除法的精度丢失

‍

移位的操作效果相当于乘除 \(2^n\), 但是移位的操作效率比乘除运算的效率更高

如果整数无法被 \(2^n\) 整除， 尾部的小数部分被丢弃，相当于结果减去了小数部分，所以右移可能结果会偏小 (向下取整), 因此 -1 右移之后还是 -1, 二进制位不变

1
2
3
4
5
6
(-5) >> 1; // -3, 11111111 11111111 11111111 11111101
5 >> 1; // 2, 00000000 00000000 00000000 00000010
-1; // 11111111 11111111 11111111 11111111
-1 >> 1; // -1, 11111111 11111111 11111111 11111111
uint32_t num = (uint32_t)-1; // 4294967295, 11111111 11111111 11111111 11111111
num >> 1; // 2147483647, 01111111 11111111 11111111 11111111

‍

读写数据的二进制位

可以通过 "与" 和 "或" 操作来读写一个数据的对应位， 虽然本文源码以 C++​为例，但这在多数语言中都是相通的操作

使用 Python 时需要注意一下，Python 的整数是使用数组实现， 其长度可以无限大，不像普通语言，整数类型具有固定或有限长度

1
2
3
4
5
6
7
8
9
10
int test = 123; // C++中的int一般为32位整型
// 读取所有的二进制位
for (int i = 31; i >= 0; --i) {
  printf("%d", (test & (0x1 << i)) != 0 ? 1 : 0);
}
// 输出: 00000000000000000000000001111011
// 将倒数第2位设置为0
test &= ~(0x1 << 1); // 00000000000000000000000001111001
// 再将倒数第3位设置为1
test |= (0x1 << 2); // 00000000000000000000000001111101

这样的话，我们可以将一个整型变量当作一个 bit 数组使用， 对任意位进行读写

但是 int 只有 32 位长度，如果我们需要更大的 bit 数组怎么办呢，int64 吗？ 要是需要的长度远大于 64 呢？

我们可以使用整型数组来当作一个大的 bit 数组使用， 而且数组的内存是连续的，非常容易操作

1
2
3
4
5
6
7
8
// 我们将一个长度为5的int数组当作160位的bit数组使用
int bit_arr[5] = {0};
// 将第100位(从左到右)设置为1
int int_index = 100 / 32; // 先取得bit对应的int下标
int bit_index = (100 % 32); // 再取得bit在对应int中的下标
bit_arr[int_index] |= (0x1 << (31 - bit_index)); // int最左的1位需要左移31位才能访问
// 同理, 取得第100位的bit值也是一样的步骤, 先计算int下标, 再计算int内的bit下标
int bit_value = (bit_arr[int_index] & (0x1 << (31 - bit_index))) != 0 ? 1 : 0;

可以再进一步，将上述计算封装起来，仅对外暴露简单易用的接口， 很多语言的标准库中都封装好了，比如 cpp 中的 bitset, 有兴趣可以自己封装试试

‍

‍

数据转为二进制字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
void print_bin(T data) {
  std::string str;
  uint8_t* bytes = (uint8_t*)&data;
  auto len = sizeof(T);
  for (int i = len - 1; i >= 0; --i) {
    uint8_t v = bytes[i];
    for (int j = 8 - 1; j >= 0; --j) {
      str.append((v & (0x1 << j)) > 0 ? "1" : "0");
    }
    str.append(" ");
  }
  printf("%s\n", str.c_str());
}

数据按位取反之后得到的值是什么

先利用上述的 print_bin​看看 6​ -6​ ~6​的二进制

1
2
3
4
print_bin(6)
print_bin(-6)
printf("%d\n", ~6)
print_bin(~6)

结果如下

1
2
3
4
11111111 11111111 11111111 11111010 // -6 的二进制（补码）
00000000 00000000 00000000 00000110 // 6 的二进制（补码）
-7
11111111 11111111 11111111 11111001 // ~6 的二进制, 可以看到, 其真值为-7

​~6​为什么是 -7​呢， 其实我们将 -7​的补码写出来就会发现， 它与 ~6​的二进制完全一样

好像发现了点什么，我们再看看 ~(-6)​

1
2
3
print_bin(-6)
printf("%d\n", ~(-6))
print_bin(~(-6))

结果如下

1
2
3
11111111 11111111 11111111 11111010 // -6的二进制 (-6的补码)
5
00000000 00000000 00000000 00000101 // ~(-6)的二进制 (5的补码)

​6​取反得到 -7​, -6​取反得到 5​, 难道对一个整数取反就是它的相反数减去 1?

我们多用几个数字测试一下，包含特殊值 0

1
2
3
4
for (int i = -3; i < 4; ++i)
{
	printf("%d %d\n", i, ~i + 1);
}

结果如下，0 也符合预期

1
2
3
4
5
6
7
-3 3
-2 2
-1 1
0 0
1 -1
2 -2
3 -3

到此我们其实得到了一个普适的规律: ~n + 1 = -n​ 也就是对一个整数取反 (~) 并加 1 得到它的相反数

取得二进制位最右边的 1

1
int mostRightOne = n & (~n + 1);

根据以上章节提到的结论 ~n + 1 = -n​ 可以得到以下等价代码

1
int mostRightOne = n & (-n);

使用异或交换两个数字

  • 任何数字异或自身等于 0 a ^ a == 0​

  • 任何数字与 0 异或等于自身 a ^ 0 == a​

  • 异或满足交换律和结合律 a ^ b == b ^ aa ^ (b ^ c) == (a ^ b) ^ c​

    1
    2
    3
    4
    int a = 1, b = 2;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b:

‍