解释按位运算符和掩码的直观方法是什么？另外，掩码是做什么用的？
What is an intuitive way to interpret the bitwise operators and masking? Also, what is masking used for?
我现在正在我的计算机系统中学习按位运算符和掩码 class。但是我在将它们内部化时遇到了一些麻烦。
我了解运算符 &、|、^、>>（算术和逻辑移位）和 << DO，但我不太明白它们除了优化乘法之外的真正用途和除法运算（对于 >> 和 <<），并检查某些位是否打开或关闭（& 运算符）。
另外，我不明白掩码是干什么用的。我知道 x & 0xFF 用于提取整数 x 中的最低有效位，但我无法真正从中推断出其他类型的掩码（例如那些提取数字中最左边的 1 的掩码，获得数字中 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 布尔成员。
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，因此 bitmap | (1ULL << i) 与 bitmap 相同，除了第 i 位也被设置（不管它以前是什么）。 bitmap |= (1ULL << i); 所做的基本上是说我想将第 i 位设置为 1，并让其他一切保持原样。这里的第 i 位用于表示第 i 个对象是否空闲，所以另一种解释方式是我想将第 i 个元素标记为已使用。
现在要测试元素 i 是否被使用，我们将使用 &:
if(bitmap & (1ULL << i)) {
// i is used
}
else {
// i is not used
}
bitmap & (1ULL << i) 只会是一个非零值，因此如果第 i 位也在 bitmap.
中设置，则为真
最后要将元素标记为未使用，我们将执行以下操作：
bitmap = bitmap & ~(1ULL << i);
或者再次更简洁
bitmap &= ~(1ULL << i);
~(1ULL << i) 将是 64 位（假设 unsigned long long 是 64 位），除第 i 位外，每个位都设置为 1。当它与 bitmap 相加时，结果与 bitmap 完全相同，只是第 i 位将设置为 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) 转换为单个常量，因此这减少了操作次数，因为只检查结构的一个成员而不是两个。
继另一个优秀的回答之后，还有一个地方要补充。 口罩。什么是面具？听起来令人印象深刻，那是什么？好吧，这只是一个 数字 ... 重要的部分 -- 是数字代表什么 。通常，当您想到掩码、数字时，您会想到掩码告诉您构成该数字的各个位的状态。
考虑一个 unsigned integer，它是 4-bytes 的信息（好吧，在 x86 机器上通常是 4 字节）。所有人都熟悉用于隔离该 unsigned int 的低字节的通用掩码 0xff。举个例子：
ui = 73289 (00000000-00000001-00011110-01001001)
byte0 = ui & 0xff; // 0xff = binary 11111111 (255)
byte0 : 73 (01001001)
所以上面的 mask 或 0xff 只不过是数字 255 恰好具有 11111111 的二进制表示，这确保 anded 与数字 ui 将给出 ui.
的第一个 8 位 （或字节）
如果您感兴趣的掩码经常更改或没有像 0xff 这样的易读的十六进制等价物，则将表示感兴趣的位的数字简单地分配给变量很有用。然后将该变量称为 bitmask。 （仅此而已，只是分配给变量的数字恰好代表您感兴趣的位状态）。
说到这里，让我们再看看esm:
给出的例子
#define PLAYER_JUMPING (1U << 0)
#define PLAYER_SWIMMING (1U << 1)
#define PLAYER_RUNNING (1U << 2)
#define PLAYER_DEAD (1U << 3)
要找到哪些玩家既是 运行 又是跳跃，我们需要做类似的事情：
if ((player[x] & (PLAYER_RUNNING | PLAYER_JUMPING)) ==
(PLAYER_RUNNING | PLAYER_JUMPING))
printf ("player[x] is running & jumping");
打字和阅读都是一团糟，但如果我们将 PLAYER_RUNNING | PLAYER_JUMPING 的结果分配给一个变量并使用该变量（我们的 bitmask），它可以变得更易于管理为了测试。例如：
mask_rj = PLAYER_RUNNING | PLAYER_JUMPING; // its value is '5' or (00000101)
if ((player[x] | mask_rj) == mask_rj)
printf ("player[x] is running & jumping");
一个使用掩码找到 运行 并跳跃的玩家的简短示例是：
#include <stdio.h>
#include <limits.h> // for CHAR_BIT
#if defined(__LP64__) || defined(_LP64)
# define BUILD_64 1
#endif
#ifdef BUILD_64
# define BITS_PER_LONG 64
#else
# define BITS_PER_LONG 32
#endif
#define PLAYER_JUMPING (1U << 0)
#define PLAYER_SWIMMING (1U << 1)
#define PLAYER_RUNNING (1U << 2)
#define PLAYER_DEAD (1U << 3)
char *binpad (unsigned long n, size_t sz);
char *binsep (unsigned long n, size_t sz, unsigned char szs, char sep);
int main (void) {
unsigned char players[] = { 0b00001000, 0b00000010,
0b00000101, 0b00000100 };
unsigned char nplayers = sizeof players/sizeof *players;
unsigned char mask_rj = PLAYER_RUNNING | PLAYER_JUMPING;
unsigned char i = 0;
printf ("\n mask_rj : %hhu (%s)\n\n",
mask_rj, binpad (mask_rj, sizeof mask_rj * CHAR_BIT));
for (i = 0; i < nplayers; i++)
printf (" player [%hhu] : %hhu (%s)\n",
i, players[i],
binpad (players[i], sizeof players[i] * CHAR_BIT));
for (i = 0; i < nplayers; i++)
if ((players[i] & mask_rj) == mask_rj)
printf ("\n player [%hhu] is Running & Jumping\n", i);
return 0;
}
char *binpad (unsigned long n, size_t sz)
{
static char s[BITS_PER_LONG + 1] = {0};
char *p = s + BITS_PER_LONG;
register size_t i;
for (i = 0; i < sz; i++)
*(--p) = (n>>i & 1) ? '1' : '0';
return p;
}
输出
$ ./bin/bitmask
mask_rj : 5 (00000101)
player [0] : 8 (00001000)
player [1] : 2 (00000010)
player [2] : 5 (00000101)
player [3] : 4 (00000100)
player [2] is Running & Jumping
我现在正在我的计算机系统中学习按位运算符和掩码 class。但是我在将它们内部化时遇到了一些麻烦。
我了解运算符 &、|、^、>>（算术和逻辑移位）和 << DO，但我不太明白它们除了优化乘法之外的真正用途和除法运算（对于 >> 和 <<），并检查某些位是否打开或关闭（& 运算符）。
另外，我不明白掩码是干什么用的。我知道 x & 0xFF 用于提取整数 x 中的最低有效位，但我无法真正从中推断出其他类型的掩码（例如那些提取数字中最左边的 1 的掩码，获得数字中 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 布尔成员。
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，因此 bitmap | (1ULL << i) 与 bitmap 相同，除了第 i 位也被设置（不管它以前是什么）。 bitmap |= (1ULL << i); 所做的基本上是说我想将第 i 位设置为 1，并让其他一切保持原样。这里的第 i 位用于表示第 i 个对象是否空闲，所以另一种解释方式是我想将第 i 个元素标记为已使用。
现在要测试元素 i 是否被使用，我们将使用 &:
if(bitmap & (1ULL << i)) {
// i is used
}
else {
// i is not used
}
bitmap & (1ULL << i) 只会是一个非零值，因此如果第 i 位也在 bitmap.
最后要将元素标记为未使用，我们将执行以下操作：
bitmap = bitmap & ~(1ULL << i);
或者再次更简洁
bitmap &= ~(1ULL << i);
~(1ULL << i) 将是 64 位（假设 unsigned long long 是 64 位），除第 i 位外，每个位都设置为 1。当它与 bitmap 相加时，结果与 bitmap 完全相同，只是第 i 位将设置为 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) 转换为单个常量，因此这减少了操作次数，因为只检查结构的一个成员而不是两个。
继另一个优秀的回答之后，还有一个地方要补充。 口罩。什么是面具？听起来令人印象深刻，那是什么？好吧，这只是一个 数字 ... 重要的部分 -- 是数字代表什么 。通常，当您想到掩码、数字时，您会想到掩码告诉您构成该数字的各个位的状态。
考虑一个 unsigned integer，它是 4-bytes 的信息（好吧，在 x86 机器上通常是 4 字节）。所有人都熟悉用于隔离该 unsigned int 的低字节的通用掩码 0xff。举个例子：
ui = 73289 (00000000-00000001-00011110-01001001)
byte0 = ui & 0xff; // 0xff = binary 11111111 (255)
byte0 : 73 (01001001)
所以上面的 mask 或 0xff 只不过是数字 255 恰好具有 11111111 的二进制表示，这确保 anded 与数字 ui 将给出 ui.
如果您感兴趣的掩码经常更改或没有像 0xff 这样的易读的十六进制等价物，则将表示感兴趣的位的数字简单地分配给变量很有用。然后将该变量称为 bitmask。 （仅此而已，只是分配给变量的数字恰好代表您感兴趣的位状态）。
说到这里，让我们再看看esm:
给出的例子#define PLAYER_JUMPING (1U << 0)
#define PLAYER_SWIMMING (1U << 1)
#define PLAYER_RUNNING (1U << 2)
#define PLAYER_DEAD (1U << 3)
要找到哪些玩家既是 运行 又是跳跃，我们需要做类似的事情：
if ((player[x] & (PLAYER_RUNNING | PLAYER_JUMPING)) ==
(PLAYER_RUNNING | PLAYER_JUMPING))
printf ("player[x] is running & jumping");
打字和阅读都是一团糟，但如果我们将 PLAYER_RUNNING | PLAYER_JUMPING 的结果分配给一个变量并使用该变量（我们的 bitmask），它可以变得更易于管理为了测试。例如：
mask_rj = PLAYER_RUNNING | PLAYER_JUMPING; // its value is '5' or (00000101)
if ((player[x] | mask_rj) == mask_rj)
printf ("player[x] is running & jumping");
一个使用掩码找到 运行 并跳跃的玩家的简短示例是：
#include <stdio.h>
#include <limits.h> // for CHAR_BIT
#if defined(__LP64__) || defined(_LP64)
# define BUILD_64 1
#endif
#ifdef BUILD_64
# define BITS_PER_LONG 64
#else
# define BITS_PER_LONG 32
#endif
#define PLAYER_JUMPING (1U << 0)
#define PLAYER_SWIMMING (1U << 1)
#define PLAYER_RUNNING (1U << 2)
#define PLAYER_DEAD (1U << 3)
char *binpad (unsigned long n, size_t sz);
char *binsep (unsigned long n, size_t sz, unsigned char szs, char sep);
int main (void) {
unsigned char players[] = { 0b00001000, 0b00000010,
0b00000101, 0b00000100 };
unsigned char nplayers = sizeof players/sizeof *players;
unsigned char mask_rj = PLAYER_RUNNING | PLAYER_JUMPING;
unsigned char i = 0;
printf ("\n mask_rj : %hhu (%s)\n\n",
mask_rj, binpad (mask_rj, sizeof mask_rj * CHAR_BIT));
for (i = 0; i < nplayers; i++)
printf (" player [%hhu] : %hhu (%s)\n",
i, players[i],
binpad (players[i], sizeof players[i] * CHAR_BIT));
for (i = 0; i < nplayers; i++)
if ((players[i] & mask_rj) == mask_rj)
printf ("\n player [%hhu] is Running & Jumping\n", i);
return 0;
}
char *binpad (unsigned long n, size_t sz)
{
static char s[BITS_PER_LONG + 1] = {0};
char *p = s + BITS_PER_LONG;
register size_t i;
for (i = 0; i < sz; i++)
*(--p) = (n>>i & 1) ? '1' : '0';
return p;
}
输出
$ ./bin/bitmask
mask_rj : 5 (00000101)
player [0] : 8 (00001000)
player [1] : 2 (00000010)
player [2] : 5 (00000101)
player [3] : 4 (00000100)
player [2] is Running & Jumping