c - 解释按位运算符和掩码的直观方法是什么？另外， mask 是做什么用的？

Question

我现在在我的计算机系统课上学习按位运算符和掩码。但是，我在将它们内化时遇到了一些麻烦。

我了解运算符 &、|、^、>>(算术和逻辑移位)和 << DO，但除了优化乘法和除法运算(对于>> 和 <<)，并检查某些位是打开还是关闭(& 运算符)。

另外，我不明白掩蔽是用来做什么的。我知道做 x & 0xFF 用于提取整数 x 中的最低有效位，但我无法真正推断出其他类型的掩码(例如，提取数字中最左边的 1 的掩码)如何获得一个数字中有多少个 1 等)被使用？

任何人都可以对此有所了解，最好举一些例子吗？谢谢你。

Answer 1

理解位掩码的一个好方法是举一个例子，所以我会给出一个例子。假设我们有一个结构数组:

struct my_struct {
  int foo;
  int bar;
};

struct my_struct array_of_structs[64]; // I picked 64 for a specific reason I will discuss later

我们将使用这个数组作为一个池，这个数组的元素根据需要分配，也可以被释放。实现此目的的一种方法是添加 used结构中的 bool 成员。

struct my_struct {
  int foo;
  int bar;
  char used;
};

但另一种方法是创建位图。由于数组的大小为 64，因此我们只需要一个 64 位整数。请注意，如果您的元素比单个数据类型中的位多，您可以使用位图的元素数组来执行此操作，但为了清楚起见，我将省略这一点。

 unsigned long long bitmap;  // Guaranteed to be at least 64 bits (if I recall correctly)

因此，让每个位对应于我们数组中的一个元素，该位的 0 表示未使用，1 表示已使用。因此标记元素i如使用的那样，我们将执行以下操作:

bitmap = bitmap | (1ULL << i);

或者更简洁:

bitmap |= (1ULL << i);

(1ULL << i)除了 i 之外，每个位都设置为 0 th 位所以 bitmap | (1ULL << i)与 bitmap 相同除了 i th 位也被设置(不管它以前是什么)。什么bitmap |= (1ULL << i);正在做的基本上是说我要设置i th 位为 1 并保留其他所有内容。 i这里的第 th 位用来表示 i对象是免费的还是不免费的，所以还有什么另一种解释方式是我想标记i所使用的元素。

现在测试元素 i是否使用我们将使用 & :

if(bitmap & (1ULL << i)) {
  // i is used
}
else {
  // i is not used
}

bitmap & (1ULL << i)将只是一个非零值，因此如果 i th 位也在 bitmap 中设置.

最后，要将元素标记为未使用，我们将执行以下操作:

bitmap = bitmap & ~(1ULL << i);

或者再次更简洁

bitmap &= ~(1ULL << i);

~(1ULL << i)将为 64 位(假设 unsigned long long 为 64 位)，除 i 外，每个位都设置为 1位。当它与 bitmap 相加时结果与 bitmap 完全相同除了 i第 th 位将被设置为 0。

有人可能想知道何时使用位图与 used多变的。在某些情况下，位图可能会更快，尽管它也可能会更慢，如果这部分成为真正的瓶颈，我会说你必须测试哪个适用于你的应用程序。当您没有自定义结构时，我可以举一个使用位图将事物标记为已使用或未使用的示例。具体来说，根据我自己的经验，我在操作系统中使用位图将物理帧标记为已使用或未使用。由于没有结构，因为我标记的是内存本身，所以位图可以工作。然而，这在寻找空闲帧方面并不是最有效的，但它确实有效。

另一个常见用途是标记属性或属性是否存在。这通常称为位标志。例如，假设我们有一个带有标志元素的播放器结构。

struct player {
  // some members
  unsigned long long flag;
};

然后我们可能有关于这个玩家的各种属性，比如正在跳跃、正在游泳、正在运行、已经死亡。我们可以创建对应于每个属性的位掩码。

#define PLAYER_JUMPING  (1ULL << 0)
#define PLAYER_SWIMMING (1ULL << 1)
#define PLAYER_RUNNING  (1ULL << 2)
#define PLAYER_DEAD     (1ULL << 3)

然后使用已经演示的类似操作来打开和关闭属性。

struct player my_player;
my_player.flag |= PLAYER_JUMPING; // Mark the player as jumping
my_player.flag &= ~PLAYER_SWIMMING; // Mark the player as not swimming
if(my_player.flag & PLAYER_RUNNING)  // Test if the player is running

最后，我之前没有演示的一个操作是按位异或:^ .您可以使用它来切换属性。

my_player.flag = my_player.flag ^ PLAYER_DEAD; // If player was dead now player is not dead and vise versa

或者更简洁:

my_player.flag ^= PLAYER_DEAD; // If player was dead now player is not dead and vise versa

这将仅影响位掩码中设置的特定位，所有其他位将保留其先前的值，即 x ^ 0 == x在位级别。

以这种方式使用位掩码时，您可以使用一个位与来测试多个属性。例如，如果您只关心玩家是在奔跑还是在跳跃，您可以执行以下操作:

if(my_player.flag & (PLAYER_RUNNING | PLAYER_JUMPING))  // Test if the player is running or jumping

请注意，几乎每个编译器都会转换 (PLAYER_RUNNING | PLAYER_JUMPING)到单个常量，因此这减少了操作的数量，因为只检查结构的一个成员而不是两个。