Understanding $2$'s complement representation is fundamental to learning about Computer Science. It allows us to write negative numbers in binary.  The leftmost digit is used as a sign bit.  If it is $1$, we have a negative number and it is represented as the two's complement of its absolute value.  Let's say you wrote down the $2$'s complement representation for each $32$-bit integer in the inclusive range from $\boldsymbol{a}$ to $\boldsymbol{b}$.  How many $1$'s would you write down in all?  

For example, using an $8$-bit byte rather than $32$ bit integer, the two's complement of a number can be found by reversing all its bits and adding $1$.  The two's complement representations for a few numbers are shown below:  

        |Number|                Representation in
Number   Binary     Inverse     Two's Complement
-3      00000011    11111100    11111101
-2      00000010    11111101    11111110
-1      00000001    11111110    11111111
 0      00000000                00000000
 1      00000001                00000001
 2      00000010                00000010
 3      00000011                00000011

To write down that range of numbers' two's complements in $8$ bits, we wrote $\textbf{26}\:1$'s.  Remember to use $32$ bits rather than $8$ in your solution.  The logic is the same, so the $8$ bit representation was chosen to reduce apparent complexity in the example.  

Function Description  

Complete the twosCompliment function in the editor below.  It should return an integer.  

twosCompliment has the following parameter(s): 

- a: an integer, the range minimum 

- b: an integer, the range maximum  

Input Format

The first line contains an integer $\mathbf{T}$, the number of test cases.   

Each of the next $\mathbf{T}$ lines contains two space-separated integers, $\boldsymbol{a}$ and $\boldsymbol{b}$.  

Constraints

$T\leq1000$
$-2^{31}\leq a\leq b\leq2^{31}-1$

Output Format

For each test case, print the number of $\mbox{I}$'s in the $32$-bit $2$'s complement representation for integers in the inclusive range from $\boldsymbol{a}$ to $\boldsymbol{b}$ on a new line.

Sample Input 0
3
-2 0
-3 4
-1 4

Sample Output 0
63
99
37

Explanation 0

Test case 0 

-2 has 31 ones 

-1 has 32 ones 

0 has 0 ones 

31+32+0 = 63 

Test case 1 

-3 has 31 ones 

-2 has 31 ones 

-1 has 32 ones 

0 has 0 ones 

1 has 1 ones 

2 has 1 ones 

3 has 2 ones 

4 has 1 ones 

31+31+32+0+1+1+2+1 = 99 

Test case 2 

-1 has 32 ones 

0 has 0 ones 

1 has 1 ones 

2 has 1 ones 

3 has 2 ones 

4 has 1 ones 

32+0+1+1+2+1 = 37  

Sample Input 1
4
-5 0
1 7
-6 -3
3 6

Sample Output 1
155
12
122
7

Explanation 1

Test case 0 

-5 has 31 ones 

-4 has 30 ones 

-3 has 31 ones 

-2 has 31 ones 

-1 has 32 ones 

0 has 0 ones 

31+30+31+31+32+0 = 155 

Test case 1 

1 has 1 ones 

2 has 1 ones 

3 has 2 ones 

4 has 1 ones 

5 has 2 ones 

6 has 2 ones 

7 has 3 ones 

1+1+2+1+2+2+3 = 12 

Test case 2 

-6 has 30 ones 

-5 has 31 ones 

-4 has 30 ones 

-3 has 31 ones 

30+31+30+31 = 122 

Test case 3 

3 has 2 ones 

4 has 1 ones 

5 has 2 ones 

6 has 2 ones 

2+1+2+2 = 7

Difficulty: HARD
Tags: Bit manipulation
Skill types: Bit manipulation

Starter code:

Solutions:
t = int(input())

def gen(num):
	if num == '':
		return 0
	elif num == '1':
		return 1
	elif num == '0':
		return 0
	elif num[0] == '0':
		return gen(num[1:])
	else:
		return int(num[1:], 2) + 1 + gen(num[1:]) + 2 ** (len(num) - 2) * (len(num) - 1)

def func(a, b):
	if a < 0 and b >= 0:
		if a + b + 1 == 0:
			return 32 * (b + 1)
		elif a + b + 1 < 0:
			return 32 * (b + 1) + func(a, -(b + 2))
		else:
			return 32 * -a + func(-a, b)
	elif a < 0 and b < 0:
		return 32 * (b - a + 1) - func(-b - 1, -a - 1)
	else:
		if a == 0:
			return gen(bin(b)[2:])
		return gen(bin(b)[2:]) - gen(bin(a - 1)[2:])
for ts in range(t):
	(a, b) = input().strip().split()
	(a, b) = (int(a), int(b))
	print(func(a, b))


def CountBits(val):
	return '{:b}'.format(val).count('1')

def SumToBit(bit):
	if bit < 0:
		return 0
	return bit + 1 << bit

def SumUpA(val, bits):
	totalSum = 0
	newBit = -1
	while val != (2 << bits) - 1:
		orig = val
		while orig == val:
			newBit += 1
			val |= 1 << newBit
		totalSum += SumToBit(newBit) - SumToBit(newBit - 1) + CountBits((val & ~((2 << newBit) - 1)) >> newBit) * (val - orig)
	return totalSum

def SumUp(val):
	return CountBits(val) + SumUpA(val, val.bit_length() - 1)

def NewSum(a, b):
	if a < 0:
		a = twos_comp(a)
		base = SumUp(a)
		baseBits = 0
	elif a == 0:
		base = 0
		baseBits = 0
	else:
		base = SumUp(a)
		baseBits = a.bit_length()
	if b < 0:
		b = twos_comp(b)
		cap = SumUp(b)
		targetBits = 0
	elif b == 0:
		cap = 0
		targetBits = 0
	else:
		cap = SumUp(b)
		targetBits = b.bit_length()
	baseToCap = SumToBit(targetBits - 1) - SumToBit(baseBits - 1)
	return base + baseToCap - cap + CountBits(b)

def twos_comp(val):
	return 4294967296 + val
tests = int(input())
for t in range(tests):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	print(NewSum(a, b))


n = 1 << 32

def h(x):
	res = 0
	while x > 0:
		res += x & 1
		x >>= 1
	return res

def g(x):
	if x <= 1:
		return x
	if x & 1:
		return 2 * g(x >> 1) + (x + 1) // 2
	return g(x - 1) + h(x)

def f(a, b):
	if a == 0:
		return g(b)
	if a > 0:
		return g(b) - g(a - 1)
	if b >= 0:
		return g(b) + f(n + a, n - 1)
	return f(a, 0) - f(b + 1, 0)
for T in range(int(input())):
	print(f(*map(int, input().split())))


MAXBITS = 32

def count(n):
	if n >= 0:
		return poscount(n)
	else:
		n += 1
		return poscount(-1 - n) + n * MAXBITS if n != 0 else 0

def poscount(n):
	if n == 0:
		return 0
	else:
		nbits = n.bit_length() - 1
		msb = 1 << nbits
		rem = n - msb
		return msb * nbits // 2 + rem + poscount(rem) + 1
ncases = int(input())
for case in range(ncases):
	(a, b) = [int(fld) for fld in input().split()]
	print(count(b) - count(a - 1))


import math

def sumOf1s(pattern, n):
	if int(0.5 * (1 + math.pow(-1, int(n / pattern + 1)))) == 1:
		return int(n // (pattern * 2) * pattern * 2 / 2) + (n % pattern + 1)
	else:
		return int(n // pattern * pattern / 2)

def solve(a, b):
	a -= 1
	sumA = sum((sumOf1s(2 ** y, abs(-2 ** 32 - a)) for y in range(32)))
	sumB = sum((sumOf1s(2 ** y, abs(-2 ** 32 - b)) for y in range(32)))
	return sumB - sumA
T = int(input())
for _ in range(T):
	(a, b) = (int(x) for x in input().split(' '))
	print(solve(a, b))


def count_pos(num):
	if num == 0:
		return 0
	total = 0
	for curr_bit in range(32):
		total += num // (2 << curr_bit) << curr_bit
		total += max(0, num % (2 << curr_bit) - ((1 << curr_bit) - 1))
	return total

def count_neg(num):
	if num == 0:
		return 0
	assert num < 0
	total = -num * 32
	zeros = count_pos(-num - 1)
	return total - zeros

def count(a, b):
	if b < 0:
		return count_neg(a) - count_neg(b + 1)
	elif a > 0:
		return count_pos(b) - count_pos(a - 1)
	elif a == 0:
		return count_pos(b)
	elif b == 0:
		return count_neg(a)
	else:
		return count_neg(a) + count_pos(b)
cases = int(input())
for _ in range(cases):
	nums = [int(x) for x in input().split()]
	result = count(*nums)
	print(result)


n = int(input())
memo = {0: 1}

def count_bit_2exp(k):
	if k in memo:
		return memo[k]
	result = 1 + 2 * (count_bit_2exp(k - 1) - 1) + 2 ** (k - 1)
	memo[k] = result
	return result

def count_bit(n):
	if n < 0:
		return 32 * -n - count_bit(-n - 1)
	result = 0
	hbit = 0
	for b in reversed(range(31)):
		if n & 2 ** b:
			result += count_bit_2exp(b) + hbit * 2 ** b
			hbit += 1
	return result
for i in range(n):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	if a > 0:
		print(count_bit(b) - count_bit(a - 1))
	elif b < 0:
		print(count_bit(a) - count_bit(b + 1))
	else:
		print(count_bit(a) + count_bit(b))


def GetOnes(val, f):
	ones = 0
	rest = 0
	neg = False
	if val < 0:
		val = -val - 1
		neg = True
	for i in range(0, 31):
		mask = 1 << i
		if val & mask:
			ones += f[i] + (rest + 1)
			rest ^= val & mask
	if neg:
		ones = 32 * (val + 1) - ones
	return ones
f = [0 for x in range(0, 32)]
f[1] = 1
cum = 1
for i in range(2, 32):
	f[i] = 2 * f[i - 1] + 2 ** (i - 1)
tests = int(input().strip())
for q in range(0, tests):
	(a, b) = [int(x) for x in input().split()]
	ones = 0
	if a <= 0 and b >= 0:
		onesA = GetOnes(a, f)
		onesB = GetOnes(b, f)
		ones = onesA + onesB
	elif a < 0 and b < 0:
		onesA = GetOnes(a, f)
		onesB = GetOnes(b + 1, f)
		ones = onesA - onesB
	elif a > 0 and b > 0:
		onesA = GetOnes(a - 1, f)
		onesB = GetOnes(b, f)
		ones = onesB - onesA
	print(ones)


T = int(input())

def memoize(function):
	memo = {}

	def wrapper(*args):
		if args in memo:
			return memo[args]
		else:
			rv = function(*args)
			memo[args] = rv
			return rv
	return wrapper

@memoize
def ones_from_0(A):
	if A == 0:
		return 0
	if A < 0:
		return ones_from_0(2 ** 32 - 1) - ones_from_0(2 ** 32 + A - 1)
	msb = 1 << A.bit_length() - 1
	high_part = A ^ msb
	low_part = msb - 1
	high_part_cnt = ones_from_0(high_part)
	if high_part == low_part:
		low_part_cnt = high_part_cnt
	else:
		low_part_cnt = ones_from_0(low_part)
	return high_part_cnt + (high_part + 1) + low_part_cnt
for _ in range(T):
	(A, B) = [int(s) for s in input().split(' ')]
	if B >= 0 and A < 0:
		print(ones_from_0(B) + ones_from_0(A))
	elif B >= 0 and A >= 0:
		print(ones_from_0(B) - ones_from_0(max(0, A - 1)))
	else:
		print(ones_from_0(A) - ones_from_0(B + 1))


def to_bin(x):
	if x < 0:
		x += 1 << 32
	return bin(x)[2:]

def naive(a, b):
	(a, b) = (min(a, b), max(a, b))
	s = 0
	for i in range(a, b + 1):
		s += to_bin(i).count('1')
	return s

def sum_1_by_pos(x, i):
	b = 2 ** i
	if x % (2 * b) >= b:
		return x // (2 * b) * b + x % b + 1
	else:
		return x // (2 * b) * b

def to_positive(x):
	l = len(bin(x)) - 2
	per_pos = [sum_1_by_pos(x, i) for i in range(l)]
	return sum(per_pos)

def to_negative(x):
	x = abs(x)
	return 32 * x - to_positive(x - 1)

def smart(a, b):
	(a, b) = (min(a, b), max(a, b))
	if a >= 0 and b >= 0:
		sa = to_positive(a - 1)
		sb = to_positive(b)
		return sb - sa
	if a < 0 and b >= 0:
		sa = to_negative(a)
		sb = to_positive(b)
		return sa + sb
	if a < 0 and b < 0:
		sb = to_negative(b + 1)
		sa = to_negative(a)
		return sa - sb

def main():
	t = int(input())
	for _ in range(t):
		(a, b) = map(int, input().split(' '))
		print(smart(a, b))
main()


def Ones(x):
	if x < 0:
		x = (1 << 32) + x
	BitAtOnes = []
	for i in range(32):
		if x & 1:
			BitAtOnes.append(i)
		x //= 2
	return BitAtOnes

def Zeroes(x):
	return Ones(~x)

def TotalOnesPos(x):
	OneIdx = Ones(x)[::-1]
	Total = 0
	for (i, Idx) in enumerate(OneIdx):
		Total += i * (1 << Idx) + Idx * (1 << Idx) // 2
	Total += len(OneIdx)
	return Total

def TotalOnesNeg(x):
	ZeroIdx = Zeroes(x)[::-1]
	Total = 0
	for (i, Idx) in enumerate(ZeroIdx):
		Total += (32 - i - Idx) * (1 << Idx) + Idx * (1 << Idx) // 2
	Total += 32 - len(ZeroIdx)
	return Total

def TotalOnes(x):
	if x < 0:
		return TotalOnesNeg(x)
	return TotalOnesPos(x)

def Sign(x):
	if x < 0:
		return -1
	return 1
T = int(input().strip())
for dummyT in range(T):
	(A, B) = [int(x) for x in input().strip().split()]
	if Sign(A) == Sign(B):
		if Sign(A) > 0:
			print(TotalOnes(B) - TotalOnes(A) + len(Ones(A)))
		else:
			print(TotalOnes(A) - TotalOnes(B) + len(Ones(B)))
	else:
		print(TotalOnes(A) + TotalOnes(B))


def popcount(N):
	n = abs(N)
	p = 0
	b = 0
	while n > 1 << b:
		b += 1
	while b > 0:
		m = 1 << b
		if n & m:
			n ^= m
			p += b * (m >> 1) + n
		b -= 1
	if N < 0:
		return 32 * N + p
	else:
		return p
T = int(input())
for t in range(T):
	(A, B) = map(int, input().split())
	print(popcount(B + 1) - popcount(A))


def fun(n):
	if n < 0:
		return 0
	res = 0
	y = 1
	while n // 2 ** y != 0:
		res += n // 2 ** y * 2 ** (y - 1)
		if n % 2 ** y + 1 - 2 ** (y - 1) > 0:
			res += n % 2 ** y + 1 - 2 ** (y - 1)
		y += 1
	if n % 2 ** y + 1 - 2 ** (y - 1) > 0:
		res += n % 2 ** y + 1 - 2 ** (y - 1)
	return res
for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	if a >= 0 and b >= 0:
		res = fun(b) - fun(a - 1)
	if a < 0 <= b:
		res = fun(b) + 32 * -a - fun(-a - 1)
	if a < 0 and b < 0:
		res = 32 * (-a + b + 1) - (fun(-a - 1) - fun(-b - 2))
	print(res)


def count(a):
	if a == 0:
		return 0
	if a % 2 == 0:
		return count(a - 1) + bin(a).count('1')
	return (a + 1) // 2 + 2 * count(a // 2)

def solve(a, b, r=32):
	if a > 0:
		return count(b) - count(a - 1)
	if a == 0:
		return count(b)
	if b > 0:
		return count(b) - r * a - count(~a)
	if b >= -1:
		return r * -a - count(~a)
	b += 1
	return r * (b - a) + count(~b) - count(~a)
T = int(input())
for _ in range(T):
	(A, B) = map(int, input().split())
	print(solve(A, B))


from math import log2

def bit_sum(a, b):
	if a < 0 and b >= 0:
		return bit_sum_u(a + 2 ** 32, 2 ** 32 - 1) + bit_sum_u(0, b)
	if a < 0:
		a += 2 ** 32
	if b < 0:
		b += 2 ** 32
	return bit_sum_u(a, b)

def bit_sum_u(a, b):
	s = 0
	step = 1
	while a + step <= b:
		if not a & step:
			step *= 2
			continue
		s += bit_sum_block(a, step)
		a += step
		step *= 2
	while a != b:
		if a + step > b:
			step //= 2
			continue
		s += bit_sum_block(a, step)
		a += step
	return s + bin(b).count('1')

def bit_sum_block(a, b):
	assert a % b == 0 and log2(b).is_integer()
	return bin(a).count('1') * b + b // 2 * int(log2(b))
for i in range(int(input())):
	print(bit_sum(*map(int, input().split())))


import sys
count = 0
ones = []
ones.insert(0, 0)
ones.insert(1, 1)
for i in range(2, 32):
	ones.insert(i, 2 * ones[i - 1] + 2 ** (i - 2))
tot_1s = []
tot_1s.insert(0, 0)
for i in range(1, 32):
	tot_1s.insert(i, tot_1s[i - 1] + ones[i])
num_cases = int(input().strip())
for i in range(num_cases):
	total_count = 0
	(lower_num, upper_num) = input().strip().split(' ')
	(lower_num, upper_num) = [int(lower_num), int(upper_num)]
	num1 = abs(lower_num) - (1 if lower_num < 0 else 0)
	num2 = abs(upper_num) - (1 if upper_num < 0 else 0)
	lower_b = bin(num1)[::-1][0:len(bin(num1)) - 2]
	upper_b = bin(num2)[::-1][0:len(bin(num2)) - 2]
	count_l = 0
	count_u = 0
	XXX_lower = 0
	XXX_upper = 0
	msb1 = num1
	msb2 = num2
	for bit in range(len(lower_b) - 1, 0, -1):
		if lower_b[bit] == '1':
			msb1 = msb1 - 2 ** bit
			XXX_lower = XXX_lower + 1
		count_l = count_l + int(lower_b[bit]) * (tot_1s[bit] + msb1 + 1)
	for bit in range(len(upper_b) - 1, 0, -1):
		if upper_b[bit] == '1':
			msb2 = msb2 - 2 ** bit
			XXX_upper = XXX_upper + 1
		count_u = count_u + int(upper_b[bit]) * (tot_1s[bit] + msb2 + 1)
	count_l = count_l + int(lower_b[0])
	XXX_lower = XXX_lower + int(lower_b[0])
	count_u = count_u + int(upper_b[0])
	XXX_upper = XXX_upper + int(upper_b[0])
	if lower_num < 0:
		count_l = 32 * abs(lower_num) - count_l
		XXX_lower = 32 - XXX_lower
	if upper_num < 0:
		count_u = 32 * abs(upper_num) - count_u
		XXX_upper = 32 - XXX_upper
	if lower_num >= 0 and upper_num >= 0:
		total_count = count_u - count_l + XXX_lower
	elif lower_num <= 0 and upper_num <= 0:
		total_count = count_l - count_u + XXX_upper
	elif lower_num <= 0 and upper_num >= 0:
		total_count = count_u + count_l
	print(total_count)


def bin_s(n):
	lower = 0
	upper = base
	while lower < upper:
		x = lower + (upper - lower) // 2
		val = 2 ** x
		if n == val:
			return val
		elif n > val:
			if lower == x:
				return val
			lower = x
		elif n < val:
			upper = x
	return 2 ** lower

def cum1(n):
	if n <= 1:
		return n
	else:
		n2 = n // 2
		return 2 * cum1(n2) + n2 - 1

def div3(n):
	if n <= 1:
		return n
	else:
		np = bin_s(n)
		nr = n - np
		cp = cum1(np)
		cr = div3(nr) + nr
		return cp + cr

def findComplis(n, base):
	ones = div3(n)
	zeros = base * n - ones
	return (zeros, ones)
(N, base) = (int(input()), 32)
lrgst_int = 2 ** (base - 1)
for cur in range(N):
	(A, B) = [int(t) for t in input().split()]
	if A > B:
		cop = A
		A = B
		B = cop
	if B >= A > 0:
		A -= 1
	if A <= B < 0:
		B += 1
	if A <= -1:
		a = -1 - A
		(onesA, zerosA) = findComplis(a, base)
		onesA += base
	else:
		(zerosA, onesA) = findComplis(A, base)
	if B <= -1:
		b = -1 - B
		(onesB, zerosB) = findComplis(b, base)
		onesB += base
		ans = onesA - onesB
	else:
		(zerosA, onesB) = findComplis(B, base)
		if A < 0:
			ans = onesB + onesA
		else:
			ans = onesB - onesA
	print(ans)


import sys
import re
results = []
inputs = []

def calc_ones(num):
	if num == 1:
		return 1
	else:
		x = 1
		new_total = 0
		while x < num * 2 - 1:
			whole_groupings = int(num / x)
			if whole_groupings % 2 == 0:
				new_total = new_total + whole_groupings / 2 * x
			else:
				new_total = new_total + int(whole_groupings / 2) * x
				new_total = new_total + num - whole_groupings * x + 1
			x = x * 2
		return new_total

def calc_neg_ones(num):
	if num == -2:
		zeros = 1
	else:
		zeros = calc_ones(abs(num) - 1)
	return 32 * abs(num) - zeros
cases = sys.stdin.readline()
for n in range(0, int(cases)):
	line = sys.stdin.readline()
	line = re.findall('\\S+', line)
	inputs.append(line[0])
	inputs.append(line[1])
for n in range(0, int(cases)):
	counter = 0
	A = int(inputs[n * 2])
	B = int(inputs[n * 2 + 1])
	if A <= 0 and B >= 0:
		counter = calc_neg_ones(A)
		counter = counter + calc_ones(B)
		results.append(counter)
	elif A < 0 and B < 0:
		counter = calc_neg_ones(A)
		counter = counter - calc_neg_ones(B + 1)
		results.append(counter)
	elif A >= 0 and B > 0:
		counter = calc_ones(B)
		if A > 0:
			counter = counter - calc_ones(A - 1)
		results.append(counter)
for result in results:
	sys.stdout.write(str(int(result)) + '\n')


def ones_between(a, b):
	if a >= 0:
		return ones_below(b) - ones_below(a)
	if b < 0:
		return ones_below(-b) - ones_below(-a) + 32 * (b - a)
	return ones_below(b) - 32 * a - ones_below(-a)

def ones_below(n):
	k = n.bit_length() - 1
	if n & n - 1 == 0:
		return n // 2 * k
	m = 1 << k
	return ones_below(m) + ones_below(n - m) + n - m
t = int(input())
for t0 in range(t):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	print(ones_between(a, b + 1))


def ones(n):
	total = 0
	for i in range(31, -1, -1):
		k = 1 << i
		if n & k:
			n ^= k
			total += bits[i] + (n + 1)
	return total

def onesNeg(n):
	return n * -32 - ones(~n)
bits = [0] * 32
for i in range(1, 32):
	bits[i] = (1 << i - 1) * i
for _ in range(int(input())):
	(a, b) = map(int, input().strip().split())
	if a > 0:
		print(ones(b) - ones(a - 1))
	elif a == 0:
		print(ones(b))
	elif b >= 0:
		print(onesNeg(a) + ones(b))
	elif b == -1:
		print(onesNeg(a))
	else:
		print(onesNeg(a) - onesNeg(b + 1))


from math import floor, log
bit_len = 32

def hamming_weight(n):
	if n == 0:
		return 0
	elif n > 0:
		logn = floor(log(n, 2))
		hw = 0
		for i in range(logn + 1):
			powi = 2 ** i
			hw += floor((n + 1) / (2 * powi)) * powi
			cycle_ratio = (n + 1) / (2 * powi) - floor((n + 1) / (2 * powi))
			if cycle_ratio > 0.5:
				cycle_ratio -= 0.5
				hw += int(cycle_ratio * (2 * powi))
		return hw
	else:
		return bit_len * -n - hamming_weight(-n - 1)
T = int(input())
for t in range(T):
	(A, B) = map(int, input().split(' '))
	if A == 0:
		print(hamming_weight(B))
	elif A > 0:
		print(hamming_weight(B) - hamming_weight(A - 1))
	elif B == 0:
		print(hamming_weight(A))
	elif B < 0:
		print(hamming_weight(A) - hamming_weight(B + 1))
	else:
		print(hamming_weight(A) + hamming_weight(B))


def z(a):
	(ob, fa) = (0, 2)
	while fa <= a * 2:
		ob += (a + 1) // fa * (fa // 2) + max(0, (a + 1) % fa - fa // 2)
		fa *= 2
	return ob
for x in range(int(input())):
	[a, b] = [int(x) for x in input().strip().split(' ')]
	if a >= 0 and b >= 0:
		print(z(b) - z(max(0, a - 1)))
	elif a < 0 and b >= 0:
		print(z(b) + (32 * -a - z(-a - 1)))
	else:
		print(32 * -a - z(-a - 1) - (32 * (-b - 1) - z(-b - 2)))


def cal_set_bits(n):
	co = 0
	j = 0
	while j < 32:
		co += n & 1
		n = n >> 1
		j += 1
	return co

def solve(a):
	if a >= 0:
		if a == 0:
			return 0
		elif a % 2 == 0:
			return solve(a - 1) + cal_set_bits(a)
		else:
			return 2 * solve(a >> 1) + int(a + 1) / 2
	else:
		a += 1
		return (int(-a) + 1) * 32 - solve(-a)
import math
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	if L <= 0:
		if R >= 0:
			count = solve(L) + solve(R)
		else:
			count = solve(L) - solve(R + 1)
	else:
		count = solve(R) - solve(L - 1)
	print(int(count))


def lgst2Pwr(inNum):
	j = 0
	k = 0
	while j < inNum:
		j = 2 ** k
		k += 1
	return k - 1

def getSum(temp_Int):
	sum_Int = 0
	i = 0
	currExp = 0
	exp = lgst2Pwr(temp_Int)
	while temp_Int > 0:
		if exp != -1:
			sum_Int += (-1) ** i * (2 ** (exp - 1) * exp + 1 + currExp * (2 ** exp - 1))
			temp_Int = abs(temp_Int - 2 ** exp)
			if i % 2 == 0:
				if temp_Int == 0:
					sum_Int += currExp
				currExp = currExp + exp
				exp = lgst2Pwr(temp_Int)
				currExp = currExp - exp
			else:
				exp = lgst2Pwr(temp_Int)
		i += 1
	return int(sum_Int)

def cntAllOnes(stInt, edInt):
	stInt_abs = abs(stInt)
	edInt_abs = abs(edInt)
	if stInt >= 0:
		return getSum(edInt) - getSum(max(stInt - 1, 0))
	elif edInt <= 0:
		return 32 * stInt_abs - getSum(max(0, stInt_abs - 1)) - (32 * max(0, edInt_abs - 1) - getSum(max(0, edInt_abs - 2)))
	else:
		return 32 * stInt_abs - getSum(stInt_abs - 1) + getSum(edInt_abs)
n = int(input().strip())
inpArr = [map(int, input().strip().split(' ')) for i in range(n)]
solArr = [cntAllOnes(st, ed) for (st, ed) in inpArr]
for y in solArr:
	print(y)


bit_width = 32

def ones_counting_to_positive(test):
	bit_number = bit_width
	mask = 1 << bit_width - 1
	bits_left_count = 0
	count = 0
	while bit_number > 0:
		bit_number -= 1
		mask_new = mask >> 1
		if mask & test == mask:
			count += 1 + bit_number * mask_new + bits_left_count * mask
			bits_left_count += 1
		mask = mask_new
	return count

def ones_counting_to_negative(test):
	return -bit_width * test - ones_counting_to_positive(-test - 1)

def solve():
	limit = int(input().strip())
	index = 0
	while index < limit:
		(a, b) = input().strip().split(' ')
		(a, b) = [int(a), int(b)]
		count = 0
		if a == 0:
			pass
		elif a < 0:
			count += ones_counting_to_negative(a)
		else:
			count -= ones_counting_to_positive(a - 1)
		if b == 0 or b == -1:
			pass
		elif b < 0:
			count -= ones_counting_to_negative(b + 1)
		else:
			count += ones_counting_to_positive(b)
		print(count)
		index += 1
solve()


def countbit(b, n):
	q = n >> b + 1
	r = n & (1 << b + 1) - 1
	return (q << b) + max(0, r - (1 << b))

def countall(n):
	return sum((countbit(b, n) for b in range(32)))

def solve(a, b):
	if 0 <= a:
		return countall(b + 1) - countall(a)
	if b < 0:
		return countall(2 ** 32 + b + 1) - countall(2 ** 32 + a)
	return countall(2 ** 32) - countall(2 ** 32 + a) + countall(b + 1)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	assert -2 ** 31 <= a <= b < 2 ** 31
	print(solve(a, b))


def clear_msb(x):
	tmp = x
	msb = 0
	while x != 0:
		x >>= 1
		msb += 1
	msb = max(0, msb - 1)
	x = tmp
	return x & (1 << msb) - 1

def num_ones_from_zero_msb_of(end):
	msb = -1
	while end != 0:
		end >>= 1
		msb += 1
	return msb * 2 ** (msb - 1)

def num_ones_from_zero(end):
	if end <= 1:
		return end
	next_end = clear_msb(end)
	return next_end + 1 + num_ones_from_zero(next_end) + num_ones_from_zero_msb_of(end)

def num_ones(start, end):
	ones = num_ones_from_zero(end)
	if start > 0:
		ones -= num_ones_from_zero(start - 1)
	return ones

def num_ones_twos_comp(start, end):
	if start < 0:
		if end >= 0:
			start = 2 ** 32 + start
			return num_ones(start, 2 ** 32 - 1) + num_ones(0, end)
	start = 2 ** 32 + start if start < 0 else start
	end = 2 ** 32 + end if end < 0 else end
	return num_ones(start, end)
n = int(input())
for _ in range(n):
	(start, end) = map(int, input().split(' '))
	print(num_ones_twos_comp(start, end))


from collections import Counter as ct

def onesct(x):
	if x == 0 or x == -1:
		return 0
	elif x % 2 == 0:
		return onesct(x - 1) + bin(x).count('1')
	else:
		return (x + 1) // 2 + 2 * onesct(x // 2)
n = int(input())
counter = 0
for _ in range(n):
	(a, b) = input().split()
	(a, b) = [int(a), int(b)]
	counter = 0
	if b >= 0:
		counter += onesct(b)
		if a < 0:
			counter += 32 * abs(a) - onesct(abs(a + 1))
		else:
			counter -= onesct(a - 1)
	else:
		counter += 32 * (abs(a) - abs(b + 1)) + onesct(abs(b + 2)) - onesct(abs(a + 1))
		if b == -1:
			counter -= 1
	print(counter)


def count_bits(n):
	ret = 0
	while n > 1:
		if n % 2 == 1:
			ret += 1
		n = int(n / 2)
	return ret + 1

def no_bits(n):
	n = int(n)
	if n == 0:
		return 0
	elif n < 0:
		n += 1
		return (1 - n) * 32 - no_bits(-n)
	elif n % 2 == 0:
		return count_bits(n) + no_bits(n - 1)
	else:
		return int((n + 1) / 2) + 2 * no_bits(int(n / 2))
n = int(input().strip())
for i in range(n):
	(a, b) = [int(_) for _ in input().strip().split()]
	p = 0
	if a == 0:
		p = no_bits(b)
	elif b == 0:
		p = no_bits(a)
	elif a == b:
		if a > 0:
			p = no_bits(b) - no_bits(a - 1)
		else:
			p = no_bits(b) - no_bits(a + 1)
	elif a >= 0 and b > 0:
		p = no_bits(b) - no_bits(a - 1)
	elif a < 0 and b <= 0:
		p = no_bits(a) - no_bits(b + 1)
	else:
		p = no_bits(a) + no_bits(b)
	print(p)


def fun(a):
	mystr = bin(a)[2:]
	ans = 0
	count = 0
	length = len(mystr)
	for i in range(0, length):
		if mystr[i] == '1':
			ans = ans + count * 2 ** (length - 1 - i) + (length - 1 - i) * 2 ** (length - 2 - i)
			count = count + 1
	return int(ans)
t = int(input())
for i in range(0, t):
	data = list(map(int, input().split()))
	if data[0] == data[1]:
		if data[0] < 0:
			print(fun(2 ** 32 + data[0] + 1) - fun(2 ** 32 + data[0]))
		else:
			print(fun(data[0] + 1) - fun(data[0]))
	elif data[0] == 0 and data[1] > 0:
		print(fun(data[1] + 1))
	elif data[0] > 0 and data[1] > 0:
		print(fun(data[1] + 1) - fun(data[0]))
	elif data[0] < 0 and data[1] == 0:
		print(fun(2 ** 32 - 1 + 1) - fun(2 ** 32 + data[0]))
	elif data[0] < 0 and data[1] < 0:
		print(fun(2 ** 32 + data[1] + 1) - fun(2 ** 32 + data[0]))
	elif data[0] < 0 and data[1] > 0:
		print(fun(data[1] + 1) + fun(2 ** 32 - 1 + 1) - fun(2 ** 32 + data[0]))


from math import log, floor

def bin2(dec):
	if dec < 0:
		return bin(dec + 2 ** 32).split('b')[1]
	else:
		return bin(dec).split('b')[1]

def num_ones(num):
	if num <= 0:
		return 0
	max_pow = floor(log(num, 2))
	return max_pow * 2 ** (max_pow - 1) + num_ones(num - 2 ** max_pow) + num - 2 ** max_pow + 1
for i in range(int(input())):
	(start, end) = [int(num) for num in input().split(' ')]
	ones = 0
	if start < 0:
		start = int(bin2(start), 2)
		if end < 0:
			end = int(bin2(end), 2)
			ones += num_ones(end) - num_ones(start - 1)
		else:
			ones += num_ones(int(bin2(-1), 2)) - num_ones(int(bin2(start - 1), 2))
			ones += num_ones(end)
	else:
		ones += num_ones(end) - num_ones(start - 1)
	print(int(ones))


def sum1(x):
	b = 0
	for i in range(len(bin(x)[2:])):
		b += (x + 1) // 2 ** (i + 1) * 2 ** i + (x + 1) % 2 ** (i + 1) // (2 ** i + 1) * ((x + 1) % 2 ** (i + 1)) % 2 ** i
	return b
T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split(' '))
	if a >= 0 and b >= 0:
		N2 = sum1(b)
		N1 = sum1(a - 1)
		rez = N2 - N1
	if a <= 0 and b >= 0:
		N2 = sum1(b)
		N1 = sum1(2 ** 32 - 1) - sum1(2 ** 32 + a - 1)
		rez = N1 + N2
	if a <= 0 and b < 0:
		N1 = sum1(2 ** 32 - 1) - sum1(2 ** 32 + a - 1)
		N2 = sum1(2 ** 32 - 1) - sum1(2 ** 32 + b)
		rez = N1 - N2
	print(rez)


import math

def Two(x):
	t = 0
	for k in range(0, 31):
		t += (x + 1 - (x + 1) % 2 ** (k + 1)) // 2
		if (x + 1) % 2 ** (k + 1) >= 2 ** k:
			t += (x + 1) % 2 ** (k + 1) - 2 ** k
	return t

def summand(a, b):
	if b >= 0:
		if a == 0:
			return Two(b)
		if a > 0:
			return Two(b) - Two(a - 1)
		return Two(b) + Two(2 ** 31 - 1) - Two(a + 2 ** 31 - 1) - a
	else:
		return Two(2 ** 31 - 1) - Two(a + 2 ** 31 - 1) - a - Two(2 ** 31 - 1) + Two(b + 1 + 2 ** 31 - 1) + b + 1
t = int(input().strip())
for k in range(t):
	a = tuple(map(int, input().strip().split(' ')))
	print(summand(a[0], a[1]))


def get_val2(ind1, ind2):
	j = 1
	ans = 0
	for i in range(1, 33):
		a = ind2 // j
		if a != 0:
			if a % 2 == 0:
				b = a // 2
				noz = b * j
				c = ind2 % j
				noz = noz + c
			else:
				b = a // 2 + 1
				noz = b * j
		else:
			noz = ind2
		ans = ans + noz
		g = j * 2
		j = g
	return ans

def get_val1(ind1, ind2):
	j = 1
	ans = 0
	for i in range(1, 33):
		a = ind2 // j
		if a != 0:
			if a % 2 == 0:
				b = a // 2
				noz = b * j
				c = ind2 % j
				noz = noz + c
			else:
				b = a // 2 + 1
				noz = b * j
		else:
			noz = ind2
		noon = ind2 - noz
		ans = ans + noon
		g = j * 2
		j = g
	return ans
n = int(input())
for i in range(0, n):
	li = list(map(int, input().strip().split(' ')))
	df = get_val1(0, li[1] + 1)
	df1 = get_val2(0, -li[0])
	print(df + df1)


def bitize_twos_complement(X, bits=32):
	L = [0 for r in range(0, bits)]
	if X >= 0:
		for i in range(0, 32):
			L[i] = X % 2
			X //= 2
	elif X < 0:
		X *= -1
		X -= 1
		for i in range(0, 32):
			L[i] = (X + 1) % 2
			X //= 2
	return L

def numberify_twos_complement(bin_list):
	number = 0
	is_negative = False
	if bin_list[len(bin_list) - 1] == 1:
		is_negative = True
		for flippy in range(0, len(bin_list)):
			bin_list[flippy] = 1 - bin_list[flippy]
	current_power = 1
	for i in range(0, len(bin_list)):
		number += current_power * bin_list[i]
		current_power *= 2
	if is_negative:
		number += 1
		number *= -1
	return number

def count_twos_complement_ones(N, bits=32):
	bit_array = bitize_twos_complement(N)
	result = 0
	for i in range(1, bits - 1):
		if bit_array[bits - i]:
			bit_array[bits - i] = 0
			result += (bits - i) * pow(2, bits - i - 1) + (numberify_twos_complement(bit_array) + 1)
	if bit_array[1] and bit_array[0]:
		result += 4
	elif not bit_array[1] and bit_array[0]:
		result += 1
	elif bit_array[1] and (not bit_array[0]):
		result += 2
	return result

def find_twos_complement_ones(A, B):
	if 0 < A <= B:
		return count_twos_complement_ones(B) - count_twos_complement_ones(A - 1)
	elif A <= B < 0:
		return count_twos_complement_ones(B) - count_twos_complement_ones(A - 1)
	elif A <= B == 0:
		return count_twos_complement_ones(-1) - count_twos_complement_ones(A - 1)
	elif A <= B <= 0:
		return count_twos_complement_ones(B) - count_twos_complement_ones(A - 1)
	elif A < 0 < B:
		return count_twos_complement_ones(-1) - count_twos_complement_ones(A - 1) + count_twos_complement_ones(B)
	elif 0 == A <= B:
		return count_twos_complement_ones(B)
	else:
		return 0
num_queries = int(input())
for i in range(0, num_queries):
	(A, B) = [int(a) for a in input().split()]
	print(find_twos_complement_ones(A, B))


from functools import lru_cache

@lru_cache(maxsize=None)
def cum_ones(k):
	if 0 <= k < 2:
		return k
	elif k < 0:
		k0 = (1 << 32) - 1
		return cum_ones(k0 + k) - cum_ones(k0)
	m = k.bit_length()
	k0 = 1 << m - 1
	dk = k - k0
	if dk:
		return cum_ones(k0) + cum_ones(dk) + dk
	else:
		k0 //= 2
		return 2 * cum_ones(k0) + k0 - 1
for _ in range(int(input())):
	(i, j) = map(int, input().split())
	if i <= 0 and j >= 0:
		print(cum_ones(j) - cum_ones(i))
	elif i < 0 and j < 0:
		print(cum_ones(j + 1) - cum_ones(i))
	else:
		print(cum_ones(j) - cum_ones(i - 1))


import sys

def pos(z):
	h = z + 1
	sum = 0
	for i in range(33):
		a = h // 2 ** i
		sum += a // 2 * 2 ** i
		if a % 2 != 0:
			sum += h - a * 2 ** i
	return sum

def neg(z):
	sum = 0
	h = abs(z)
	for i in range(33):
		a = h // 2 ** i
		sum += a // 2 * 2 ** i
		if a % 2 == 0:
			sum += h - a * 2 ** i
	return sum

def cal(x, y):
	if x < 0 and y < 0:
		return neg(x) - neg(y + 1)
	elif x < 0 and y >= 0:
		return neg(x) + pos(y)
	else:
		return pos(y) - pos(x - 1)
t = int(input().strip())
for a0 in range(t):
	(x, y) = input().strip().split(' ')
	(x, y) = [int(x), int(y)]
	result = cal(x, y)
	print(result)


import sys

def pos(z):
	h = z + 1
	sum = 0
	for i in range(33):
		a = h // 2 ** i
		sum += a // 2 * 2 ** i
		if a % 2 != 0:
			sum += h - a * 2 ** i
	return sum

def neg(z):
	sum = 0
	h = abs(z)
	for i in range(33):
		a = h // 2 ** i
		sum += a // 2 * 2 ** i
		if a % 2 == 0:
			sum += h - a * 2 ** i
	return sum

def cal(x, y):
	if x < 0 and y < 0:
		return neg(x) - neg(y + 1)
	elif x < 0 and y >= 0:
		return neg(x) + pos(y)
	else:
		return pos(y) - pos(x - 1)
t = int(input().strip())
for a0 in range(t):
	(x, y) = input().strip().split(' ')
	(x, y) = [int(x), int(y)]
	result = cal(x, y)
	print(result)


import sys
from time import time

def bits_set(n, v):
	cnt = 0
	while n:
		cnt += 1
		n = n & n - 1 & v
	return cnt

def solve_bf(a, b):
	v = (1 << 32) - 1
	sm = 0
	for i in range(a, b + 1):
		c = bits_set(i, v)
		sm += c
	return sm

def f_gen():
	(f, d) = (0, 1)
	while True:
		yield f
		(f, d) = (2 * f + d, 2 * d)

def solve(a, b):

	def calc_positive(n):
		if n < 1:
			return 0
		(ff, u) = (list(), 1)
		for f in f_gen():
			if u > n:
				break
			ff.append(f)
			u *= 2
		total = 0
		u //= 2
		while n:
			f = ff.pop()
			if n >= u:
				r = n % u
				delta = f + r + 1
				total += delta
				n %= u
			u //= 2
		return total

	def calc(n):
		if n >= 0:
			return calc_positive(n)
		n = abs(n)
		return n * 32 - calc_positive(n - 1)
	if a == 0:
		return calc(b)
	elif b == 0:
		return calc(a)
	elif a >= 0:
		(fr, to) = (a - 1, b)
		(u, v) = (calc(fr), calc(to))
		return v - u
	elif b < 0:
		(fr, to) = (a, b + 1)
		(u, v) = (calc(fr), calc(to))
		return u - v
	(fr, to) = (a, b)
	(u, v) = (calc(fr), calc(to))
	return u + v
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	print(solve(a, b))


(MM, FULL, MEG) = (1 << 31, (1 << 30) * 31, (1 << 30) * 31 + 2147483648)

def solpos(x, sp=31):
	return x if sp == 0 else x - (1 << sp) + 1 + sp * (1 << sp - 1) + solpos(x - (1 << sp), sp - 1) if x & 1 << sp else solpos(x, sp - 1)

def sol(x):
	return solpos(x) if x >= 0 else FULL - solpos(MM + x - 1) - x if x != -2147483648 else MEG
for _ in range(int(input())):
	(A, B) = map(int, input().strip(' ').split())
	if B < 0:
		print(sol(A) - sol(B + 1))
	elif A <= 0 and B >= 0:
		print(sol(A) + solpos(B))
	else:
		print(sol(B) - solpos(A - 1))


def count_positive(n):
	count = mul = 0
	for i in range(31, -1, -1):
		b = 1 << i
		if b & n:
			count += 1 + b * i // 2 + b * mul
			mul += 1
	return count

def count_negative(n):
	n = -n
	return 32 * n - count_positive(n - 1)

def count(n):
	return count_positive(n) if n >= 0 else count_negative(n)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if b < 0:
		print(count(a) - count(b + 1))
	elif a > 0:
		print(count(b) - count(a - 1))
	else:
		print(count(a) + count(b))


q = int(input())
Q = [tuple(map(int, input().split())) for x in range(q)]

def f(y):
	s = bin(y)[2:]
	l = len(s)
	n = 0
	ones = 0
	for i in range(l):
		if s[i] == '1':
			n += 2 ** (l - 1 - i) * ones + 2 ** (l - 2 - i) * (l - 1 - i)
			ones += 1
	n += ones
	return n

def g(x):
	mx = abs(x)
	return f(x) if x == mx else 32 * mx - f(mx - 1)
for z in Q:
	(x, y) = z
	if x > 0:
		print(int(g(y) - g(x - 1)))
	elif y >= 0:
		print(int(g(y) + g(x)))
	else:
		print(int(g(x) - g(y + 1)))


for _ in range(int(input())):
	(down, up) = map(int, input().split())
	temp_down = down
	temp_up = up
	rd = 0
	ru = 0
	try:
		if down < 0:
			down = abs(down)
			j = 2
			for i in range(32):
				rd += down // j * (j // 2)
				if down % j > j // 2:
					rd += j // 2
				else:
					rd += down % j
				j *= 2
		else:
			j = 2
			temp = 0
			for i in range(32):
				temp += down // j * (j // 2)
				if down % j > j // 2:
					temp += j // 2
				else:
					temp += down % j
				j *= 2
			rd += 32 * down - temp
		if up < 0:
			up = abs(up)
			j = 2
			up -= 1
			for i in range(32):
				ru += up // j * (j // 2)
				if up % j > j // 2:
					ru += j // 2
				else:
					ru += up % j
				j *= 2
		else:
			j = 2
			up += 1
			temp = 0
			for i in range(32):
				temp += up // j * (j // 2)
				if up % j > j // 2:
					temp += j // 2
				else:
					temp += up % j
				j *= 2
			ru += 32 * up - temp
		if temp_down <= 0 and temp_up >= 0:
			print(rd + ru)
		elif temp_down >= 0 and temp_up >= 0:
			print(ru - rd)
		else:
			print(rd - ru)
	except RuntimeError:
		print(0)


import os
import sys
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	count = 0
	h1 = a
	h2 = b + 1
	for num in range(32):
		power = 2 ** num
		sum_a = h1 // (power * 2) * power + max(0, h1 % (power * 2) - power)
		sum_b = h2 // (power * 2) * power + max(0, h2 % (power * 2) - power)
		count += sum_b - sum_a
	print(count)


def count(x):
	x = x + 1
	y = 0
	for i in range(1, 33):
		y += x // 2 ** i * 2 ** (i - 1) + max(0, x % 2 ** i - 2 ** (i - 1))
	return y

def twosCompliment(a, b):
	if a >= 0 and b >= 0:
		return count(b) - count(a - 1)
	elif a < 0 and b < 0:
		z = 32 * (b - a + 1)
		a = -1 - a
		b = -1 - b
		(a, b) = (b, a)
		return z - (count(b) - count(a - 1))
	elif a < 0 and b >= 0:
		return count(b) + 32 * (0 - a) - count(a * -1 - 1)
n = int(input())
for i in range(n):
	w = list(map(int, input().strip().split()))
	print(twosCompliment(w[0], w[1]))


t = int(input())

def gen(num):
	if num == '':
		return 0
	elif num == '1':
		return 1
	elif num == '0':
		return 0
	elif num[0] == '0':
		return gen(num[1:])
	else:
		return int(num[1:], 2) + 1 + gen(num[1:]) + 2 ** (len(num) - 2) * (len(num) - 1)

def func(a, b):
	if a < 0 and b >= 0:
		if a + b + 1 == 0:
			return 32 * (b + 1)
		elif a + b + 1 < 0:
			return 32 * (b + 1) + func(a, -(b + 2))
		else:
			return 32 * -a + func(-a, b)
	elif a < 0 and b < 0:
		return 32 * (b - a + 1) - func(-b - 1, -a - 1)
	else:
		if a == 0:
			return gen(bin(b)[2:])
		return gen(bin(b)[2:]) - gen(bin(a - 1)[2:])
for ts in range(t):
	(a, b) = input().strip().split()
	(a, b) = (int(a), int(b))
	print(func(a, b))