位操作:清除位范围
我准备采访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