I am learning a backtrack problem with memoization using bit-mask.

When checking if the i'th bit is set in a bit-mask, all the solutions I have come across are doing (mask >> i) & 1. I was wondering, why is the & 1 necessary? Isn't (mask >> i) a 1 when the i'th bit is set, and a 0 when the bit is not set? That already translate into true and false.

CodePudding user response：

(mask >> i) cannot eliminate the higher bits.

For example, when mask = 5 (101 in binary) and i = 1, the value of (mask >> i) is 2. This evaluated as true, but the 2nd lowest bit is 0, so you fail to check the bit correctly.

Therefore, & 1 is necessary to eliminate the higher bits and check one specified bit correctly.

CodePudding user response：

For example, if you want to check bit 0 for the mask 0b10 then the expression mask >> 0 yields the same value 0b10, that is not equal to 0. However, its bit 0 is equal to 0. So you need to write ( mask >> 0 ) & 1, or in general ( mask >> i ) & 1.

That is, higher bits that precede the i-th bit can be 1. Thus the expression mask >> i does not change their values. So the value of the expression can be unequal to 0 though the i-th bit itself is equal to 0.

CodePudding user response：

The expression (mask >> i) keeps all the bits from the i-th. That means, if either the i-th, (i 1)-th, etc. is set, then it'll evaluate to true in an if-expression.