Check whether the number has alternating bits?

Question

I have come across the question in leetcode on checking whether the number has alternative bits or not ?. Clear explanation of the question is given below. And this question is solved in stack overflow too. Stackoverflow Solution.

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.Leetcode Question

I know how to solve the question using for loop by checking whether two bits are same or not (i.e previous bit and the present bit is same or not). But i was intrigued by the below solution in leetcode

(n & (n >> 1)) == 0 && (n & (n >> 2)) == (n >> 2)

I am concerned about the understanding behind this one line code. Examples please !!

score 1 · Answer 1 · answered Aug 13 '21 at 16:55

1

Lets start with n & (n >> 1) == 0: if the bits are alternating, then there would be 0 overlap, and so & would return 0.

The second part makes sure that the bits aren't all 0 and ensures the last bits which are discarded with the shift are still consistent

answered Aug 13 '21 at 16:55

Matthew Sanetra

11
1

Hi, I have understood the first point. Can you give me an example to understand the question point please. Thank you – James K J Aug 13 '21 at 17:00
The second part makes sure that there is no right-hand block of all 0 (trailing the final 1.) – shawnt00 Aug 13 '21 at 17:06
`1010100` would pass the first test but not the second. – shawnt00 Aug 13 '21 at 17:17
@shawnt00. I beg your pardon. I still didn't understand it. – James K J Aug 13 '21 at 20:03
In the problem statement, we're told that n is positive, so there's no need to check for all 0, but it's nice to have a more general solution too. – General Grievance Aug 13 '21 at 20:27

Check whether the number has alternating bits?

1 Answers1