位操作:清除位范围

我准备采访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) )。

我基本上和第二个function有同样的困惑。 从((1 << (i+1))减去1的具体影响是什么?从我的理解中, ((1 << (i+1))得到一个“on”位,向左移动i + 1次 – 用1减去这个数量是多少?

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

对于那些偶然有我正在引用的文本的人来说,它是在第5版的第91页。

我们假设i= 5

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

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

结论:对于给定i(1 << i) -1会给你一个掩码,其中i第一位设置为1而其他位设置为0

对于第一个问题:

i = 5想说i = 5

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

所以a & with这个掩码将最重要的位清除为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 

因此&使用此掩码清除位到索引i

第一function:

我们以i=3为例。 (1 << i)将以二进制forms产生1000 。 从中减去1给出了二进制的0111 (即1的数字)。 使用数字进行AND运算将清除除最后一位之外的所有内容,就像function描述所说的那样。

第二function:

对于第二个function,同样适用。 如果i=3 ,则((i << (i+1)) - 1)给出01111 。 波浪号反转了比特,所以我们有10000 。 这样做很重要,而不是仅仅向左移动i位,因为在我们的掩码之前可能有任意数量的有效位(因此10000可能是8位长,看起来像11110000这就是波形符号让我们得到的,只是为了清楚)。 然后,使用掩码对数字进行AND运算以获得最终结果

//要清除最重要位到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到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