Given two numbers: 'left' and 'right' (1 <= 'left' <= 'right' <= 200000000000000)
return sum of all '1' occurencies in binary representations of numbers between 'left' and 'right' (including both)

``` 
Example:
countOnes 4 7 should return 8, because:
4(dec) = 100(bin), which adds 1 to the result.
5(dec) = 101(bin), which adds 2 to the result.
6(dec) = 110(bin), which adds 2 to the result.
7(dec) = 111(bin), which adds 3 to the result.
So finally result equals 8.
```
WARNING: Segment may contain billion elements, to pass this kata, your solution cannot iterate through all numbers in the segment!

Source: codewars | Difficulty: MEDIUM
Tags: Bit manipulation

Starter code: def countOnes(left, right):
	

Solutions:
import math

def count(n):
	if n is 0:
		return 0
	x = int(math.log(n, 2))
	return x * 2 ** (x - 1) + n - 2 ** x + 1 + count(n - 2 ** x)

def countOnes(left, right):
	return count(right) - count(left - 1)


def countOnes(left, right):
	left_binary_digits = count_binary_digits(left)
	right_binary_digits = count_binary_digits(right)
	right_binary_sum = sum([int(i) for i in str(bin(right))[2:]])
	left_position_in_block = left - calculate_starting_digit(left_binary_digits) + 1
	right_position_in_block = right - calculate_starting_digit(right_binary_digits) + 1
	if left_binary_digits == right_binary_digits:
		number_of_ones = calculate_ones_in_incomplete_block(left_binary_digits, left_position_in_block) - calculate_ones_in_incomplete_block(right_binary_digits, right_position_in_block) + right_binary_sum
	else:
		number_of_ones = calculate_ones_in_incomplete_block(left_binary_digits, left_position_in_block) + calculate_multiple_blocks(left_binary_digits + 1, right_binary_digits - 1) + calculate_ones_in_incomplete_block(right_binary_digits, right_position_in_block, True) + right_binary_sum
	return number_of_ones

def count_binary_digits(number):
	return len(str(bin(number))) - 2

def calculate_starting_digit(n_digits):
	return sum([pow(2, i - 1) for i in range(1, n_digits)]) + 1

def calculate_ones_in_incomplete_block(n_digits, position, front_part=False):
	all_rows = pow(2, n_digits - 1)
	upper_ones = 0
	last_row = all_rows
	result = last_row - position + 1
	middle_row = last_row / 2
	for i in range(n_digits - 1):
		if position <= middle_row:
			result += all_rows / 2 - upper_ones
			temp = int(last_row)
			last_row = middle_row
			middle_row -= (temp - middle_row) / 2
		else:
			result += last_row - position + 1 + (all_rows - last_row) / 2
			upper_ones += (last_row - middle_row) / 2
			middle_row += (last_row - middle_row) / 2
	if front_part:
		return all_rows * (1 + 0.5 * (n_digits - 1)) - result
	else:
		return result

def calculate_multiple_blocks(digits_start, digits_stop):
	result = 0
	if digits_stop >= digits_start:
		for i in range(digits_start, digits_stop + 1):
			result += pow(2, i - 1) * (1 + 0.5 * (i - 1))
	return result


from math import log2

def countOnes(left, right):
	return countUpTo(right) - countUpTo(left - 1)

def countUpTo(n):
	s = 0
	while n:
		p = n.bit_length() - 1
		p2 = 1 << p
		s += p * (p2 >> 1) + n - p2 + 1
		n &= ~p2
	return s


sumOnes = lambda n: (lambda msb: n and -~n + ~-msb * 2 ** msb + sumOnes(n - 2 ** (-~msb)))(n.bit_length() - 2)
countOnes = lambda a, b: sumOnes(b) - sumOnes(a - 1)


import math

def countOnes(left, right):

	def onesRangeDigit(n, digit):
		ex = 2 ** digit
		ones = ex * math.floor((n + 1) / (2 * ex)) + max((n + 1) % (2 * ex) - ex, 0)
		return ones

	def onesRange(n):
		ex = math.ceil(math.log(n + 1, 2))
		print(ex)
		ones = 0
		for i in range(ex):
			ones += onesRangeDigit(n, i)
		return ones
	return onesRange(right) - onesRange(left - 1)


def countOnesFromZero(num):
	l = sorted([i for (i, v) in enumerate(bin(num)[2:][::-1]) if v == '1'], reverse=True)
	l.append(0)
	return sum((i * 2 ** v + v * 2 ** (v - 1) for (i, v) in enumerate(l)))

def countOnes(left, right):
	return countOnesFromZero(right) - countOnesFromZero(left) + bin(left).count('1')


def countOnes(left, right):

	def f(n):
		c = 0
		a = list(reversed(list(bin(n))))
		for (i, d) in enumerate(a):
			if d == '1':
				c += 1 + 2 ** i * i / 2 + 2 ** i * a[i + 1:].count('1')
		return c
	return f(right) - f(left - 1)


def countevenone(left, right, span, maxbincount):
	if span == 1:
		return bin(left).count('1')
	if span == 2:
		return bin(right).count('1') + bin(left).count('1')
	if span % 2 != 0:
		if left % 2 == 0:
			adds = span // 2 + bin(right).count('1')
			left = left // 2
			right = (right - 1) // 2
		else:
			adds = span // 2 + bin(left).count('1')
			left = (left + 1) // 2
			right = right // 2
		span = span // 2
		maxbincount = maxbincount - 1
		countones = countevenone(left, right, span, maxbincount) * 2 + adds
	else:
		if left % 2 == 0:
			left = left // 2
			right = right // 2
			adds = span // 2
			span = span // 2
		else:
			adds = (span - 2) // 2 + bin(right).count('1') + bin(left).count('1')
			left = (left + 1) // 2
			right = (right - 1) // 2
			span = (span - 2) // 2
		maxbincount = maxbincount - 1
		countones = countevenone(left, right, span, maxbincount) * 2 + adds
	return countones

def countOnes(left, right):
	span = right - left + 1
	maxbincount = len(bin(right).replace('0b', ''))
	return countevenone(left, right, span, maxbincount)


def countOnes(left, right):

	def bindig(number):
		ans = 0
		g = bin(number)[2:][::-1]
		for i in range(len(g)):
			if g[i] == '1':
				if i == len(g) - 1:
					ans += 1 + 2 ** (i - 1) * i
				else:
					ans += 1 + 2 ** (i - 1) * i + g[i + 1:].count('1') * 2 ** i
		return ans
	return bindig(right) - bindig(left - 1)