693. Binary Number with Alternating Bits

Problem

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

Example 1:

Input: 5
Output: True
Explanation:
The binary representation of 5 is: 101

Example 2:

Input: 7
Output: False
Explanation:
The binary representation of 7 is: 111.

Example 3:

Input: 11
Output: False
Explanation:
The binary representation of 11 is: 1011.

Example 4:

Input: 10
Output: True
Explanation:
The binary representation of 10 is: 1010.

Problem Summary

Given a positive integer, check whether it is a binary number with alternating bits: in other words, whether any two adjacent bits in its binary representation are never equal.

Solution Approach

• Determine whether any two adjacent binary bits of a number are unequal, that is, whether they alternate like 0101; if so, output true. There are multiple ways to solve this problem, and the simplest method is direct simulation. A more clever method is to use bit operations and properly construct special data to achieve the goal through bit operations. Construct 101010 from 010101; after applying the & bit operation to the two, the result is 0, because they both "fill the gaps" of each other.

Code

package leetcode

// Solution One
func hasAlternatingBits(n int) bool {
	/*
	   n =         1 0 1 0 1 0 1 0
	   n >> 1      0 1 0 1 0 1 0 1
	   n ^ n>>1    1 1 1 1 1 1 1 1
	   n           1 1 1 1 1 1 1 1
	   n + 1     1 0 0 0 0 0 0 0 0
	   n & (n+1)   0 0 0 0 0 0 0 0
	*/
	n = n ^ (n >> 1)
	return (n & (n + 1)) == 0
}

// Solution Two
func hasAlternatingBits1(n int) bool {
	last, current := 0, 0
	for n > 0 {
		last = n & 1
		n = n / 2
		current = n & 1
		if last == current {
			return false
		}
	}
	return true
}