Kulyash is given an integer N. His task is to break N into some number of (integer) powers of 2. 

TO achieve this, he can perform the following operation several times (possibly, zero):
Choose an integer X which he already has, and break X into 2 integer parts (Y and Z) such that X = Y + Z.

Find the minimum number of operations required by Kulyash to accomplish his task.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input.
- The first and only line of each test case contains an integer N — the original integer with Kulyash.

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

For each test case, output on a new line the minimum number of operations required by Kulyash to break N into powers of 2.  

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{9}$

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

----- Sample Output 1 ------ 
1
0

----- explanation 1 ------ 
Test case $1$: $3$ can be broken into $2$ and $1$ (both are powers of $2$) by using $1$ operation.

Test case $2$: $4$ is already a power of $2$ so there is no need to perform any operations.

Source: codechef | Difficulty: EASY
Tags: Bit manipulation

Mathematics

Greedy algorithms


Solutions:
BitsSetTable256 = [0] * 256

def initialize():
	BitsSetTable256[0] = 0
	for i in range(256):
		BitsSetTable256[i] = (i & 1) + BitsSetTable256[i // 2]

def countSetBits(n):
	return BitsSetTable256[n & 255] + BitsSetTable256[n >> 8 & 255] + BitsSetTable256[n >> 16 & 255] + BitsSetTable256[n >> 24]
for _ in range(int(input())):
	initialize()
	print(countSetBits(int(input())) - 1)


for _ in range(int(input())):
	n = bin(int(input())).count('1')
	print(n - 1)


for _ in range(int(input())):
	n = int(input())
	set_bits = 0
	while n:
		n &= n - 1
		set_bits += 1
	print(set_bits - 1)


from math import log
for _ in range(int(input())):
	n = int(input())
	ans = []
	while n > 0:
		res = round(log(n, 2), 14)
		ans.append(int(res))
		n -= 2 ** ans[-1]
	print(len(ans) - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	binary = bin(n)
	print(binary.count('1') - 1)


for T in range(int(input())):
	n = int(input())
	k = 0
	while True:
		if n < 2 ** k:
			break
		k += 1
	k -= 1
	t = 0
	while n > 0:
		if n >= 2 ** k:
			t += 1
			n = n - 2 ** k
		k = k - 1
	print(t - 1)


import math
for _ in range(int(input())):
	num = int(input())
	c = 0
	while num > 0:
		power = math.floor(math.log2(num))
		num -= math.pow(2, power)
		if num != 0:
			c += 1
	print(c)


import math
for _ in range(int(input())):
	z = int(input())
	op = -1
	while z > 0:
		z -= 2 ** math.floor(math.log2(z))
		op += 1
	print(op)


from math import log

def po2(x):
	return log(x, 2)
for _ in range(int(input())):
	n = int(input())
	cnt = 0
	ans = []
	while n > 0:
		res = round(po2(n), 14)
		ans.append(int(res))
		n -= 2 ** ans[-1]
		if n > 0:
			cnt += 1
	print(len(ans) - 1)


t = int(input())
for i in range(0, t):
	n = int(input())
	l = bin(n).replace('0b', '')
	print(l.count('1') - 1)


for i in range(int(input())):
	n = int(input())
	l = []
	while n // 2 != 0:
		l.append(n % 2)
		n = n // 2
	if 1 not in l:
		print(0)
	else:
		print(l.count(1))


tc = int(input())
for t in range(tc):
	N = int(input())
	nBin = bin(N).replace('0b', '')
	opCountStr = nBin.count('1')
	opCount = int(opCountStr) - 1
	print(opCount)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	c = 0
	while n > 1:
		if n % 2 == 1:
			c = c + 1
		n = n // 2
	print(c)


for i in range(int(input())):
	n = int(input())
	c = 0
	while n > 1:
		if n % 2 == 1:
			c = c + 1
		n = n // 2
	print(c)


for i in range(int(input())):
	d = int(input())
	c = 0
	while d:
		c += d & 1
		d >>= 1
	print(c - 1)


for _ in range(int(input())):
	n = int(input())
	c = 0
	r = ''
	a = 1
	while a <= n:
		a *= 2
	a = a / 2
	while a >= 1:
		if a <= n:
			n = n - a
			r = r + '1'
			c += 1
		else:
			r = r + '0'
		a = a / 2
	print(c - 1)


t = int(input())
for tc in range(t):
	n = int(input())
	b = bin(n).count('1')
	print(b - 1)


nn = int(input())
for I in range(nn):
	n = int(input())
	c = -1
	while n:
		if n % 2 == 1:
			c += 1
		n //= 2
	print(c)


t = int(input())

def split(x):
	if x == 1 or x == 2:
		return 0
	y = 1
	while y < x:
		if x == 2 ** y:
			return 0
		if x // 2 ** y < 1:
			z = x % 2 ** (y - 1)
			return 1 + split(z)
		y = y + 1
for i in range(t):
	n = int(input())
	count = split(n)
	print(count)


h = int(input())
for i in range(h):
	g = int(input())
	j = str(bin(g)).count('1')
	print(j - 1)


T = int(input())
while T:
	N = int(input())
	power_of_2 = []
	for i in range(32):
		power_of_2.append(pow(2, i))
	count = 0
	stop_pos = 0
	total_count = 0

	def power(number):
		if number == 1:
			return 0
		elif number // 2 in power_of_2 and number % 2 == 0:
			return 0
		else:
			for i in range(31):
				if pow(2, i) < number:
					continue
				else:
					reminder = number % pow(2, i - 1)
					count = 1 + power(reminder)
					return count
	total_count = power(N)
	print(total_count)
	T -= 1


for _ in range(int(input())):
	N = int(input())
	count = 0
	while N > 1:
		if N % 2 == 1:
			count += 1
		N //= 2
	print(count)


for x in range(int(input())):
	n = int(input())
	count = 0
	while n > 1:
		if n % 2 == 1:
			count += 1
		n //= 2
	print(count)


import math
for _ in range(int(input())):
	n = int(input())
	count = 0
	while n > 1:
		if n % 2 == 1:
			count += 1
		n //= 2
	print(count)


n = int(input())
for i in range(n):
	m = int(input())
	k = bin(m)
	h = k.count('1')
	print(h - 1)


import math
t = int(input())
for v in range(0, t, 1):
	counter = 0
	t = 0
	operations = {}
	n = int(input())
	if 2 ** int(math.log(n, 2)) == n:
		counter = 0
	else:
		while True:
			if n - t > 0:
				operations[int(math.log(n - t, 2))] = 2 ** int(math.log(n - t, 2))
				counter += 1
			else:
				counter -= 1
				break
			t = 0
			for v in operations:
				t += operations[v]
	print(counter)


T = int(input())
for _ in range(T):
	n = int(input())
	b = bin(n)[3:]
	print(b.count('1'))


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


import math
t = int(input())
for _ in range(t):
	a = int(input())
	count = 0
	while a != 0:
		sumu = 1
		while sumu <= a:
			sumu *= 2
		sumu = sumu // 2
		a -= sumu
		count += 1
	print(count - 1)


def sgcd(a, b):
	if a == b:
		return a
	if a == 0:
		return b
	if b == 0:
		return a
	if a % 2 == 0:
		if b % 2 == 0:
			return 2 * sgcd(a / 2, b / 2)
		else:
			return sgcd(a / 2, b)
	if b % 2 == 0:
		return sgcd(a, b / 2)
	else:
		return sgcd(abs(a - b) / 2, min(a, b))

def egcd(a, b):
	if b == 0:
		return a
	else:
		A = egcd(b, a % b)
	return A

def lcm(a, b):
	try:
		return int(a * b / sgcd(a, b))
	except:
		return a * b / egcd(a, b)

def I(a):
	return map(int, a.split(' '))

def ispowerof(x, y):
	import math
	a = math.log10(y) / math.log10(x)
	return math.ceil(a) == math.floor(a)

def b(a, c=0):
	if a == 1:
		return c
	if ispowerof(2, a):
		return c
	while a > 0:
		if a % 2:
			c += 1
		a = a // 2
	return c - 1

def main():
	for i in range(int(input())):
		a = int(input())
		print(b(a))
main()


import math
for _ in range(int(input())):
	n = int(input())
	ans = -1
	while n > 0:
		a = int(math.log(n, 2))
		n -= 2 ** a
		ans += 1
	print(ans)


i = 0
b = ''
testcases = int(input())
while i < testcases:
	count = 0
	n = int(input())
	while n > 1:
		if n % 2 == 1:
			count = count + 1
		n = (n - n % 2) / 2
	print(count)
	i = i + 1


T = int(input())
for _ in range(T):
	n = int(input())
	sq = 0
	while n > 1:
		if n % 2 == 1:
			sq += 1
		n //= 2
	print(sq)


for i in range(int(input())):
	Num = int(input())
	Count = 0
	while Num != 0:
		Sum = 1
		while Sum <= Num:
			Sum = Sum * 2
		Sum = Sum / 2
		Num = Num - Sum
		Count += 1
	print(Count - 1)


T = int(input())
for _ in range(T):
	N = int(input())
	res = -1
	while N != 0:
		if N & 1 == 1:
			res += 1
		N >>= 1
	print(res)


from math import log2

def ops(n):
	d = log2(n)
	dtrunc = int(d)
	i = 0
	while d != dtrunc:
		n = n - 2 ** dtrunc
		d = log2(n)
		dtrunc = int(d)
		i += 1
	return i
t = int(input())
for _ in range(0, t):
	print(ops(int(input())))


for i in range(int(input())):
	c = 0
	n = int(input())
	for j in range(len(bin(n))):
		if list(bin(n))[j] == '1':
			c += 1
	print(c - 1)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = bin(n)
	count1 = a.count('1')
	print(count1 - 1)


t = int(input())
for i in range(t):
	n = int(input())
	n = bin(n)
	c = n.count('1')
	print(c - 1)


cases = int(input())
for l in range(cases):
	i = int(input())
	print(bin(i).count('1') - 1)


t = int(input())
for i in range(t):
	n = int(input())
	b = bin(n)
	s = b.count('1')
	if s == 1:
		print('0')
	else:
		print(s - 1)


n = int(input())
l = []
for i in range(0, n):
	k = int(input())
	a = str(bin(k))[2:]
	sum = -1
	for j in a:
		if j == '1':
			sum += 1
	l.append(sum)
for i in l:
	print(i)


n = int(input())
for i in range(n):
	a = int(input())
	z = str(bin(a))
	v = z.count('1')
	print(v - 1)


t = int(input())
for i in range(t):
	x = int(input())
	y = str(format(x, 'b'))
	k = 0
	for i in y:
		if i == '1':
			k = k + 1
	print(k - 1)


n = int(input())
for i in range(n):
	r = bin(int(input()))
	print(r.count('1') - 1)


t = int(input())
for i in range(0, t):
	n = int(input())
	binn = bin(n)
	count1 = int(str(binn.count('1')))
	print(count1 - 1)


T = int(input())
l = [int(input()) for i in range(T)]
for i in range(T):
	k = bin(l[i])
	k = k[2:]
	j = k.count('1')
	print(j - 1)


T = int(input())
ans = []
for i in range(T):
	N = int(input())
	ones = 0
	while N > 0:
		a = N % 2
		if N % 2 == 1:
			ones += 1
		N = N // 2
	ans.append(ones - 1)
for k in ans:
	print(k)


t = int(input())
while t:
	n = int(input())
	cnt = str(bin(n)).count('1')
	print(cnt - 1)
	t -= 1


t = int(input())
for _ in range(t):
	print(bin(int(input())).count('1') - 1)


parts = [2 ** n for n in range(30)]
parts = parts[::-1]
for _ in range(int(input())):
	N = int(input())
	breaks = 0
	for p in parts:
		if N > p:
			breaks += 1
			N -= p
		elif N == p:
			break
	print(breaks)


def main():
	for t in range(int(input())):
		N = int(input())
		print(splitn(N))

def splitn(N):
	return bin(N).count('1') - 1
main()


for i in range(int(input())):
	n = int(input())
	c = 0
	a = 0
	flag = 't'
	while flag == 't' and n > 0:
		if n == 2 ** a:
			flag = 'f'
		elif n < 2 ** a:
			n = n - 2 ** (a - 1)
			c += 1
			a = 0
		else:
			a += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	count = 0
	j = 0
	while n > 1:
		if 2 ** j < n:
			j = j + 1
		elif 2 ** j == n:
			break
		else:
			n = n - 2 ** (j - 1)
			count = count + 1
			j = 0
	print(count)


import numpy as np
T = int(input())
for k in range(T):
	N = int(input())
	n = -1
	while N > 0:
		n = n + 1
		N = int(N - 2 ** np.floor(np.log2(N)))
	print(n)


T = int(input())
for t in range(T):
	N = int(input())
	N = bin(N)
	print(N.count('1') - 1)


t = int(input())
for tt in range(t):
	n = int(input())
	onecount = str(bin(n)).count('1')
	print(int(onecount) - 1)


for _ in range(int(input())):
	print(str(bin(int(input()))).count('1') - 1)


T = int(input())
for i in range(T):
	N = int(input())
	c = str(bin(N)).count('1')
	print(c - 1)