I was learning a backtrack problem with memoization using bit-mask today. When checking if the ith bit is set in a bit-mask, all the solutions I came across were doing (mask >> i) & 1. I was wondering why the & 1 is necessary. Isn't (mask >> i) a 1 when the ith bit is set and a 0 when the bit is not set, which already translate into true and false?

The language is C by the way. Thanks!

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：

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.

CodePudding user response：

For example if you want to check the zero bit for the mask 0b10 then the expression mask >> 0 yields the same value 0b10 that is not equal to 0. However its zero bit 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 unequal to 0. 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.