Playing with Bits

0

0 votes
Basics of bit manipulation
Problem

Given an integer x. Write a Program to count the number of integers between 1 to x (both inclusive) that don't have any adjacent 1's in their binary representations.

 

Input Format:

The first line contains T, number of test cases. (1<=T<=100)
Each of the next T lines contains the integer x. (1<= x <= 10^5)


Output Format: for each line of test cases print a number denoting the number of integers between 1 to x that doesn't have any adjacent 1's in their binary representation.

 

Sample Input :
1
5
Sample Output:
4

Explanation: 1,2,4,5 don't have consecutive 1's in their binary representation but 3 ("11") has consecutive 1's.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

1,2,4,5 don't have consecutive 1's in their binary representation but 3 ("11") has consecutive 1's.

Editor Image

?