What does (x & (x >> 1) == 0) check for?

user_5924264 0
Viewed 167

I saw this statement in a large code base, and I don't know what this check using bit manipulation is for. Is this some standard trick in bit manipulation? If so, what is it looking for?

I know that in binary, x >> 1 shifts all the bits of x to the right 1 place, so anding that with x will guarantee the largest set bit of x becomes zero. But I just don't understand the purpose of this check.

bit-manipulation language-agnostic
1 Answers

(x & (x >> 1)) == 0 (extra parentheses added for safety) checks if there are adjacent set bits in x, and evaluates to true if there aren't.

For example:

10101010 -> true
00010000 -> true
00000011 -> false
10100110 -> false
user_5550450
Related