Alternating Bit Checker

Bit ManipulationMath

Given a positive integer n, determine whether its binary representation has alternating bits. That is, two adjacent bits must always have different values (for example, 1010 or 101).

Return true if n has alternating bits, and false otherwise.

Example 1

Input

[
  "5"
]

Output

true

Explanation. The binary representation of 5 is '101'. Adjacent bits alternate, so the result is true.

Example 2

Input

[
  "7"
]

Output

false

Explanation. The binary representation of 7 is '111'. Adjacent bits are identical, so the result is false.

Example 3

Input

[
  "11"
]

Output

false

Explanation. The binary representation of 11 is '1011'. The last two bits are equal ('11'), so the result is false.

Example 4

Input

[
  "10"
]

Output

true

Explanation. The binary representation of 10 is '1010'. Adjacent bits alternate, so the result is true.

Example 5

Input

[
  "1"
]

Output

true

Explanation. The binary representation of 1 is '1'. There are no adjacent bits to violate the rule, so the result is true.

Example 6

Input

[
  "1431655765"
]

Output

true

Explanation. The binary representation of 1431655765 consists of alternating '01' bits throughout 31 bits.

Follow-up: Could you perform the check in O(1) time complexity using bitwise arithmetic operations instead of a loop?

Constraints:

1 <= n <= 2^31 - 1

Views: 3