Bits (Codeforces 485C)
Tags: Implement, math

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).Each of the following n lines contain two integers li, ri — the arguments for the corresponding query (0 ≤ li ≤ ri ≤ 1018).

Output: For each query print the answer in a separate line.

Note: The binary representations of numbers from 1 to 10 are listed below:110 = 12210 = 102310 = 112410 = 1002510 = 1012610 = 1102710 = 1112810 = 10002910 = 100121010 = 10102

Sample Inputs:
3
1 2
2 4
1 10

Sample Outputs:
1
3
7

Solution (Python):
from sys import stdin

def parseline(line):
    return list(map(int, line.split()))

def round_to_power_of_2(k):
    k |= k >> 1
    k |= k >> 2
    k |= k >> 4
    k |= k >> 8
    k |= k >> 16
    k += 1
    return k

def is_power_of_2(k):
    return 0 == k & k - 1
if __name__ == '__main__':
    lines = list(filter(None, stdin.read().split('\n')))
    lines = list(map(parseline, lines))
    (n,) = lines[0]
    for (li, ri) in lines[1:n + 1]:
        z = round_to_power_of_2(li ^ ri)
        mask = z - 1
        if is_power_of_2((ri & mask) + 1):
            print(ri)
        else:
            pos = z >> 1
            print(ri ^ pos | pos - 1)

Solution (Python):
t = int(input())
for _ in range(t):
    (l, r) = map(int, input().split())
    res = l
    for i in range(64):
        if res & 1 << i == 0:
            x = res + (1 << i)
            if x <= r:
                res = x
    print(res)

Solution (Python):
""""""
from math import ceil, sqrt, log, gcd

def ii():
    return int(input())

def si():
    return input()

def mi():
    return map(int, input().split())

def li():
    return list(mi())

def main():
    n = ii()
    for i in range(n):
        (l, r) = mi()
        s1 = bin(r)[2:]
        n1 = len(s1)
        s2 = bin(l)[2:]
        s2 = '0' * (n1 - len(s2)) + s2
        s2 = list(s2)
        s1 = list(s1)
        x = s1.count('1')
        f = 0
        f1 = -1
        for i in range(n1):
            if f == 1:
                s2[i] = '1'
            elif s1[i] != s2[i]:
                f1 = i
                f = 1
        if f1 != -1:
            s3 = s2[:]
            s3[f1] = '1'
            s3 = ''.join(s3)
            x = int(s3, 2)
            if x <= r:
                print(x)
            else:
                s2 = ''.join(s2)
                print(int(s2, 2))
        else:
            s2 = ''.join(s2)
            print(int(s2, 2))
if __name__ == '__main__':
    main()