You are given a number N. Find the total number of setbits in the numbers from 1 to N. 
Example 1:
Input: N = 3
Output: 4
Explaination: 
1 -> 01, 2 -> 10 and 3 -> 11. 
So total 4 setbits.
 
Example 2:
Input: N = 4
Output: 5
Explaination: 1 -> 01, 2 -> 10, 3 -> 11 
and 4 -> 100. So total 5 setbits.
 
Your Task:
You do not need to read input or print anything. Your task is to complete the function countBits() which takes N as input parameter and returns the total number of setbits upto N.
 
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

    def countBits(self, N):

        # code here

Solutions:
class Solution:

	def countBits(self, N):

		def rec(N):
			if N == 0 or N == 1:
				return N
			m = 1
			c = 0
			while m <= N:
				c = c + 1
				m = m << 1
			c = c - 1
			a = (1 << c - 1) * c
			b = N - (1 << c) + 1
			return a + b + rec(N - 2 ** c)
		c = rec(N)
		return c


class Solution:

	def countBits(self, N):
		ans = 0
		for i in range(20, 0, -1):
			if N & 1 << i:
				ans += N % (1 << i) + 1 + (1 << i - 1) * i
				N &= (1 << i) - 1
		if N % 2:
			ans += 1
		return ans


class Solution:

	def countBits(self, N):

		def findpow(n):
			x = 0
			while 1 << x <= n:
				x = x + 1
			return x - 1

		def ans(n):
			if n <= 1:
				return n
			x = findpow(n)
			return x * pow(2, x - 1) + (n - pow(2, x) + 1) + ans(n - pow(2, x))
		return ans(N)


from math import log2

class Solution:

	def countBits(self, N):
		cnt = 0
		N += 1
		for i in range(0 + 1, int(log2(N)) + 1 + 1):
			(x, y) = (N // 2 ** i, N % 2 ** i)
			cnt += x * 2 ** (i - 1)
			if y > 2 ** (i - 1):
				cnt += y - 2 ** (i - 1)
		return cnt


import math

class Solution:

	def countBits(self, n):
		n = n + 1
		answer = 0
		for i in range(32):
			if 1 << i > n:
				break
			grp0s1s = n >> i
			grp1s = grp0s1s >> 1
			total = grp1s * (1 << i)
			if grp0s1s % 2 == 1:
				collide = n % (1 << i)
				answer = answer + (total + collide)
			else:
				answer = answer + total
		return answer


class Solution:

	def countBits(self, N):
		set_bits = 0
		while N > 0:
			(mx_pwr_2_lt_n, mx_pwr_2_lt_n_val) = (0, 1)
			while mx_pwr_2_lt_n_val << 1 <= N:
				mx_pwr_2_lt_n_val <<= 1
				mx_pwr_2_lt_n += 1
			set_bits += (mx_pwr_2_lt_n_val >> 1) * mx_pwr_2_lt_n + (N - mx_pwr_2_lt_n_val + 1)
			N -= mx_pwr_2_lt_n_val
		return set_bits


import math

class Solution:

	def countBits(self, N):
		if N <= 1:
			return N
		x = math.floor(math.log(N, 2))
		rest = N - 2 ** x + 1
		return 2 ** (x - 1) * x + rest + self.countBits(rest - 1)


class Solution:

	def countBits(self, N):
		last = N
		N = N + 1
		count = 0
		(a, b, c) = (2, 1, 0)
		while last:
			last = last >> 1
			count += N // a * b
			rem = N % a
			if rem > b:
				count += rem - b
			a = a << 1
			b = b << 1
		return count


import math

class Solution:

	def countBits(self, n):
		k = 0
		b = n
		while True:
			i = int(math.log2(b))
			c = 2 ** (i - 1) * i
			k += c + (n - 2 ** i) + 1
			if 2 ** i == b:
				return int(k)
			n = b - 2 ** i
			b = n


import math

class Solution:

	def countBits(self, n):
		if n < 2:
			return n
		count = 0
		max_power_before = int(math.log(n, 2))
		count += max_power_before * 2 ** max_power_before / 2
		remaining = n - 2 ** max_power_before + 1
		count += remaining
		return int(count + self.countBits(remaining - 1))


def countTotalBits(n):
	count = 0
	while n >= 1:
		n = n / 2
		count += 1
	return count

class Solution:

	def countBits(self, N):
		if N == 1:
			return 1
		if N == 0:
			return 0
		x = countTotalBits(N) - 1
		val = 2 ** (x - 1) * x + (N + 1 - 2 ** x) + Solution.countBits(self, N - 2 ** x)
		return val


class Solution:

	def countBits(self, N):
		return self.count1(N)

	def count1(self, A):
		if A == 0 or A == 1:
			return A
		x = self.po(A)
		ans = x * (1 << x - 1) + (A - (1 << x) + 1) + self.count1(A - (1 << x))
		return ans

	def po(self, n):
		c = 1
		while 1 << c <= n:
			c += 1
		return c - 1


class Solution:

	def countBits(self, N):

		def getpowerof2(n):
			x = 0
			while 2 ** x <= n:
				x += 1
			return x - 1
		if N == 0:
			return 0
		x = getpowerof2(N)
		bitstill2x = 2 ** (x - 1) * x
		msbrest = N - 2 ** x + 1
		rest = N - 2 ** x
		ans = bitstill2x + msbrest + self.countBits(rest)
		return int(ans)


import math

class Solution:

	def countBits(self, n):
		if n == 0:
			return 0
		pow = math.log10(n) / math.log10(2)
		pow = math.floor(pow)
		return int(2 ** (pow - 1) * pow + (n - 2 ** pow + 1) + self.countBits(n - 2 ** pow))


class Solution:

	def countBits(self, N):
		if N <= 1:
			return N
		p = self.highestPower(N)
		leftBits = p * (1 << p - 1)
		midBits = N - (1 << p) + 1
		rightBits = self.countBits(N - (1 << p))
		return leftBits + midBits + rightBits

	def highestPower(self, n):
		count = 0
		while 1 << count <= n:
			count += 1
		return count - 1


class Solution:

	def powerof2(self, n):
		x = 1
		c = 0
		while x <= n:
			p = x
			x = x << 1
			c += 1
		return [p, c - 1]

	def countBits(self, n):
		if n == 0:
			return 0
		l = self.powerof2(n)
		ans = (l[0] >> 1) * l[1] + (n - l[0] + 1) + self.countBits(n - l[0])
		return ans


from math import *

class Solution:

	def countBits(self, n):

		def comb(n, r):
			return factorial(n) // (factorial(n - r) * factorial(r))

		def f(i):
			l = len(i)
			if i == '1' + '0' * (l - 1):
				k = 1
				for ii in range(1, l):
					k += ii * comb(l - 1, ii)
				return k
			else:
				ll = l - 1
				k = 0
				kk = 0
				for ii in i:
					if ii == '1':
						k += f('1' + '0' * ll)
						k += int('1' + '0' * ll, 2) * kk
						kk += 1
					ll -= 1
				return k
		k = bin(n)[2:]
		return f(k)


class Solution:

	def countBits(self, N):

		def getpower(n):
			i = 1
			while 2 ** i <= n:
				i += 1
			return i - 1

		def helper(n):
			if n <= 1:
				return n
			p = getpower(n)
			return p * 2 ** (p - 1) + (n - 2 ** p + 1) + helper(n - 2 ** p)
		return helper(N)


import math

class Solution:

	def countBits(self, N):
		count = 0
		while N > 0:
			x = int(math.log(N, 2))
			y = 1 << x
			count += y // 2 * x + 1
			N = N - y
			count += N
		return count


class Solution:

	def countBits(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		(m, k) = (1, 0)
		while n >= m:
			m = m << 1
			k = k + 1
		m = m >> 1
		k = k - 1
		return k * (m >> 1) + (n - m + 1) + self.countBits(n - m)


import math

class Solution:

	def countBits(self, n):
		if n < 2:
			return n
		bits = int(math.log(n, 2))
		sol = bits * int(math.pow(2, bits - 1)) + 1
		temp = n - int(math.pow(2, bits))
		sol += temp
		return sol + self.countBits(temp)


class Solution:

	def max2(self, n):
		c = 0
		while 1 << c <= n:
			c += 1
		return c - 1

	def countBits(self, N):
		if N <= 1:
			return N
		x = self.max2(N)
		ans = x * (1 << x - 1) + (N - (1 << x)) + 1 + self.countBits(N - (1 << x))
		return ans


import math

class Solution:

	def countBits(self, N):
		two = 2
		ans = 0
		n = N
		while n != 0:
			ans += math.floor(N / two) * (two >> 1)
			if N & two - 1 > (two >> 1) - 1:
				ans += (N & two - 1) - (two >> 1) + 1
			two <<= 1
			n >>= 1
		return ans


from functools import lru_cache

class Solution:

	def countBits(self, N):
		n = bin(N)[2:]

		@lru_cache(None)
		def dp(idx, isPrefix, total):
			if idx == len(n):
				return total
			limit = 1
			if isPrefix:
				limit = int(n[idx])
			ret = 0
			for i in range(limit + 1):
				_isPrefix = isPrefix and i == limit
				_total = total + i
				ret += dp(idx + 1, _isPrefix, _total)
			return ret
		return dp(0, 1, 0)


import math

class Solution:

	def countBits(self, N):
		bits = [0 for i in range(32)]
		bits[0] = 1
		for i in range(1, 32):
			bits[i] = 2 * bits[i - 1] + 2 ** i

		def bits_count(A):
			if A == 1:
				return 1
			if A == 0:
				return 0
			msb = int(math.log2(A))
			return bits[msb - 1] + bits_count(~(1 << msb) & A) + (~(1 << msb) & A) + 1
		return bits_count(N)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.countBits(N))


class Solution:

	def countBits(self, N):

		def findTwoPower(N):
			x = 0
			while 1 << x <= N:
				x += 1
			return x - 1
		if N <= 1:
			return N
		x = findTwoPower(N)
		return x * int(2 ** (x - 1)) + (N - (1 << x) + 1) + self.countBits(N - (1 << x))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.countBits(N))


class Solution:

	def countBits(self, N):
		count = 0
		N = N + 1
		powerOf2 = 1
		while powerOf2 <= N:
			pairs = N // powerOf2
			count += pairs // 2 * powerOf2
			if pairs & 1:
				count += N % powerOf2
			powerOf2 <<= 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.countBits(N))


class Solution:

	def countBits(self, n):
		n += 1
		ans = n // 2
		pow = 2
		while pow <= n:
			tp = n // pow
			ans += tp // 2 * pow
			ans += n % pow if tp & 1 else 0
			pow <<= 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.countBits(N))


class Solution:

	def countBits(self, N):

		def largest(n):
			i = 0
			while 1 << i <= n:
				i += 1
			return i - 1

		def solve(n):
			if n == 0:
				return 0
			if n == 1:
				return 1
			x = largest(n)
			return x * (1 << x - 1) + (n - (1 << x) + 1) + solve(n - (1 << x))
		return solve(N)


class Solution:

	def countBits(self, N):
		if N == 0:
			return 0
		p = 0
		ans = 0
		while pow(2, p) <= N:
			p += 1
		p -= 1
		ans += p * pow(2, p) // 2 + N - pow(2, p) + 1 + self.countBits(N - pow(2, p))
		return ans


class Solution:

	def countBits(self, n):
		if n == 0:
			return 0

		def find_x(n):
			x = 0
			while 2 ** x <= n:
				x += 1
			return x - 1
		x = find_x(n)
		remaining = self.countBits(n - 2 ** x)
		ans = 2 ** (x - 1) * x + (n - 2 ** x + 1) + remaining
		return int(ans)


class Solution:

	def countBits(self, n):
		c = 2
		ans = 0
		n += 1
		while True:
			ans += n // c * (c // 2)
			ans += max(0, n % c - c // 2)
			if n // c == 0:
				break
			c *= 2
		return ans


class Solution:

	def countBits(self, N):
		ans = 0
		tot_sets = 0
		N1 = N
		while N1:
			tot_sets += 1
			N1 &= N1 - 1
		ans += tot_sets
		for i in range(32):
			if i == 0 and N & 1 << i:
				tot_sets -= 1
				ans += tot_sets
			elif N & 1 << i:
				tot_sets -= 1
				ans += 2 ** (i - 1) * i + 2 ** i * tot_sets
		return int(ans)


class Solution:

	def countBits(self, N):
		n = N
		ans = 0
		pre = 1
		add = 1
		while n > 0:
			if n & 1 == 1:
				ans += pre
				if add > 1:
					ans += N & add - 1
			n = n >> 1
			pre = pre * 2 + (add - 1)
			add = add * 2
		return ans


import math

class Solution:

	def countBits(self, n):
		if n == 0:
			return 0
		k = math.log(n, 2)
		k = int(k)
		prev = int(k * 2 ** (k - 1))
		next = int(n - 2 ** k)
		return next + 1 + prev + self.countBits(next)


class Solution:

	def countBits(self, N):
		if N <= 1:
			return N
		x = self.left_set_bit(N)
		return x * (1 << x - 1) + (N - (1 << x) + 1) + self.countBits(N - (1 << x))

	def left_set_bit(self, n):
		res = -1
		while n:
			n = n >> 1
			res += 1
		return res


class Solution:

	def f(self, n):
		x = 0
		while 1 << x <= n:
			x += 1
		return x - 1

	def countBits(self, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		x = self.f(N)
		return x * 2 ** (x - 1) + N - 2 ** x + 1 + self.countBits(N - 2 ** x)


class Solution:

	def countBits(self, N):

		def highest_power(n):
			a = 1
			power = 1
			while a * 2 <= n:
				a = a * 2
				power += 1
			return power - 1

		def rec(n):
			if n == 0:
				return 0
			if n == 1:
				return 1
			temp = highest_power(n)
			return 2 ** (temp - 1) * temp + (n - 2 ** temp + 1) + rec(n - 2 ** temp)
		return rec(N)


class Solution:

	def countBits(self, N):

		def largestpower(n):
			x = 0
			while 1 << x <= n:
				x += 1
			return x - 1

		def countsetbits(n):
			if n <= 1:
				return n
			x = largestpower(n)
			return x * pow(2, x - 1) + (n - pow(2, x) + 1) + countsetbits(n - pow(2, x))
		return countsetbits(N)


class Solution:

	def countBits(self, N):
		if N <= 0:
			return 0
		elif N == 1:
			return 1
		x = 0
		while 1 << x <= N:
			x += 1
		x -= 1
		return (1 << x - 1) * x + (N - (1 << x) + 1) + self.countBits(N - (1 << x))


class Solution:

	def countBits(self, N):
		from math import log2
		total = 0
		comuputal = 1
		pow2 = 1
		bits_count = int(log2(N)) + 1
		ones = 0
		for i in range(bits_count):
			if N >> i & 1:
				ones += 1
		for i in range(bits_count):
			if N & 1:
				ones -= 1
				total += comuputal + pow2 * ones
			comuputal = comuputal * 2 + pow2 - 1
			pow2 *= 2
			N = N >> 1
		return total


class Solution:

	def getAmountOfBits(self, n: int) -> int:
		start = 1
		cnt = 1
		while start <= n:
			start *= 2
			cnt += 1
		return cnt - 1

	def helper(self, n: int, start: int=4, total: int=3):
		count = n + 1 - start
		for i in range(count):
			total += i + 1
		if count > 2:
			total -= count - 2
		return total

	def countBits(self, n: int) -> int:
		numDigits = self.getAmountOfBits(n)
		total = 1
		if numDigits == 1:
			return total
		else:
			if n == 2 ** numDigits - 1:
				const = 1
				for i in range(1, numDigits):
					const *= 2
					total += const + i * (const >> 1)
			else:
				const = 1
				for i in range(1, numDigits - 1):
					const *= 2
					total += const + i * (const >> 1)
				const *= 2
				number_per_group_full = 1
				number_per_group_non_full = 0
				k = n - const + 1
				total += k
				while k >= 1:
					total += k // 2 * number_per_group_full
					if k % 2 == 1:
						total += number_per_group_non_full
						number_per_group_non_full += number_per_group_full
					k = k // 2
					number_per_group_full *= 2
			return total


def powerLargest(N):
	x = 0
	while 1 << x <= N:
		x += 1
	return x - 1

class Solution:

	def countBits(self, N):
		if N <= 1:
			return N
		x = powerLargest(N)
		return x * pow(2, x - 1) + (N - pow(2, x) + 1) + self.countBits(N - pow(2, x))


class Solution:

	def countBits(self, N):

		def largestTwoPower(N):
			x = 0
			while 1 << x <= N:
				x += 1
			return x - 1
		if N <= 1:
			return N
		x = largestTwoPower(N)
		return x * int(2 ** (x - 1)) + (N - (1 << x) + 1) + self.countBits(N - (1 << x))


class Solution:

	def countBits(self, N):

		def getpower(temp):
			x = 0
			while 1 << x <= temp:
				x += 1
			return x - 1

		def solve(n):
			if n == 0 or n == 1:
				return n
			p = getpower(n)
			temp = 1 << p - 1
			return p * temp + n - (1 << p) + 1 + solve(n - (1 << p))
		return solve(N)


import math

class Solution:

	def count_all_comb_bits(self, n):
		if n <= 0:
			return 0
		if n == 1:
			return 1
		return n * (1 << n - 1)

	def left_most_1(self, n):
		return math.floor(math.log(n, 2)) + 1

	def countBits(self, N, M=0):
		if N == 0:
			return M
		left_most_idx = self.left_most_1(N)
		if N == 1:
			return M * (1 << left_most_idx - 1) + M + 1
		result = self.count_all_comb_bits(left_most_idx - 1) + M * (1 << left_most_idx - 1)
		return self.countBits(N - (1 << left_most_idx - 1), M + 1) + result


class Solution:

	def countBits(self, N):

		def solve(n):
			if n < 2:
				return n
			x = 1
			i = 0
			while 1:
				if x << i > n:
					break
				i += 1
			i -= 1
			temp = (1 << i - 1) * i
			temp += n - (1 << i) + 1
			return temp + solve(n - (1 << i))
		return solve(N)


class Solution:

	def findMaxPowerWithinRange(self, num):
		x = 0
		while pow(2, x) <= num:
			x = x + 1
		return x - 1

	def countBits(self, N):
		x = self.findMaxPowerWithinRange(N)
		if N == 0:
			return 0
		firstExpression = pow(2, x - 1) * x
		secondExpression = N - pow(2, x) + 1
		ans = firstExpression + secondExpression + self.countBits(N - pow(2, x))
		ans = int(ans)
		return ans


class Solution:

	def largestPowerOfTwoInRange(self, N):
		power = 0
		while pow(2, power) <= N:
			power = power + 1
		return power - 1

	def countSetBits(self, num):
		setBitsCount = 0
		while num != 0:
			bit = num & 1
			if bit == 1:
				setBitsCount = setBitsCount + 1
			num = num >> 1
		return setBitsCount

	def countBits(self, N):
		if N == 0:
			return 0
		x = self.largestPowerOfTwoInRange(N)
		ans = pow(2, x - 1) * x + (N - pow(2, x) + 1) + self.countBits(N - pow(2, x))
		ans = int(ans)
		return ans


class Solution:

	def powerOf2(self, n):
		x = 0
		while pow(2, x) <= n:
			x += 1
		return x - 1

	def countBits(self, n):
		if n <= 1:
			return n
		x = self.powerOf2(n)
		ans = pow(2, x - 1) * x + (n - pow(2, x) + 1) + self.countBits(n - pow(2, x))
		return ans


class Solution:

	def findLargestPower(self, n):
		x = 0
		while 1 << x <= n:
			x += 1
		return x - 1

	def countBits(self, N):
		if N <= 1:
			return N
		x = self.findLargestPower(N)
		return x * pow(2, x - 1) + (N - pow(2, x) + 1) + self.countBits(N - pow(2, x))


class Solution:

	def countBits(self, N):
		n = N

		def get_left_most_set_bit(n):
			left_most_set_bit_indx = 0
			while n > 0:
				left_most_set_bit_indx += 1
				n >>= 1
			return left_most_set_bit_indx
		left_most_set_bit_indx = get_left_most_set_bit(n)
		total_rep = 0
		mod = 0
		nearest_pow = 0
		total_set_bit_count = 0
		add_remaining = 0
		curr = 0
		for i in range(1, left_most_set_bit_indx + 1):
			nearest_pow = pow(2, i)
			if nearest_pow > n:
				last_pow = pow(2, i - 1)
				mod = n % last_pow
				total_set_bit_count += mod + 1
			else:
				if i == 1 and n % 2 == 1:
					total_rep = (n + 1) / nearest_pow
					mod = nearest_pow % 2
					add_remaining = 0
				else:
					total_rep = int(n / nearest_pow)
					mod = n % nearest_pow
					add_remaining = int(mod - nearest_pow / 2 + 1) if mod >= nearest_pow / 2 else 0
				curr = int(total_rep * (nearest_pow / 2) + add_remaining)
				total_set_bit_count += curr
		return total_set_bit_count


def power(n):
	x = 0
	while 2 ** x <= n:
		x += 1
	return x - 1

class Solution:

	def countBits(self, n):
		if n == 0:
			return 0
		if n == 3:
			return 4
		x = power(n)
		ans = x * 2 ** (x - 1) + (n - 2 ** x + 1) + self.countBits(n - 2 ** x)
		ans1 = int(ans)
		return ans1


class Solution:

	def countBits(self, N):
		n = len(bin(N))
		ans = 0
		N += 1
		for i in range(1, n + 1):
			q = N // 2 ** i
			r = N % 2 ** i
			first = q * 2 ** (i - 1)
			if r > 2 ** (i - 1):
				second = r - 2 ** (i - 1)
			else:
				second = 0
			ans = ans + first + second
		return ans


import math

class Solution:

	def _calc(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		if n == 2:
			return 2
		if n == 3:
			return 4
		x = int(math.log2(n))
		left = n - math.pow(2, x)
		if left > 0:
			return self._calc(left) + left + self._calc(math.pow(2, x))
		else:
			half_x = math.pow(2, x - 1)
			x1 = self._calc(half_x)
			return 2 * x1 - 1 + half_x

	def countBits(self, N):
		return int(self._calc(N))


class Solution:

	def countBits(self, n):
		ans = 0
		for i in range(32):
			part1 = n + 1 >> i + 1 << i
			part2 = n + 1 - (1 << i) - (n + 1 >> i + 1 << i + 1)
			if part2 > 0:
				ans += part1 + part2
			else:
				ans += part1
		return ans


import math

class Solution:

	def countBits(self, N):
		a = 0
		n = int(math.log(N, 2)) + 1
		for x in range(n + 1):
			b = 2 ** (x + 1)
			c = 2 ** x
			a += (N + 1) // b * c
			if (N + 1) % b > c:
				a += (N + 1) % 2 ** x
		return a


import math

class Solution:

	def countBits(self, n):
		if n <= 1:
			return n
		x = math.floor(math.log(n, 2))
		return x * pow(2, x - 1) + (n - pow(2, x) + 1) + self.countBits(n - pow(2, x))


class Solution:

	def countBits(self, N):
		two = 2
		ans = 0
		n = N
		while n != 0:
			ans += int(N / two) * (two >> 1)
			if N & two - 1 > (two >> 1) - 1:
				ans += (N & two - 1) - (two >> 1) + 1
			two <<= 1
			n >>= 1
		return ans


import math

class Solution:

	def closest(self, n):
		i = 0
		while 1 << i <= n:
			i += 1
		return i if 1 << i == n else i - 1

	def countBits(self, N):
		if N <= 1:
			return N
		lc = int(math.log(N, 2))
		ans = lc * (1 << lc - 1) + (N + 1 - (1 << lc))
		return ans + self.countBits(N - (1 << lc))


class Solution:

	def countBits(self, N):
		N = N + 1
		k = 0
		res = 0
		while True:
			f = pow(2, k)
			r = N % f
			q = N // f
			if q == 0:
				return res
			if r == 0 or q % 2 == 0:
				q = q // 2
				res = res + q * pow(2, k)
			else:
				q = q // 2
				res = res + q * pow(2, k) + r
			k = k + 1


class Solution:

	def nearest(self, A):
		i = 0
		while 1 << i <= A:
			i = i + 1
		return i - 1

	def countBits(self, N):
		if N <= 1:
			return N
		x = self.nearest(N)
		a = x * (1 << x - 1)
		b = N - (1 << x) + 1
		return a + b + self.countBits(N - (1 << x))


class Solution:

	def countBits(self, n):
		i = 0
		bitmap = 1
		total = 0
		while 2 ** i <= n:
			powi = 1 << i
			if powi & n:
				rem = (n & bitmap) - powi
				total += powi // 2 * i + 1 + rem
			i += 1
			bitmap <<= 1
			bitmap += 1
		return total


import math

class Solution:

	def highestpower(self, n):
		i = 0
		while math.pow(2, i) <= n:
			i += 1
		return i - 1

	def countBits(self, n):
		x = self.highestpower(n)
		if n <= 0:
			return 0
		return int(x * math.pow(2, x - 1) + (n - math.pow(2, x) + 1) + self.countBits(n - math.pow(2, x)))


class Solution:

	def largest2power(self, n):
		x = 0
		while 2 ** x <= n:
			x += 1
		return x - 1

	def countBits(self, N):
		if N == 0:
			return 0
		x = self.largest2power(N)
		return int(2 ** (x - 1) * x + (N - 2 ** x + 1) + self.countBits(N - 2 ** x))


class Solution:

	def countBits(self, N):

		def getleftmost(n):
			m = 0
			while n > 1:
				n >>= 1
				m += 1
			return m

		def backtrack(n, m):
			if not n:
				return 0
			if n == (1 << m + 1) - 1:
				return (m + 1) * (1 << m)
			n = n - (1 << m)
			return n + 1 + self.countBits(n) + m * (1 << m - 1)
		m = getleftmost(N)
		return backtrack(N, m)


import math

class Solution:

	def countBits2(self, N):
		bitTable = [0] * 256
		for i in range(256):
			bitTable[i] = (i & 1) + bitTable[i // 2]
		count = 0
		for i in range(1, N + 1):
			count += bitTable[i & 255]
			i >>= 8
			count += bitTable[i & 255]
			i >>= 8
			count += bitTable[i & 255]
			i >>= 8
			count += bitTable[i & 255]
		return count

	def countBits(self, N):
		n = N + 1
		i = 1
		count = 0
		while N:
			powerOf2Div = 1 << i
			powerOf2 = 1 << i - 1
			count += n // powerOf2Div * powerOf2
			remainder = n % powerOf2Div
			if remainder != 0 and remainder > powerOf2:
				count += remainder - powerOf2
			i += 1
			N >>= 1
		return count