Given an integer range [A,B],  

What’s the probability to get a 1-bit if we first randomly choose a number x in the range and then randomly choose a bit from x?  
What’s the expected number of bit 1s if we randomly choose a number x in the range?  

Input Format 

The first line of input is the number of test cases $\mathbf{T}$ 

Each test cases is a line contains 2 integers $\mbox{A}$ and $\mbox{B}$ separated by a space. 

Output Format 

For each test case output a line containing 2 float numbers separated by a space. The first one is the probability and the second one is the expected number. You should output the number accurate to 5 fractional digits. 

Constraints 

$1\leq T\leq200$ 

$1\leq A\leq B\leq10^{10}$  

Sample Input

1
2 4

Sample Output

0.61111 1.33333

Explanation 

(10)  (11)  (100) 

(1) So we got a one in $\frac{1}{3}\times\frac{1}{2}+\frac{1}{3}\times\frac{1}{1}+\frac{1}{3}\times\frac{1}{3}=\frac{11}{18}$ 

(2) The expected 1 we have is : $1\times\frac{1}{3}+2\times\frac{1}{3}+1\times\frac{1}{3}=\frac{4}{3}$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Probability


Solutions:
from functools import lru_cache

@lru_cache(maxsize=None)
def s1(n):
	if n < 3:
		return n
	if n % 2 == 0:
		return s1(n // 2) + s1(n // 2 - 1) + n // 2
	return 2 * s1(n // 2) + n // 2 + 1

def s2(n):
	res = 0
	for i in range(1, 40):
		if 2 ** i > n:
			return res + (s1(n) - s1(2 ** (i - 1) - 1)) / i
		res += (1 + 1 / i) / 2 * 2 ** (i - 1)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans1 = (s2(b) - s2(a - 1)) / (b - a + 1)
	ans2 = (s1(b) - s1(a - 1)) / (b - a + 1)
	print('%.5f %.5f' % (ans1, ans2))


t = int(input())

def get_ones2(low, high):
	return get_ones1(high + 1) - get_ones1(low)

def get_ones1(x):
	bit = 0
	ret = 0
	while 1 << bit < x:
		full = x >> bit + 1
		ret += full << bit
		rest = x - (full << bit + 1)
		ret += max(rest - (1 << bit), 0)
		bit += 1
	return ret

def f(low, high):
	low_len = len(bin(low)) - 2
	high_len = len(bin(high)) - 2
	n = high - low + 1
	if low_len == high_len:
		ones = get_ones2(low, high)
		return (ones / low_len / n, ones / n)
	sum_ones = 0
	sum_fracs = 0
	for l in range(low_len, high_len + 1):
		if low_len < l < high_len:
			ones = (l - 1 << l - 2) + (1 << l - 1)
		else:
			ones = get_ones2(max(low, 1 << l - 1), min(high, (1 << l) - 1))
		sum_ones += ones
		sum_fracs += ones / l
	return (sum_fracs / n, sum_ones / n)
for _ in range(t):
	(low, high) = map(int, input().split())
	(ans, ans2) = f(low, high)
	print('{:.5f} {:.5f}'.format(ans, ans2))


__author__ = 'danielbaeck'
import math
import itertools
LIM = 1111
S = [0.0] * LIM
p2 = 0.5
for i in range(1, LIM):
	S[i] = S[i - 1] + p2 / i
	p2 *= 2
t = int(input())

def bit_length(n):
	return len(bin(n)[2:])

def bit_count(n):
	return sum([int(digit) for digit in bin(n)[2:]])

def bit_sum(n):
	return b1(n, bit_count(n)) + b2(n)

def b1(n, b):
	if n == 0:
		return 0
	if n & 1:
		return b1(n - 1, b - 1) + b - 1
	return b1(n >> 1, b) << 1

def b2(n):
	if n == 0:
		return 0
	return (b2(n >> 1) << 1) + (n >> 1)
for i in range(t):
	(A, B) = [int(x) for x in input().split(' ')]
	C = B + 1.0 - A
	(lA, bA) = (bit_length(A), bit_sum(A))
	(lB, bB) = (bit_length(B + 1), bit_sum(B + 1))
	fA = S[lA] + bA / float(lA)
	fB = S[lB] + bB / float(lB)
	p1 = (fB - fA) / C
	p2 = (bB - bA) / C
	print('{:.5f} {:.5f}'.format(p1, p2))


from functools import lru_cache

@lru_cache(maxsize=None)
def s1(n):
	if n < 3:
		return n
	if n % 2 == 0:
		return s1(n // 2) + s1(n // 2 - 1) + n // 2
	return 2 * s1(n // 2) + n // 2 + 1

def s2(n):
	res = 0
	for i in range(1, 40):
		if 2 ** i > n:
			return res + (s1(n) - s1(2 ** (i - 1) - 1)) / i
		res += (1 + 1 / i) / 2 * 2 ** (i - 1)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans1 = (s2(b) - s2(a - 1)) / (b - a + 1)
	ans2 = (s1(b) - s1(a - 1)) / (b - a + 1)
	print('%.5f %.5f' % (ans1, ans2))


from itertools import count

def main():
	ncases = int(input())
	for case in range(ncases):
		(a, b) = [int(fld) for fld in input().split()]
		print('{:.5f} {:.5f}'.format(*rirb(a, b)))

def rirb(lo, hi):
	prob1 = count1 = 0
	for (s0, s1, s_) in subintervals(lo, hi):
		num = (s1 + 0.5 * s_) * (1 << s_)
		prob1 += num / (s0 + s1 + s_)
		count1 += num
	return (prob1 / (hi - lo + 1), count1 / (hi - lo + 1))

def subintervals(lo, hi):
	start = lo
	while start <= hi:
		stop = start
		for i in count(0):
			pow2i = 1 << i
			if stop + pow2i > hi or stop & pow2i:
				yield nblanks(start, i)
				start += pow2i
				break
			stop += pow2i

def nblanks(start, i):
	s_ = i
	s0 = s1 = 0
	p = 1 << i
	while p <= start:
		if p & start:
			s1 += 1
		else:
			s0 += 1
		p <<= 1
	return (s0, s1, i)
main()


LIM = 1111
S = [0.0] * LIM
p2 = 0.5
for i in range(1, LIM):
	S[i] = S[i - 1] + p2 / i
	p2 *= 2

def bit_length(n):
	return len(bin(n)[2:])

def bit_count(n):
	return sum(map(int, bin(n)[2:]))

def bit_sum(n):
	return b1(n, bit_count(n)) + b2(n)

def b1(n, b):
	if n == 0:
		return 0
	if n & 1:
		return b1(n - 1, b - 1) + b - 1
	return b1(n >> 1, b) << 1

def b2(n):
	if n == 0:
		return 0
	return (b2(n >> 1) << 1) + (n >> 1)
for cas in range(int(input())):
	(A, B) = map(int, input().split())
	C = B + 1.0 - A
	(lA, bA) = (bit_length(A), bit_sum(A))
	(lB, bB) = (bit_length(B + 1), bit_sum(B + 1))
	fA = S[lA] + bA / float(lA)
	fB = S[lB] + bB / float(lB)
	print('%.5f %.5f' % ((fB - fA) / C, (bB - bA) / C))


def number_of_ones_between_powers_of_two(k):
	if k == 0:
		return 1
	else:
		return (1 << k) + k * (1 << k - 1)

def number_of_ones_over_power_less_than(k, b):
	n = b - (1 << k) + 1
	i = 1
	total = n
	while n >> i:
		extra = (n - (1 << i)) % (1 << i + 1)
		if extra >= 1 << i:
			extra = 0
		total += (n >> i << i - 1) + extra
		i += 1
	return total

def number_of_ones_less_than_power_greater_than(k, a):
	return number_of_ones_between_powers_of_two(k - 1) - number_of_ones_over_power_less_than(k - 1, a - 1)

def number_of_ones_between(a, b):
	k_a = length_in_binary(a) - 1
	k_b = length_in_binary(b) - 1
	total = 0
	for k in range(k_a + 1, k_b):
		total += number_of_ones_between_powers_of_two(k)
	if k_b > k_a:
		total += number_of_ones_over_power_less_than(k_b, b)
		total += number_of_ones_less_than_power_greater_than(k_a + 1, a)
	else:
		total = number_of_ones_between_powers_of_two(k_a)
		if a > 1 << k_a:
			total -= number_of_ones_over_power_less_than(k_a, a - 1)
		if b + 1 < 1 << k_b + 1:
			total -= number_of_ones_less_than_power_greater_than(k_b + 1, b + 1)
	return total

def length_in_binary(a):
	length = 0
	while a:
		a >>= 1
		length += 1
	return length

def probability(a, b):
	k_a = length_in_binary(a) - 1
	k_b = length_in_binary(b) - 1
	total = 0
	for k in range(k_a + 1, k_b):
		total += number_of_ones_between_powers_of_two(k) / (k + 1)
	if k_b > k_a:
		total += number_of_ones_over_power_less_than(k_b, b) / (k_b + 1)
		total += number_of_ones_less_than_power_greater_than(k_a + 1, a) / (k_a + 1)
	else:
		total = number_of_ones_between_powers_of_two(k_a)
		if a > 1 << k_a:
			total -= number_of_ones_over_power_less_than(k_a, a - 1)
		if b + 1 < 1 << k_b + 1:
			total -= number_of_ones_less_than_power_greater_than(k_b + 1, b + 1)
		total /= k_a + 1
	return total / (b - a + 1)

def expected(a, b):
	return number_of_ones_between(a, b) / (b - a + 1)
t = int(input().strip())
for _ in range(t):
	ab = input().strip().split(' ')
	(a, b) = (int(ab[0]), int(ab[1]))
	print('{0:.5f} {1:.5f}'.format(probability(a, b), expected(a, b)))


def bitcount(n):
	h = n >> 1
	b = 0
	x = 1
	while x < n:
		b += h & -x
		if n & x:
			b += n & x - 1
		x <<= 1
	return b
T = int(input())
for t in range(T):
	(A, B) = map(int, input().split())
	B += 1
	N = B - A
	ones = bitcount(B) - bitcount(A)
	tot = 0
	for i in range(B.bit_length()):
		lo = max(A, 1 << i)
		hi = min(B, 1 << i + 1)
		if lo < hi:
			tot += (bitcount(hi) - bitcount(lo)) / (i + 1)
	print('{:.5f} {:.5f}'.format(tot / N, ones / N))


from functools import lru_cache

@lru_cache(maxsize=None)
def s1(n):
	if n < 3:
		return n
	if n % 2 == 0:
		return s1(n // 2) + s1(n // 2 - 1) + n // 2
	return 2 * s1(n // 2) + n // 2 + 1

def s2(n):
	res = 0
	for i in range(1, 40):
		if 2 ** i > n:
			return res + (s1(n) - s1(2 ** (i - 1) - 1)) / i
		res += (1 + 1 / i) / 2 * 2 ** (i - 1)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans1 = (s2(b) - s2(a - 1)) / (b - a + 1)
	ans2 = (s1(b) - s1(a - 1)) / (b - a + 1)
	print('%.5f %.5f' % (ans1, ans2))


def count_by_length(prefix_ones, prefix_length, suffix_length):
	if prefix_length == suffix_length == 0:
		return (0, 0)
	r2 = (2 * prefix_ones + suffix_length) * 2 ** (suffix_length - 1)
	if prefix_ones > 0:
		r1 = r2 / (prefix_length + suffix_length)
		return (r1, r2)
	r1 = 0
	for i in range(suffix_length):
		r1 += (1 + i / 2) * 2 ** i / (i + 1)
	return (r1, r2)

def count_from_start(A):
	bits = [int(x) for x in f'{A:b}']
	(r1, r2) = count_by_length(0, 0, len(bits) - 1)
	prefix_ones = 1
	for (i, b) in enumerate(bits):
		if i == 0:
			continue
		if b == 0:
			continue
		(rr1, rr2) = count_by_length(prefix_ones, i + 1, len(bits) - i - 1)
		r1 += rr1
		r2 += rr2
		prefix_ones += 1
	r1 += prefix_ones / len(bits)
	r2 += prefix_ones
	return (r1, r2)

def count(A, B):
	(b1, b2) = count_from_start(B)
	if A == 1:
		return (b1 / B, b2 / B)
	A -= 1
	(a1, a2) = count_from_start(A)
	return ((b1 - a1) / (B - A), (b2 - a2) / (B - A))
for _ in range(int(input())):
	(A, B) = list(map(int, input().split()))
	(r1, r2) = count(A, B)
	print(f'{r1:.5f} {r2:.5f}')


def onesbelow(a):
	curr2pow = 1
	pow2num1s = [0]
	while curr2pow < a:
		pow2num1s.append(pow2num1s[-1] * 2 + curr2pow)
		curr2pow *= 2
	num1s = 0
	toret = 0
	pownum = len(pow2num1s) - 1
	while curr2pow > 0:
		if a & curr2pow:
			toret += pow2num1s[pownum] + curr2pow * num1s
			num1s += 1
		curr2pow //= 2
		pownum -= 1
	return toret
t = int(input())
for i in range(t):
	[a, b] = list(map(int, input().split()))
	ranges = []
	curr2pow = 1
	thepow = 0
	while curr2pow <= a:
		curr2pow *= 2
		thepow += 1
	if curr2pow > b:
		ranges.append([b + 1 - a, (onesbelow(b + 1) - onesbelow(a)) / thepow])
	else:
		ranges.append([curr2pow - a, (onesbelow(curr2pow) - onesbelow(a)) / thepow])
		while 2 * curr2pow <= b:
			thepow += 1
			ranges.append([curr2pow, (onesbelow(2 * curr2pow) - onesbelow(curr2pow)) / thepow])
			curr2pow *= 2
		thepow += 1
		ranges.append([b + 1 - curr2pow, (onesbelow(b + 1) - onesbelow(curr2pow)) / thepow])
	num = 0.0
	den = 0
	for i in ranges:
		num += i[1]
		den += i[0]
	print('%.5f %.5f' % (num / den, (onesbelow(b + 1) - onesbelow(a)) / (b + 1 - a)))


def g1s(N):
	cnt = 0
	while N:
		cnt += 1
		N -= N & -N
	return cnt

def log2k(K):
	cnt = 0
	while K > 1:
		cnt += 1
		K >>= 1
	return cnt

def get_1s(N):
	ret = 0
	while N > 0:
		k = N & -N
		ret += g1s(N - k) * k + log2k(k) * k / 2 + 1
		N -= k
	return ret

def get_1p(N):
	ret = []
	k = 0
	d = 0
	for i in range(1, 40):
		if (1 << i) - 1 <= N:
			ret.append((i + 1 << i - 1, i * 2))
			k = (1 << i) - 1
			d = i
	ret.append((get_1s(N) - get_1s(k), d + 1))
	return ret

def gcd(x, y):
	while y != 0:
		r = x % y
		x = y
		y = r
	return x
T = int(input().strip())
for ti in range(T):
	(A, B) = map(int, input().strip().split(' '))
	pb1_b = get_1p(B)
	pb1_a = get_1p(A - 1)
	fu = 0
	fv = 1
	for p in pb1_b:
		fu = fu * p[1] + p[0] * fv
		fv = p[1] * fv
		g = gcd(fu, fv)
		fu /= g
		fv /= g
	for p in pb1_a:
		fu = fu * p[1] - p[0] * fv
		fv = p[1] * fv
		g = gcd(fu, fv)
		fu /= g
		fv /= g
	pb1 = fu / fv
	nb1 = get_1s(B) - get_1s(A - 1)
	ans1 = pb1 / (B - A + 1)
	ans2 = nb1 / (B - A + 1)
	print('%.5f %.5f' % (ans1, ans2))


from functools import lru_cache

@lru_cache(maxsize=None)
def s1(n):
	if n < 3:
		return n
	if n % 2 == 0:
		return s1(n // 2) + s1(n // 2 - 1) + n // 2
	return 2 * s1(n // 2) + n // 2 + 1

def s2(n):
	res = 0
	for i in range(1, 40):
		if 2 ** i > n:
			return res + (s1(n) - s1(2 ** (i - 1) - 1)) / i
		res += (1 + 1 / i) / 2 * 2 ** (i - 1)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans1 = (s2(b) - s2(a - 1)) / (b - a + 1)
	ans2 = (s1(b) - s1(a - 1)) / (b - a + 1)
	print('%.5f %.5f' % (ans1, ans2))


from functools import lru_cache

@lru_cache(maxsize=None)
def s1(n):
	if n < 3:
		return n
	if n % 2 == 0:
		return s1(n // 2) + s1(n // 2 - 1) + n // 2
	return 2 * s1(n // 2) + n // 2 + 1

def s2(n):
	res = 0
	for i in range(1, 40):
		if 2 ** i > n:
			return res + (s1(n) - s1(2 ** (i - 1) - 1)) / i
		res += (1 + 1 / i) / 2 * 2 ** (i - 1)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans1 = (s2(b) - s2(a - 1)) / (b - a + 1)
	ans2 = (s1(b) - s1(a - 1)) / (b - a + 1)
	print('%.5f %.5f' % (ans1, ans2))