什么是解释按位运算符和屏蔽的直观方法？另外,掩盖用于什么？

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在结构中添加一个布尔成员.

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)已每个位设置为0,除了i个位,因此bitmap | (1ULL << i)是一样的bitmap,除了i个位设置,以及(不管是什么以前是).我bitmap |= (1ULL << i);在做什么基本上是说我想把它设置i为1并将其他所有内容保留原样.i这里的第二位用于表示该i对象是否空闲,所以另一种解释方法是我想将i第th个元素标记为已使用.

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

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

bitmap & (1ULL << i)将只是一个非零值,因此如果第in位也设置为true,则为true bitmap.

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

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

或者说再简洁一点

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

~(1ULL << i)将为64位(假设无符号长long为64位),除了该i位之外,每个位都设置为1 .当bitmap结果与结果完全相同时,bitmap除了第in位将被设置为0.

有人可能想知道何时使用位图与used变量.在某些情况下,位图可能会更快,虽然它也可能更慢,我会说你必须测试哪些适用于你的应用程序,如果这部分成为真正的瓶颈.我可以给出一个使用位图来标记已使用或未使用的内容的示例是当您没有自定义结构时.具体来说,根据我自己的经验,我在操作系统中使用位图来标记使用或未使用的物理帧.由于没有结构,因为我标记的是内存本身,位图可以工作.然而,就找到免费帧而言,这不是最有效的,但它有效.

另一个常见用途是标记属性或属性是否存在.这通常被称为位标志.例如,假设我们有一个带有flag元素的player结构.

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)为单个常量,因此这会减少操作数,因为只检查结构的一个成员而不是两个.