13

我正在准备使用 Gayle Laakman McDowell 的文本“Cracking the Coding Interview”进行面试。在涉及位操作的部分中，提供了两个函数，但我不太明白它是如何工作的。

// To clear all bits from the most significant bit through i (inclusive), we do:
int clearMSBthroughI(int num, int i) {
    int mask = (1 << i) - 1;
    return num & mask;
}

// To clear all bits from i through 0 (inclusive), we do:
int clearBitsIthrough0(int num, int i) {
    int mask = ~(((1 << (i+1)) - 1);
    return num & mask;
}

在第一个函数中，我(1 << i)当然知道做什么，但我不确定从这个值中减去 1 会如何影响位（即(1 << i) - 1)）。

我对第二个功能基本上有同样的困惑。减 1 有什么影响，特别是对位有什么影响((1 << (i+1))？据我了解，((1 << (i+1))结果是一个“on”位，向左移动 i+1 次——将其减去 1 有什么作用？

谢谢，我希望这很清楚！如果还有其他问题，请告诉我。

对于那些碰巧有我引用的文本的人，它在第 5 版的第 91 页。

4

4 回答 4

28

让我们假设i= 5

(1 << i)给你01000001 放在第 6 位位置

1所以现在如果我们从中减去，那么我们得到0011111==> 只有第 5 位被设置为1，其他的被设置为0，这就是我们得到掩码的方式

结论：为了i 给(1 << i) -1你一个掩码，第i一个位设置为1，其他位设置为0

于 2013-04-04T16:44:53.523 回答
6

对于第一个问题：

让我们说i = 5

(1 << i )    = 0010 0000 = 32 in base 10
(1 << i ) -1 = 0001 1111 = 31

因此，&带有此掩码的 a 将最高有效位清除为 i，因为所有位位置上方（包括索引）i都将为 0，而任何下面的位都将为 1。

对于第二个问题：

再说一次i = 5

  (1 << (i + 1))      = 0100 0000 = 64 in base 10
  (1 << (i + 1)) - 1  = 0011 1111 = 63
~((1 << (i + 1)) - 1) = 1100 0000 = 192

所以&带有这个掩码的 a 清除位到索引i

于 2013-04-04T16:53:20.693 回答
4

第一个功能：

让我们举个i=3例子。(1 << i)将产生1000二进制。从中减去 1 会得到0111二进制（即 i 个 1）。与数字相加将清除除最后 i 位之外的所有位，就像函数描述中所说的那样。

第二个功能：

对于第二个功能，同样适用。如果i=3，那么((i << (i+1)) - 1)给我们01111。波浪号反转位，所以我们有10000. 这样做很重要，而不是仅仅i向左移动位，因为在我们的掩码之前可能有任意数量的有效位（所以10000可能是 8 位长，看起来像11110000。这就是波浪号得到的，只是为了清楚） . 然后，该数字与最终结果的掩码进行“与”运算

于 2013-04-04T16:51:26.873 回答
3

// 要清除从最高有效位到 i（包括）的所有位，我们这样做：

int clearMSBthroughI(int num, int i) {
    int mask = (1 << i) - 1;
    return num & mask;
}

Take the example of i = 3
1<<3 gives you 0x00001000 
(1<<3)-1 gives you 0x00000111
num & (1<<i)-1 will clear the bits from msb to i

// 要清除从 i 到 0（含）的所有位，我们这样做：

int clearBitsIthrough0(int num, int i) {
    int mask = ~(((1 << (i+1)) - 1);
    return num & mask;
}

i = 3 的相同示例为您提供

1 <<(3+1) =0x00010000
1 <<(3+1)-1 = 0x00001111
mask =~(1<<(3+1)-1) = 0x11110000
num & mask will cleaR the bits from 0 throuh i
于 2013-04-04T16:58:57.350 回答