Codeforces Round #276 (Div. 1) A. Bits 二进制 贪心

A. Bits

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/484/problem/A

Description

Let's denote as the number of bits set ('1' bits) in the binary representation of the non-negative integer x.

You are given multiple queries consisting of pairs of integers l and r. For each query, find the x, such that l ≤ x ≤ r, and is maximum possible. If there are multiple such numbers find the smallest of them.

Input

The first line contains integer n — the number of children in the line (1 ≤ n ≤ 106).

The second line contains n integers ai — the charisma of the i-th child ( - 109 ≤ ai ≤ 109).

Output

For each query print the answer in a separate line.

Sample Input

3
1 2
2 4
1 10

Sample Output

 

1
3
7

HINT

题意

给你q次询问，每次询问，问你l<=x<=y中，x的2进制中，1的个数最多的那个数是什么

题解：

贪心，从x开始，依次从最小位开始，把x中的0变成1，直到大于y

然后输出答案就好了

代码

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

int main()
{
    int n;scanf("%d",&n);
    while(n--)
    {
        long long x,y;scanf("%lld%lld",&x,&y);
        long long i;
        long long ans=x;
        for(i=x;i<=y;i+=~i&-~i)ans=i;
        printf("%lld
",ans);
    }
}