codeforces 484A Bits Ì°ÐÄ-)λÊý

codeforces 484A Bits Ì°ÐÄ-)λÊý

µã»÷´ò¿ªÁ´½Ó
A. Bits time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

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 queries (1?¡Ü?n?¡Ü?10000).<†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CkVhY2ggb2YgdGhlIGZvbGxvd2luZyA8ZW0+bjwvZW0+IGxpbmVzIGNvbnRhaW4gdHdvIGludGVnZXJzIDxlbT5sPC9lbT48ZW0+aTwvZW0+LD88ZW0+cjwvZW0+PGVtPmk8L2VtPiChqgogdGhlIGFyZ3VtZW50cyBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgcXVlcnkgKDA/odw/PGVtPmw8L2VtPjxlbT5pPC9lbT4/odw/PGVtPnI8L2VtPjxlbT5pPC9lbT4/odw/MTAxOCkuPC9wPgoKCgpPdXRwdXQKPHA+CkZvciBlYWNoIHF1ZXJ5IHByaW50IHRoZSBhbnN3ZXIgaW4gYSBzZXBhcmF0ZSBsaW5lLjwvcD4KCgoKU2FtcGxlIHRlc3QocykKCgoKaW5wdXQKPHByZSBjbGFzcz0="brush:java;">3 1 2 2 4 1 10 output

1
3
7

Note

The binary representations of numbers from 1 to 10 are listed below:

110?=?12

210?=?102

310?=?112

410?=?1002

510?=?1012

610?=?1102

710?=?1112

810?=?10002

910?=?10012

1010?=?10102

¸øÄãÒ»¸öÇø¼äl,r£¬ÈÃÄã´Ó´ËÇø¼äÖÐÕÒµ½¶þ½øÖÆÊýÖÐ1µÄ¸öÊý×î¶àµÄÄǸöÊý£¬ÈôÓжà¸ö£¬È¡×îС¡£ ½«lºÍrת»»³É¶þ½øÖÆÊý£¬ÄÇô½«ÕâÁ½¸öÊý´Ó¸ßλÍùµØλ¿ªÊ¼Åжϣ¬Èç¹ûÏàͬ£¬ÄÇô´ð°¸ÔÚÕâλÉÏÒ²ÊÇ´Ë值£¬Èç¹û²»ÏàµÈ£¬ÄÇô´ð°¸ÔÚ´ËΪÉÏΪ0£¬È»ºóʣϵĵÍλ¶¼Îª1¡£µ±È»ÌØÊâÇé¿ö¾ÍÊǵ±ÅжÏÔÚijλ²»Í¬Ê±£¬rµÄʣϵÍλȫÊÇ1£¬ÄÇôÔڴ˲»Í¬µÄλÉÏÒ²Ó¦¸ÃÊÇ1¡£

//841 ms	 2300 KB
#include
#include
#include
#define ll __int64
using namespace std;
ll s1[100007],s2[100007],s[100007];
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ll l,r;
        int num1=0,num2=0;
        scanf("%I64d%I64d",&l,&r);
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
        memset(s,0,sizeof(s));
        while(l)
        {
            s1[num1++]=l%2;
            l>>=1;
        }
        while(r)
        {
            s2[num2++]=r%2;
            r>>=1;
        }
        ll ans=0;
        int flag=0,i;
        int num=max(num1,num2);
        for(i=num-1; i>=0; i--)
        {
            if(s2[i]==s1[i])s[i]=s2[i];
            else break;
        }
        for(int k=i; k>=0; k--)
        {
            s[k]=1;
            if(!s2[k])flag=1;
        }
        if(flag)s[i]=0;
        ll aa=1;
        for(int k=0; k