You are given a number N. Find the total count of set bits for all numbers from 1 to N(both inclusive).
Example 1:
Input: N = 4
Output: 5
Explanation:
For numbers from 1 to 4.
For 1: 0 0 1 = 1 set bits
For 2: 0 1 0 = 1 set bits
For 3: 0 1 1 = 2 set bits
For 4: 1 0 0 = 1 set bits
Therefore, the total set bits is 5.
Example 2:
Input: N = 17
Output: 35
Explanation: From numbers 1 to 17(both inclusive), 
the total number of set bits is 35.
Your Task: The task is to complete the function countSetBits() that takes n as a parameter and returns the count of all bits.
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{8}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    #Function to return sum of count of set bits in the integers from 1 to n.

    def countSetBits(self,n):

        # code here

        # return the count

Solutions:
import math

class Solution:

	def countSetBits(self, n):
		digits = math.ceil(math.log(n + 1, 2))
		count = 0
		for i in range(digits):
			div = 2 ** (i + 1)
			divi = (n + 1) // div
			rem = (n + 1) % div
			mul = 2 ** i
			if rem <= div // 2:
				rem = 0
			else:
				rem = rem - div // 2
			count += mul * divi + rem
		return count


class Solution:

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

	def countSetBits(self, n):
		if n == 0:
			return 0
		x = self.highestpow2(n)
		pow2 = x * 2 ** (x - 1)
		rem = n - 2 ** x + 1
		rest = n - 2 ** x
		ans = pow2 + rem + self.countSetBits(rest)
		return int(ans)


class Solution:

	def countSetBits(self, n):
		(res, i, ln) = (0, 1, n)
		while ln != 0:
			q = (n + 1) // 2 ** i
			a = (n + 1) % 2 ** i
			b = 2 ** (i - 1)
			res = res + q * b
			if a > b:
				res = res - b + a
			ln = ln // 2
			i += 1
		return res


import math

class Solution:

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


import math

class Solution:

	def countSetBits(self, n):

		def count(n):
			if n <= 1:
				return n
			power = int(math.log2(n))
			less = 2 ** power
			digit = less // 2 * power
			c = n - less
			ans = 1 + digit + c + count(c)
			return ans
		return count(n)


class Solution:

	def countSetBits(self, n):
		n += 1
		powerOf2 = 2
		cnt = n // 2
		while powerOf2 <= n:
			totalPairs = n // powerOf2
			cnt += totalPairs // 2 * powerOf2
			if totalPairs & 1:
				cnt += n % powerOf2
			else:
				cnt += 0
			powerOf2 <<= 1
		return cnt


class Solution:

	def countSetBits(self, n):
		count = 0
		factor = 1
		while n >= factor:
			pairs = (n + 1) // (factor * 2) * factor
			ones = max(0, (n + 1) % (factor * 2) - factor)
			count += pairs + ones
			factor *= 2
		return count


class Solution:

	def countSetBits(self, n):
		po = 1
		suma = 0
		while n * 2 >= po:
			suma += (n + 1) // (po * 2) * po
			a = (n + 1) % (po * 2)
			if a - po > 0:
				suma += a - po
			po = po * 2
		return suma


class Solution:

	def countSetBits(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


class Solution:

	def countSetBits(self, n):
		r = 0
		t = n
		i = 1
		while t != 0:
			q = (n + 1) // 2 ** i
			w = (n + 1) % 2 ** i
			b = 2 ** (i - 1)
			r = r + q * b
			if w > b:
				r = r - b + w
			t = t // 2
			i += 1
		return r


class Solution:

	def countSetBits(self, n):
		count = 0
		i = 0
		while 2 ** i <= n:
			total_pairs = n // 2 ** (i + 1)
			total_ones = total_pairs * 2 ** i
			remaining_ones = max(0, n % 2 ** (i + 1) - 2 ** i + 1)
			count += total_ones + remaining_ones
			i += 1
		return count


class Solution:

	def countSetBits(self, n):
		n += 1
		count = 0
		x = 2
		while x // 2 < n:
			quotient = n // x
			count += quotient * x // 2
			reminder = n % x
			if reminder > x // 2:
				count += reminder - x // 2
			x = x * 2
		return count


import math

class Solution:

	def countSetBits(self, n):
		count = 0
		m = int(math.log(n, 2))
		while m >= 0:
			b = (n + 1) // 2 ** m
			count += b // 2 * 2 ** m
			if b % 2 != 0:
				count += (n + 1) % 2 ** m
			m -= 1
		return count


from math import *

class Solution:

	def countSetBits(self, n):
		n += 1
		count = 0
		x = 2
		while x // 2 < n:
			quotient = n // x
			count += quotient * x // 2
			remainder = n % x
			if remainder > x // 2:
				count += remainder - x // 2
			x = x * 2
		return count


import math

class Solution:

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


import math

class Solution:

	def countSetBits(self, n):
		res = 0
		store = 0
		original = n
		while n > 0:
			ne = n
			n = n & n - 1
			if n > 0:
				store = store + (original - n)
			x = ne ^ n
			if x == 1:
				res = res + 1
			else:
				res = res + math.log2(x) * pow(2, math.log2(x) - 1)
				res = res + 1
		return int(res + store)


from collections import defaultdict

class Solution:

	def countSetBits(self, n):
		cnt = defaultdict(int)
		cnt[1] = 1
		k = 1
		i = 2
		while i <= n:
			cnt[i] = i // 2 * k + 1
			i *= 2
			k += 1
		i = 1
		while i * 2 <= n:
			i *= 2
		ans = 0
		j = i
		while j > 0:
			if j <= n:
				ans += cnt[j]
				n -= j
				ans += n
			j //= 2
		return ans


class Solution:

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

	def countSetBits(self, n):
		if n <= 1:
			return n
		x = Solution.findLargestPower(self, n)
		return x * pow(2, x - 1) + (n - pow(2, x) + 1) + Solution.countSetBits(self, n - pow(2, x))


class Solution:

	def countSetBits(self, n):
		n = n + 1
		count = n // 2
		powerOf2 = 2
		while powerOf2 < n:
			pairOfOnes = n // powerOf2
			count += pairOfOnes // 2 * powerOf2
			if pairOfOnes & 1:
				extraOnes = n % powerOf2
				count += extraOnes
			powerOf2 <<= 1
		return count


class Solution:

	def countSetBits(self, n):
		n += 1
		po2 = 2
		c = n // 2
		while po2 <= n:
			tp = n // po2
			c += tp // 2 * po2
			if tp & 1:
				c += n % po2
			else:
				c += 0
			po2 <<= 1
		return c


import math

class Solution:

	def countSetBits(self, n):
		ans = 0
		while n:
			temp = n
			while temp & temp - 1:
				temp = temp & temp - 1
			x = math.log(temp, 2)
			ans = ans + int(x * 2 ** (x - 1))
			n = n - temp
			ans = ans + n + 1
		return ans


import math

class Solution:

	def countSetBits(self, n):
		n += 1
		p = 0
		count = 0
		while 2 ** p < n:
			num_groups = math.floor(n / 2 ** p)
			count += math.floor(num_groups / 2) * 2 ** p
			if num_groups & 1 != 0:
				count += n % 2 ** p
			p += 1
		return count


import math

class Solution:

	def countSetBits(self, n):
		if n <= 1:
			return n
		k = math.floor(math.log2(n))
		res = int(k * math.pow(2, k - 1) + n - math.pow(2, k) + 1 + self.countSetBits(n - math.pow(2, k)))
		return res


import math

class Solution:

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


class Solution:

	def countSetBits(self, n):
		S = 0
		t = n + 1
		for i in range(n.bit_length()):
			x2 = 1 << i
			x = x2 << 1
			l = x2 * (t // x)
			s = t % x - x2
			if s < 0:
				s = 0
			S += l + s
		return S


class Solution:

	def countSetBits(self, n):
		intervals = 0
		if n == 1:
			return 1
		ans = 0
		power_2 = 1
		i = 0
		while power_2 <= n:
			intervals = (n + 1) // power_2
			intervals_with_1 = intervals // 2
			ones_in_intervals_with_1 = intervals_with_1 * power_2
			extra_ones = (n + 1) % power_2
			if intervals & 1 == 0:
				ans += ones_in_intervals_with_1
			else:
				ans += ones_in_intervals_with_1
				ans += extra_ones
			power_2 *= 2
		return ans


class Solution:

	def countSetBits(self, n):

		def count(num):
			ans = ''
			while num:
				rem = num % 2
				num = num // 2
				ans = str(rem) + ans
			return ans
		bits = len(count(n))
		bitpow = [1]
		for i in range(bits):
			bitpow.append(bitpow[-1] * 2)
		totnum = n + 1
		ans = 0
		for i in range(bits):
			zo = totnum // bitpow[i]
			if zo % 2 == 0:
				ans += zo // 2 * bitpow[i]
			else:
				ans += zo // 2 * bitpow[i]
				ans += totnum % bitpow[i]
		return ans


import math

class Solution:

	def countSetBits(self, n):
		num = int(math.log2(n))
		left = n - 2 ** num
		count = 0
		while left > 0:
			count += 2 ** (num - 1) * num
			count += 1 * left + 1
			n = left
			num = int(math.log2(n))
			left = n - 2 ** num
		count += 2 ** (num - 1) * num + 1
		return int(count)


class Solution:

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

	def countSetBits(self, n):

		def helper(n):
			if n == 0:
				return 0
			x = self.largestPowOf2(n)
			beforeLargestPow2Bits = (1 << x - 1) * x if x > 0 else x
			lastSetBitsFromPow2toN = n - (1 << x) + 1
			rest = n - (1 << x)
			remainingSetBitsTillN = self.countSetBits(rest)
			ans = beforeLargestPow2Bits + lastSetBitsFromPow2toN + remainingSetBitsTillN
			return ans
		return helper(n)


import math

class Solution:

	def countSetBits(self, n):
		if n <= 1:
			return n
		a = math.log(n, 2)
		a = int(a)
		b = 2 ** a // 2
		c = n - 2 ** a
		sol = a * b + 1 + c + self.countSetBits(c)
		return sol


class Solution:

	def countSetBits(self, n):
		n = n + 1
		p = 1
		sum = n // 2
		while pow(2, p) < n:
			d = n // pow(2, p)
			if d % 2 == 0:
				sum = sum + d // 2 * pow(2, p)
			else:
				sum = sum + d // 2 * pow(2, p) + n % pow(2, p)
			p = p + 1
		return sum


class Solution:

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

	def countSetBits(self, n):
		if n == 0:
			return 0
		x = self.countpower(n)
		x1 = x * pow(2, x - 1)
		x2 = n - pow(2, x) + 1
		rest = n - pow(2, x)
		ans = x1 + x2 + self.countSetBits(rest)
		return int(ans)


import math

class Solution:

	def countSetBits(self, n):
		if n <= 1:
			return n
		x = int(math.log2(n))
		return x * (1 << x - 1) + (n - (1 << x) + 1) + self.countSetBits(n - (1 << x))


class Solution:

	def countSetBits(self, n):
		res = 0
		i = 2
		while i // 2 <= n:
			groups = n // i
			one_group_size = i // 2
			res += groups * one_group_size
			if n % i >= one_group_size:
				res += n % i + 1 - one_group_size
			i <<= 1
		return res


import math

class Solution:

	def countSetBits(self, n):
		ebit = 0
		count = 0
		while True:
			k = int(math.log2(n + 1))
			count += 2 ** k * ebit + k * 2 ** (k - 1)
			if 2 ** k == n + 1 or n == 0:
				break
			else:
				n = n % 2 ** k
				ebit += 1
		return int(count)


class Solution:

	def countSetBits(self, n):

		def findPrevPower(n):
			pos = -1
			while n != 0:
				n = n >> 1
				pos += 1
			return pos

		def f(n):
			if n < 1:
				return 0
			if n == 1:
				return 1
			x = findPrevPower(n)
			return 2 ** x * x // 2 + (n - 2 ** x + 1) + f(n - 2 ** x)
		return f(n)


class Solution:

	def countSetBits(self, n):
		res = 0
		x = 2
		n = n + 1
		while x // 2 < n:
			q = n // x
			res += q * x // 2
			remainder = n % x
			if remainder > x // 2:
				res += remainder - x // 2
			x = x * 2
		return res


class Solution:

	def countSetBits(self, n):
		count = 0
		i = 1
		while i <= n:
			p = 2 * i
			groups = (n + 1) // p
			count += groups * i
			count += max((n + 1) % p - i, 0)
			i = p
		return count


from math import floor, log2

class Solution:

	def countSetBits(self, n):

		def largestPowerOf2(n):
			return floor(log2(n))

		def fun(n):
			if n < 2:
				return n
			x = largestPowerOf2(n)
			temp1 = x * (1 << x - 1)
			temp2 = n - (1 << x) + 1
			rest = n - (1 << x)
			return temp1 + temp2 + fun(rest)
		return fun(n)


class Solution:

	def countSetBits(self, n):

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

		def fun(n):
			if n < 2:
				return n
			x = largestPowerOf2(n)
			temp1 = x * (1 << x - 1)
			temp2 = n - (1 << x) + 1
			rest = n - (1 << x)
			return temp1 + temp2 + fun(rest)
		return fun(n)


class Solution:

	def two(self, nu):
		x = 0
		while 1 << x <= nu:
			x += 1
		return int(x - 1)

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


import math

class Solution:

	def countSetBits(self, n):
		if n <= 1:
			return n
		else:
			x = int(math.log(n, 2))
			p = Solution()
			count = x * pow(2, x - 1) + (n + 1 - pow(2, x)) + p.countSetBits(n - pow(2, x))
		return count


class Solution:

	def countSetBits(self, N):
		if N <= 2:
			return N
		if N <= 4:
			return N + 1
		powerOf2 = 2
		setBits = 0
		n = N
		while n != 0:
			setBits += N // powerOf2 * (powerOf2 >> 1)
			if N & powerOf2 - 1 > (powerOf2 >> 1) - 1:
				setBits += (N & powerOf2 - 1) - (powerOf2 >> 1) + 1
			powerOf2 <<= 1
			n >>= 1
		return setBits


class Solution:

	def countSetBits(self, n):
		gul = 0
		g = 1
		while g <= n:
			g = g * 2
			quotient = (n + 1) // g
			remainder = (n + 1) % g
			total = quotient * (g // 2)
			if remainder > g // 2:
				total += remainder - g // 2
			gul += total
		return gul


class Solution:

	def countSetBits(self, n: int) -> int:
		if n == 0:
			return 0
		p = 0
		while 2 ** p <= n:
			p += 1
		p -= 1
		ans = p * 2 ** p // 2 + (n - 2 ** p + 1) + self.countSetBits(n - 2 ** p)
		return ans


class Solution:

	def countSetBits(self, n):

		def powe(n):
			x = 0
			while 1 << x <= n:
				x += 1
			return x - 1
		if n <= 0:
			return n
		x = powe(n)
		return int(x * pow(2, x - 1)) + int(n - pow(2, x) + 1) + self.countSetBits(n - pow(2, x))


class Solution:

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

	def countSetBits(self, n):
		if n == 0:
			return 0
		powr = self.power(n)
		val = 2 ** (powr - 1)
		count = val * powr
		count += n - 2 ** powr + 1
		count += self.countSetBits(n - 2 ** powr)
		return int(count)


class Solution:

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

	def countSetBits(self, n):
		if n == 0:
			return 0
		pow = self.powOfTwo(n)
		val = 2 ** (pow - 1)
		count = val * pow + (n - 2 ** pow + 1) + self.countSetBits(n - 2 ** pow)
		return int(count)


class Solution:

	def countSetBits(self, n):

		def max2(n):
			r = 0
			while 1 << r <= n:
				r += 1
			return r - 1

		def sol(n):
			if n <= 1:
				return n
			x = max2(n)
			return x * pow(2, x - 1) + (n - pow(2, x) + 1) + sol(n - pow(2, x))
		return sol(n)


class Solution:

	def countSetBits(self, n):

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

		def countBits(n):
			if n <= 1:
				return n
			x = get_highest_pow_of_two(n)
			bits_till_2_pow_x = x * (1 << x - 1)
			msb_from_2_pow_x_to_n = n - (1 << x) + 1
			rest_bits = countBits(n - (1 << x))
			return bits_till_2_pow_x + msb_from_2_pow_x_to_n + rest_bits
		return countBits(n)


class Solution:

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

	def countSetBits(self, n):
		if n == 1:
			return 1
		elif n == 0:
			return 0
		x = self.count_power_of_x(n)
		bits_till_2x = (1 << x - 1) * x
		msb_from_2x_n = n - (1 << x) + 1
		rest_bits = n - (1 << x)
		total_count = bits_till_2x + msb_from_2x_n + self.countSetBits(rest_bits)
		return total_count


class Solution:

	def countSetBits(self, n):
		start = 1
		result = 0
		for i in range(len(str(bin(n)))):
			count = n - start + 1
			groups = count // start
			if groups % 2 == 0:
				result += groups // 2 * start + count % start
			else:
				result += (groups // 2 + 1) * start
			start *= 2
		return result


class Solution:

	def countSetBits(self, n):
		n = n + 1
		power_of_two = 2
		count = n // 2
		while n >= power_of_two:
			pairs = n // power_of_two
			count = count + pairs // 2 * power_of_two
			if pairs & 1 != 0:
				count = count + n % power_of_two
			power_of_two = power_of_two << 1
		return count


import math

class Solution:

	def countSetBits(self, n):
		if n <= 1:
			return n
		logpo2 = int(math.log(n, 2))
		po2 = 2 ** logpo2
		sol = logpo2 * (po2 // 2) + 1 + (n - po2) + self.countSetBits(n - po2)
		return sol


class Solution:

	def countSetBits(self, n):
		c = 0
		while True:
			l = len(bin(n)[2:])
			c += (l - 1) * 2 ** (l - 2)
			n -= 2 ** (l - 1)
			c += n + 1
			if n < 3:
				c += n
				break
		return c


class Solution:

	def countSetBits(self, n):
		count = 0
		i = 1
		while n // i > 0:
			count += n // (i * 2) * i
			if n % (i * 2) > i:
				count += n % (i * 2) - i + 1
			i <<= 1
		return count + 1


class Solution:

	def countSetBits(self, n):
		cnt = 0
		k = 1
		temp = n
		while temp > 0:
			cnt += n // 2 ** k * 2 ** (k - 1) + max(n % 2 ** k + 1 - 2 ** (k - 1), 0)
			k += 1
			temp = temp // 2
		return cnt


def largestPowerOfTwo(num):
	if num == 0:
		return -1
	k = 1
	pos = 0
	while k <= num:
		k = k * 2
		pos += 1
	return pos - 1

class Solution:

	def countSetBits(self, n):
		if n == 0:
			return 0
		pos = largestPowerOfTwo(n)
		k = 2 ** pos
		ans = 2 ** (pos - 1) * pos + 1 + (n - k) + self.countSetBits(n - k)
		return int(ans)


class Solution:

	def countSetBits(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:
	cnt = 0

	def countSetBits(self, n):
		if n == 0:
			return 0
		x = math.floor(math.log2(n))
		po = math.floor(2 ** x)
		return x * math.floor(2 ** (x - 1)) + (n - po + 1) + self.countSetBits(n - po)


import math

class Solution:

	def countSetBits(self, n):
		total_bits = 0
		while n > 0:
			bits = int(math.log2(n))
			total_bits = total_bits + pow(2, bits - 1) * bits
			n = n - pow(2, bits)
			total_bits = total_bits + n + 1
		return int(total_bits)


class Solution:

	def countSetBits(self, d):

		def aux(n):
			if n <= 1:
				return n
			x = 0
			while 1 << x <= n:
				x += 1
			x = x - 1
			return (1 << x - 1) * x + (n + 1 - (1 << x)) + aux(n - (1 << x))
		return aux(d)