Sparse Number Checker

A number is called sparse if its binary representation does not contain two consecutive 1's. In other words, the number n is sparse if and only if

$$ n \&\ (n >> 1) = 0 $$

Given an integer n, determine whether it is sparse. Print 1 if it is sparse, or 0 otherwise.

inputFormat

The input consists of a single integer n read from stdin.

outputFormat

Output a single integer: 1 if n is sparse, otherwise 0. Output should be written to stdout.

22

0