Chef was recently studying the [Bitwise OR] operation, and stumbled upon the following problem:

Let F(i) = 1 \ | \ 2 \ | \ 3 \ | \ \ldots \ | \ i, where | denotes bitwise OR.

You are given an integer N. Find the number of distinct i such that 2 ≤ i ≤ N and F(i) = F(i-1).

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

- The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains an integer N.

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

For each test case, output the number of distinct i such that 2 ≤ i ≤ N and F(i) = F(i-1).

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
3
2
3
4
----- Sample Output 1 ------ 
0
1
1
----- explanation 1 ------ 
We have:

$F(1) = 1$

$F(2) = 3$

$F(3) = 3$

$F(4) = 7$

Test case $1$: $F(2) \neq F(1)$. Hence the answer is $0$. 

Test case $2$: For $i = 3$, $F(i) = F(i-1)$. Hence the answer is $1$.

Test case $3$: For $i = 3$, $F(i) = F(i-1)$. For $i = 2, 4$, $F(i) \neq F(i-1)$. Hence the answer is $1$.

Source: codechef | Difficulty: EASY
Tags: Bit manipulation

Mathematics


Solutions:
import math
T = int(input())
for _ in range(T):
	n = int(input())
	ans = int(math.log(n, 2))
	print(n - ans - 1)


t = int(input())
for i in range(t):
	k = 0
	number = int(input())
	j = number
	while number != 0 and number != 1:
		number = int(number / 2)
		k += 1
	l = k + 1
	print(j - l)


for _ in range(int(input())):
	num = int(input())
	if num <= 2:
		print(0)
	else:
		j = 0
		val = 1
		while num > val:
			j += 1
			val = 2 ** j
		result = None
		if num & num - 1 == 0:
			result = num - j - 1
		else:
			result = num - j
		print(result)


from math import log2
for _ in range(int(input())):
	n = int(input())
	q = int(log2(n))
	a = 2 ** q
	print(a - q - 1 + n - a)


import math
t = int(input())
while t > 0:
	p = int(input())
	print(p - math.floor(math.log(p, 2)) - 1)
	t -= 1


from math import log
from math import floor
for _ in range(int(input())):
	n = int(input())
	print(n - floor(log(n, 2)) - 1)


from math import log2
from math import floor
for _ in range(int(input())):
	n = int(input())
	print(n - floor(log2(n)) - 1)


import math
T = int(input())
for _ in range(0, T):
	n = int(input())
	x = math.floor(math.log(n, 2))
	print(n - 1 - x)


import math
for t in range(int(input())):
	n = int(input())
	c = int(math.log(n, 2))
	print(n - c - 1)


t = input()
for c in range(0, int(t)):
	n = int(input())
	if n == 2:
		print('0')
		continue
	if n == 3:
		print('1')
		continue
	k = 2
	while 2 ** k <= n:
		k += 1
	print(n - k)


import math
t = int(input())
for _ in range(0, t):
	n = int(input())
	if n == 2:
		print('0')
		continue
	if n == 3:
		print('1')
		continue
	k = 2
	while 2 ** k <= n:
		k += 1
	print(n - k)


num = int(input())
for _ in range(num):
	n = int(input())
	pow = 0
	while 2 ** (pow + 1) <= n:
		pow += 1
	print(n - pow - 1)


import math
tests = int(input())
for i in range(tests):
	num = int(input())
	two_powers = math.floor(math.log(num, 2))
	print(num - two_powers - 1)


from math import log
try:
	for _ in range(int(input())):
		n = int(input())
		x = log(n) / log(2)
		print(n - int(x) - 1)
except Exception as e:
	raise e


from math import floor, log2
for _ in range(int(input())):
	n = int(input())
	i = floor(log2(n))
	ans = n - 2 ** i
	ans += 2 * (2 ** (i - 1) - 1) - i + 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	for i in range(1, n):
		if pow(2, i) == n:
			print(n - i - 1)
			break
		elif pow(2, i) > n:
			print(n - i)
			break


from bisect import bisect_right

def solve(n):
	return n - bisect_right([2 ** i for i in range(30)], n)
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


T = int(input())
for _ in range(T):
	N = int(input())
	for i in range(1, N + 1):
		if N < pow(2, i):
			print(N - i)
			break
		if N == pow(2, i):
			print(N - i - 1)
			break


T = int(input())
for Akash in range(T):
	N = int(input())
	for UP in range(1, N + 1):
		if N < pow(2, UP):
			print(N - UP)
			break
		if N == pow(2, UP):
			print(N - UP - 1)
			break


import math
for _ in range(int(input())):
	n = int(input())
	c = 1
	while math.pow(2, c) <= n:
		c += 1
	print(n - c)


def compute_num(B):
	B = B[1:]
	n = int(B, 2)
	return n
T = int(input())
for t in range(1, T + 1):
	N = int(input())
	B = format(N, 'b')
	sumb = 0
	while len(B) > 1:
		n = compute_num(B)
		sumb += n
		A = '1' * len(B)
		B = A[1:]
	print(sumb)


T = int(input())
for vinay in range(T):
	N = int(input())
	for kukka in range(1, N):
		if N < 2 ** kukka:
			print(N - kukka)
			break
		if N == 2 ** kukka:
			print(N - kukka - 1)
			break


import math
t = int(input())
for _ in range(t):
	n = int(input())
	k = math.floor(math.log(n, 2))
	p = 2 ** k
	ans = n - p
	ans += p - 1 - k
	print(ans)


def pow2(bits):
	return 1 << bits

def max_num(bits):
	return pow2(bits + 1) - 1

def solution():
	n = int(input())
	bit_count = 0
	while n >> bit_count:
		bit_count += 1
	ans = 0
	for i in range(1, bit_count):
		ans += min(n, max_num(i)) - pow2(i)
	print(ans)
t = int(input())
while t > 0:
	t -= 1
	solution()


def btod(n):
	if n > 1:
		btod(n // 2)
		l.append(n % 2)
	elif n == 1:
		l.append(1)
		return l
	return l
t = int(input())
for i in range(t):
	l = []
	n = int(input())
	(res, sum) = (0, 0)
	ls = btod(n)
	k = len(ls)
	num = 2 ** (k - 1)
	itr = num
	while itr != 2:
		res += itr // 2 - 1
		itr = itr // 2
	sum = n - num + res
	print(sum)


t = int(input())
for i in range(t):
	n = int(input())
	for j in range(1, n):
		if n < 2 ** j:
			print(n - j)
			break
		if n == 2 ** j:
			print(n - j - 1)
			break


import math
t = int(input())
for tc in range(t):
	n = int(input())
	x = int(math.log2(n))
	y = 2 ** x - 1 - x
	y = y + (n - 2 ** x)
	print(y)


for _ in range(int(input())):
	n = int(input())
	x = 1
	s = 0
	while x <= n:
		x *= 2
		s = s + 1
	print(n - s)


import math
import bisect
for i in range(int(input())):
	n = int(input())
	s = 0
	c = 0
	while c <= n:
		s += 1
		c = 2 ** s
	s -= 1
	c = n - 2 ** s
	while s > 1:
		c += 2 ** s - 1 - 2 ** (s - 1)
		s -= 1
	print(c)


for _ in range(int(input())):
	sum = 0
	n = int(input())
	for i in range(n):
		if n // 2 ** i == 1:
			top = i
			break
		else:
			sum += 2 ** i - 1
	sum += n - 2 ** top
	print(sum)


import math

def Log2(x):
	return int(math.log10(x) / math.log10(2))
ans = 0
for _ in range(int(input())):
	N = int(input())
	val = Log2(N)
	print(N - val - 1)


n = int(input())
while n:
	n = n - 1
	a = int(input())
	count = 0
	for i in range(100):
		if a <= 0:
			count += a
			print(count)
			break
		x = 2 ** i
		a -= x
		count += x - 1


for _ in range(int(input())):
	n = int(input())
	cnt = 0
	tmp = n
	while tmp >= 4:
		tmp = tmp // 2
		cnt += 1
	print(n - cnt - 2)


t = int(input())
for i in range(t):
	res = 0
	n = int(input())
	if n < 3:
		print(0)
	else:
		curr = 2
		i = 1
		cnt = 0
		while pow(2, i) <= n:
			cnt += 1
			i += 1
		print(n - 1 - cnt)


for _ in range(int(input())):
	n = int(input())
	count = 0
	temp = n
	while temp > 0:
		temp //= 2
		count += 1
	print(n - count)


numTest = int(input())
for _ in range(numTest):
	n = int(input()) - 1
	i = 2
	ans = 0
	while True:
		if n == 0:
			break
		a = min(i, n)
		ans += a - 1
		n -= a
		i *= 2
	print(ans)


import math
for i in range(int(input())):
	t = int(input())
	x = math.floor(math.log(t, 2))
	print(t - x - 1)


import math
for i in range(int(input())):
	n = int(input())
	a = math.floor(math.log(n, 2))
	print(n - a - 1)


for _ in range(int(input())):
	N = int(input())
	print(N - len(bin(N)) + 2)


def pow2(i):
	return 1 << i

def max_bits(i):
	return pow2(i + 1) - 1

def solution():
	n = int(input())
	bits = 0
	while n >> bits:
		bits += 1
	ans = 0
	for i in range(1, bits):
		ans += min(n, max_bits(i)) - pow2(i)
	print(ans)
for _ in range(int(input())):
	solution()


l = []
for i in range(int(input())):
	n = int(input())
	if n == 2:
		print(0)
	elif n == 3:
		print(1)
	else:
		s = bin(n)[2:]
		l = len(s)
		print(n - l)


t = int(input())
for i in range(t):
	n = int(input())
	print(n - len(bin(n)) + 2)


def power(bit):
	return 1 << bit

def maxnum(bit):
	return power(bit + 1) - 1
t = int(input())
for _ in range(t):
	n = int(input())
	bits = 0
	while n >> bits:
		bits += 1
	res = 0
	for i in range(1, bits):
		res += min(n, maxnum(i)) - power(i)
	print(res)


import math as m
t = int(input())
for _ in range(t):
	n = int(input())
	(s, i) = (0, 0)
	while pow(2, i) <= n:
		s += 1
		i += 1
	print(n - s)


import math
t = int(input())
for tc in range(t):
	n = int(input())
	x = math.floor(math.log(n, 2))
	count = 0
	for i in range(1, x):
		count += pow(2, i) - 1
	count += n - pow(2, x)
	print(count)


t = int(input())
while t:
	t -= 1
	n = int(input())
	if n <= 2:
		print(0)
	else:
		x = 0
		d = 0
		for i in range(32):
			c = 1 << i
			if c & n:
				d = i
				x = c
		cout = 0
		con = 1
		for i in range(d):
			cout += con - 1
			con *= 2
		cout += n - x
		print(cout)


try:
	for t in range(int(input())):
		n = int(input())
		s = 1
		c = 0
		for i in range(1, n + 1):
			if s > n:
				break
			else:
				c += 1
				s += s + 1
		x = bin(n)[2:]
		if len(x) == x.count('1'):
			print(n - (2 + c - 1) + 1)
		else:
			print(n - (2 + c - 1))
except:
	pass


from math import log2
t = int(input())
for i in range(t):
	n = int(input())
	ans = n - int(log2(n)) - 1
	print(int(ans))


import math
try:
	testcases = int(input())
	while testcases:
		N = int(input())
		i = 1
		while pow(2, i) <= N:
			i += 1
		print(N - (i - 1) - 1)
		testcases -= 1
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	(tp, cc, count) = (1, 1, 0)
	while cc <= n:
		cc *= 2
	cc //= 2
	count = n - cc
	while tp < cc:
		count += tp - 1
		tp *= 2
	print(count)


from math import log2
case = int(input())
while case > 0:
	num = int(input())
	ans = num - 1 - int(log2(num))
	print(int(ans))
	case -= 1


for _ in range(int(input())):
	n = int(input())
	b = 0
	x = 1
	while True:
		y = 2 * x
		if y > n:
			b += n - x
			break
		b += y - x - 1
		x = y
	print(b)


for _ in range(int(input())):
	k = int(input())
	p = k
	c = 0
	while p >= 4:
		p = p / 2
		c = c + 1
	print(k - c - 2)


for _ in range(int(input())):
	n = int(input())
	print(n - len(bin(n)[2:]))


t = int(input())
for i in range(t):
	kur = 0
	x = int(input())
	j = 0
	while pow(2, j) <= x:
		kur += 1
		j += 1
	print(x - j)


t = int(input())
for _ in range(t):
	n = int(input())
	s = '{0:0b}'.format(n)
	print(n - len(s))


t = int(input())
for i in range(t):
	n = int(input())
	a = n
	c = 0
	while a:
		c += 1
		a //= 2
	print(n - c)