CODEWITHSUNDEEP
javaalgorithmbit-manipulation
Mutating Algorithm
Mutating Algorithm

Reputation: 2758

What's an intuitive way to check if a number contains two consecutive 0s in it's binary representation?

So, If I want to check that a number contains two consecutive 1s, I can simply do (n & (n >>> 1)) == 0
I'm thinking that to check if the number contains two consecutive 0's you would do the same thing but just inverting the bits: (~n & (~n >>> 1)) == 0. However, this doesn't seem to produce the correct result. It does make sense, logically, invert the bits and apply the same principle to check if two consecutive 1s are next to each other. Is there a more efficient and/ or intuitive way to do this?

Upvotes: 0

Views: 571

Answers (1)

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

If and only if n has no consecutive zeros after the first 1, the next statement makes n one less than a power of 2:

n |= n >>> 1

If and only if n is one less than a power of 2, the next statement makes n equal to zero:

n &= n + 1

Upvotes: 2

Related Questions