Chef's new friend hErd gave him two functions f and g.

The function f is defined over x (x≥ 1) as:  

f(x) = \begin{cases}
0, & \text{if } x = 1 \\
f( \frac{x}{2} ) + 1, & \text{if } x \text{ is even} \\
f( \lfloor \frac{x}{2} \rfloor ), & \text{if } x \text{ is odd} \\
\end{cases}

The function g is defined over x (x≥ 1) as:  

g(x) = \begin{cases}
1, & \text{if } x = 1 \\
2\cdot g( \frac{x}{2} ) + 1, & \text{if } x \text{ is even} \\
2\cdot g( \lfloor \frac{x}{2} \rfloor ), & \text{if } x \text{ is odd} \\
\end{cases}

where \lfloor z \rfloor, denotes the greatest integer less than or equal to z.

He also gave Chef two integers L and R. Chef has to find the maximum value of f(x)+g(x) for L ≤ x ≤ R.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The only line of each test case contains two space-separated integers L and R, as mentioned in the statement.

------ Output Format ------ 

For each test case, output on a new line the maximum value of f(x)+g(x) for L ≤ x ≤ R.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ L ≤ R ≤ 10^{9}$

----- Sample Input 1 ------ 
3
1 1
1 2
1 20
----- Sample Output 1 ------ 
1
4
35
----- explanation 1 ------ 
Test case $1$: $f(1)=0$ and $g(1)=1$. Hence, $f(x) + g(x) = 1$.

Test case $2$: There are $2$ possible values of $x$.
- $x = 1$: $f(1)+g(1)=1$ 
- $x = 2$: $f(2)+g(2)=(f(1) + 1) + (2\cdot g(1) + 1) = 1 + 3 = 4$.

Hence the maximum value of $f(x) + g(x) = 4$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics

Complete search


Solutions:
def base_2(x):
	return bin(x)[2:]

def f_plus_g(x):
	b = base_2(x)
	k = len(b) - 1
	c = b.count('0')
	return c + 2 ** (k + 1) + 2 ** k - 1 - x
for _ in range(int(input())):
	(l, r) = [int(x) for x in input().split()]
	assert l >= 1 and l <= r
	k = len(base_2(r)) - 1
	if 2 ** k >= l:
		print(k + 2 ** (k + 1) - 1)
		continue
	x = l
	mx = 0
	while x <= r:
		mx = max(mx, f_plus_g(x))
		i = (x ^ x - 1).bit_length() - 1
		x += 2 ** i
	print(mx)


a = int(input())
for i in range(a):
	(L, R) = map(int, input().split())
	ans = 0
	x = bin(L)
	y = bin(R)
	p = len(x) - 2
	q = len(y) - 2
	if q > p:
		ans = 2 ** q + q - 2
	elif q == p:
		A = []
		b = min(R - L, 30)
		c = 2 ** p - 1
		d = x.count('0') - 1
		g_L = c - (L - 2 ** (p - 1))
		f_L = d
		if L == R:
			ans = g_L + f_L
		else:
			for j in range(1, b + 1):
				t = bin(L + j).count('0') + g_L - j - 1
				A.append(t)
			f = max(A)
			ans = max(g_L + f_L, f)
	print(ans)


def FF(x):
	return format(x, 'b').count('0')

def GG(x):
	pwr2 = x.bit_length()
	return p_of_2[pwr2] + p_of_2[pwr2 - 1] - x - 1

def F_G(x):
	pwr2 = x.bit_length()
	return format(x, 'b').count('0') + p_of_2[pwr2] + p_of_2[pwr2 - 1] - x - 1
p_of_2 = {i: 2 ** i for i in range(31)}
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	if R == L:
		print(F_G(L))
		continue
	power_of_2 = max(p_of_2[R.bit_length()] - 1, L)
	if p_of_2[R.bit_length() - 1] > L:
		print(F_G(p_of_2[R.bit_length() - 1]))
		continue
	upp_lim = L + 2 * R.bit_length()
	if upp_lim > R:
		upp_lim = R + 1
	print(max((F_G(x) for x in range(L, upp_lim))))


import math

def bnary(n):
	return bin(n).replace('0b', '')

def g(x):
	if x == 1:
		return 1
	if x % 2 == 1:
		return 2 * g(x // 2)
	return 2 * g(x // 2) + 1

def f(x):
	if x == 1:
		return 0
	if x % 2 == 1:
		return f(x // 2)
	return f(x // 2) + 1

def h(x):
	return f(x) + g(x)
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	x = 1 << int(math.log(r, 2))
	if x >= l and x <= r:
		print(f(x) + g(x))
	else:
		res = h(l)
		for i in range(int(math.log(r, 2))):
			if l >> i & 1 == 1:
				if l + (1 << i) <= r:
					res = max(res, h((l >> i << i) + (1 << i)))
		print(res)


def f(n):
	ans = 0
	b = bin(n)[2:]
	for i in b[1:]:
		if i == '0':
			ans += 1
	return ans

def g(n):
	ans = 1
	b = bin(n)[2:]
	for i in b[1:]:
		ans *= 2
		if i == '0':
			ans += 1
	return ans

def solver(l, r):
	p = 1 << int(len(bin(r)) - 3)
	x = max(l, p)
	ans = f(x) + g(x)
	for i in range(30):
		if x + i <= r:
			ans = max(ans, f(x + i) + g(x + i))
	return ans
for t in range(int(input())):
	(l, r) = map(int, input().split())
	print(solver(l, r))


t = int(input())

def f(x):
	if x == 1:
		return 0
	elif not x & 1:
		return f(x // 2) + 1
	else:
		return f((x - 1) // 2)

def g(x):
	if x == 1:
		return 1
	elif not x & 1:
		return 2 * g(x // 2) + 1
	else:
		return 2 * g((x - 1) // 2)

def go(x):
	return g(x) + f(x)

def solve():
	(L, R) = [int(x) for x in input().split(' ')]
	for i in range(32, -1, -1):
		if L <= 1 << i <= R:
			print(go(1 << i))
			return
	best = go(L)
	for x in range(L + 1, min(L + 15, R + 1)):
		tmp = go(x)
		if tmp > best:
			best = tmp
	print(best)
while t:
	solve()
	t -= 1


t = int(input())
while t:
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	n = bin(b)[2:]
	l = len(n)
	x = 2 ** (l - 1)
	if x >= a:
		print(2 * x - 1 + l - 1)
	elif a > x:
		k = 2 * x - 1
		n2 = bin(x)[2:]
		mx = 0
		for j in range(a, min(a + 20, b) + 1):
			n1 = bin(j)[2:]
			c = 0
			for i in range(len(n2)):
				if n1[i] == n2[i] == '0':
					c += 1
			z = k - (j - x) + c
			if z > mx:
				mx = z
		print(mx)
	t -= 1


import sys
from math import log

def f(x):
	if x == 1:
		return 0
	if x % 2 == 0:
		return f(x // 2) + 1
	return f(x // 2)

def g(x):
	if x == 1:
		return 1
	if x % 2 == 0:
		return 2 * g(x // 2) + 1
	return 2 * g(x // 2)

def main():
	tc = int(input())
	for _ in range(tc):
		(a, b) = map(int, input().split())
		x = 1 << int(log(b, 2))
		if x >= a and x <= b:
			print(f(x) + g(x))
		else:
			ans = f(a) + g(a)
			for i in range(int(log(b, 2))):
				if a >> i & 1 == 1:
					if a + (1 << i) <= b:
						x = (a >> i << i) + (1 << i)
						ans = max(ans, f(x) + g(x))
			print(ans)
main()


import math
t = int(input())

def value1(val):
	a = int(math.log(val, 2))
	low = 2 ** a
	high = 2 ** (a + 1)
	x1 = val - low
	x2 = high - 1 - val
	if x1 > x2:
		ans = low + x2
	else:
		ans = high - 1 - x1
	return ans

def makebin(num):
	cnt = 0
	while num != 0:
		r = num % 2
		if r == 0:
			cnt += 1
		num = num // 2
	return cnt
while t != 0:
	(a, b) = map(int, input().split())
	x1 = int(math.log(a, 2))
	x2 = int(math.log(b, 2))
	m1 = 0
	if x1 == x2:
		for i in range(a, min(b + 1, a + 30)):
			m1 = max(m1, makebin(i) + value1(i))
		print(m1)
	else:
		print(x2 + 2 ** (x2 + 1) - 1)
	t = t - 1


from cmath import log
from sys import stdin
import sys
from collections import Counter
import math
input = lambda : stdin.readline().rstrip()
for _ in range(int(input())):

	def f(x):
		if x == 1:
			return 0
		if x % 2 == 0:
			return 1 + f(x // 2)
		if x % 2:
			return f(x // 2)

	def g(x):
		if x == 1:
			return 1
		if x % 2 == 0:
			return 1 + 2 * g(x // 2)
		if x % 2:
			return 2 * g(x // 2)
	(a, b) = map(int, input().split())
	ans = 0
	p = math.log2(b)
	t = pow(2, int(p))
	if t >= a:
		print(f(t) + g(t))
		continue
	for i in range(a, min(a + 14, b + 1)):
		ans = max(ans, f(i) + g(i))
	print(ans)


import math
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	if int(math.log2(l)) < int(math.log2(r)):
		n = 2 ** int(math.log2(r))
		print(int(math.log2(n)) + 2 * n - 1)
	elif int(math.log2(l)) == int(math.log2(r)):
		if math.log2(l) == int(math.log2(l)):
			print(int(math.log2(l)) + 2 * l - 1)
		else:
			b = bin(l)[2:]
			gs = ''
			for i in range(len(b)):
				if i == 0:
					gs += b[i]
				elif b[i] == '1':
					gs += '0'
				elif b[i] == '0':
					gs += '1'
			g = int(gs, 2)
			msum = g + b.count('0')
			for i in range(1, 31):
				d = l + i
				if d > r:
					break
				bd = bin(d)[2:]
				f = bd.count('0')
				if f + g - i > msum:
					msum = f + g - i
			print(msum)


t = int(input())

def f(n):
	if n == 1:
		return 0
	elif n % 2 == 0:
		return f(n // 2) + 1
	else:
		return f(n // 2)

def g(n):
	if n == 1:
		return 1
	elif n % 2 == 0:
		return 2 * g(n // 2) + 1
	else:
		return 2 * g(n // 2)
for _ in range(t):
	(l, r) = map(int, input().split())
	m = 0
	i = 2 ** 29
	flag = 0
	while i != 1:
		if i <= r and i >= l:
			print(f(i) + g(i))
			flag = 1
			break
		i = i // 2
	if flag == 0:
		m = 0
		if r - l <= 100:
			for i in range(l, r + 1):
				m = max(m, f(i) + g(i))
			print(m)
		else:
			for i in range(l, l + 15):
				m = max(m, f(i) + g(i))
			print(m)


import math

def F(x):
	if x == 1:
		return 0
	if x % 2:
		return F(x // 2)
	else:
		return F(x // 2) + 1

def G(x):
	if x == 1:
		return 1
	if x % 2:
		return G(x // 2) * 2
	else:
		return G(x // 2) * 2 + 1
for _ in range(int(input())):
	(l, r) = [int(i) for i in input().split()]
	x = 2 ** len(bin(r)[3:])
	if l > x:
		ans = []
		for i in range(15):
			ans.append(F(min(l + i, r)) + G(min(l + i, r)))
		print(max(ans))
	else:
		print(F(x) + G(x))


from math import log
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 6)

@lru_cache(None)
def f(x):
	if x == 1:
		return 0
	elif x % 2 == 0:
		return f(x // 2) + 1
	return f(x // 2)

@lru_cache(None)
def g(x):
	if x == 1:
		return 1
	return 2 * g(x // 2) + (1 if x % 2 == 0 else 0)
for i in range(int(input())):
	(l, r) = map(int, input().split())
	t = int(log(r, 2))
	p = pow(2, t)
	if l <= p <= r:
		print(f(p) + g(p))
	elif l == r:
		print(f(l) + g(l))
	else:
		res = 0
		for el in range(l, min(r, l + 30)):
			res = max(res, f(el) + g(el))
		for el in range(r, max(r - 30, l - 1), -1):
			res = max(res, f(el) + g(el))
		print(res)


f = lambda x: bin(x).count('0') - 1
g = lambda x: (~x & (1 << x.bit_length()) - 1) + (1 << x.bit_length() - 1)

def solve(l, r):
	p = 1
	best = None
	while p <= r:
		if p >= l:
			best = p
		p <<= 1
	if best is not None:
		return f(best) + g(best)
	return max((f(k) + g(k) for k in range(l, min(l + 100, r + 1))))
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	print(solve(l, r))


def LII():
	return [int(x) for x in input().split()]

def candidates(m, ln):
	if m == 0:
		return [m]
	rv = []
	while m < 2 ** ln:
		rv.append(m)
		b = bin(m)[2:]
		i = b.rindex('1')
		m += 2 ** (len(b) - 1 - i)
	return rv

def vl(x):
	b = bin(x)[2:]
	r = len(b) - 1
	c = b.count('0')
	return c + 2 ** (r + 1) + 2 ** r - 1 - x
for _ in range(int(input())):
	(l, r) = LII()
	mx = 0
	i = len(bin(l)) - 3
	assert 2 ** i <= l
	while 2 ** i <= r:
		l0 = max(l, 2 ** i)
		r0 = min(r, 2 ** (i + 1) - 1)
		for x in candidates(l0 - 2 ** i, i):
			y = x + 2 ** i
			if y <= r0 and vl(y) > mx:
				mx = vl(y)
		i += 1
	print(mx)


RI = lambda : [int(_x) for _x in input().split()]
II = lambda : int(input())
from itertools import permutations as p
from random import randint as R
import sys
import math
mod = 10 ** 9 + 7
mxn = 2 * 10 ** 5 + 10
F = [1] * mxn
m1 = {}
m2 = {}

def f(x):
	if x == 1:
		return 0
	if x in m1:
		return m1[x]
	if x & 1:
		ans = f(x // 2)
	else:
		ans = f(x // 2) + 1
	m1[x] = ans
	return ans

def g(x):
	if x == 1:
		return 1
	if x in m2:
		return m2[x]
	if x & 1:
		ans = 2 * g(x // 2)
	else:
		ans = 2 * g(x // 2) + 1
	m2[x] = ans
	return ans
for _ in range(II()):
	(l, r) = RI()
	nn = 1
	while nn * 2 <= r:
		nn *= 2
	if nn >= l:
		mid = nn
	else:
		mid = l
	mx = f(mid) + g(mid)
	for i in range(32):
		if 1 << i & mid:
			mid ^= 1 << i
		elif l <= mid | 1 << i <= r:
			mx = max(mx, f(mid | 1 << i) + g(mid | 1 << i))
	print(mx)


import math

def fplusg(x):
	f = bin(x)[2:].count('0')
	temp = 2 ** (math.floor(math.log2(x)) + 1)
	g = temp + temp // 2 - 1 - x
	return f + g
for tea in range(int(input())):
	(l, r) = map(int, input().split())
	lawl = 2 ** math.floor(math.log2(r))
	if lawl >= l:
		print(fplusg(lawl))
	else:
		ell = l
		paw = 1
		best = -1
		while ell <= r:
			best = max(best, fplusg(ell))
			paw *= 2
			if ell % paw != 0:
				ell += paw // 2
		print(best)


from random import randint
import sys
input = lambda : sys.stdin.readline().strip()
ir = lambda : int(sys.stdin.readline())
rir = lambda : range(int(sys.stdin.readline()))
mir = lambda : map(int, sys.stdin.readline().split())
lmir = lambda : list(map(int, sys.stdin.readline().split()))

def naive(l, r):
	return max((h(x) for x in range(l, r + 1)))

def smart(l, r):
	ans = 0
	i = r
	while i >= l:
		ans = max(ans, ph(i))
		i &= i - 1
	i = l
	while i <= r:
		ans = max(ans, ph(i))
		i += i - (i & i - 1)
	return ans

def debug():
	for _ in range(1000):
		args = sorted([randint(1, 1000), randint(1, 1000)])
		nn = naive(*args)
		ss = smart(*args)
		if nn != ss:
			print(args, '|', nn, ss)
	sys.exit(0)

def f(x):
	return 0 if x == 1 else f(x >> 1) + (~x & 1)

def g(x):
	return 1 if x == 1 else 2 * g(x >> 1) + (~x & 1)

def h(x):
	return f(x) + g(x)

def ph(x):
	return bin(x).count('0') + 3 * (1 << x.bit_length() - 1) - x - 2
for _ in rir():
	(l, r) = mir()
	print(smart(l, r))