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!

Difficulty: interview

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):
    """
    Each number has a particular number of digits in its binary representation.
    There are sets of numbers with the same number of digits in their binary representation.
    For example there is a set of 4-digit-numbers: 8,9,10,11,12,13,14,15.

    num | binary representation
      8 | 1 0 0 0
      9 | 1 0 0 1
     10 | 1 0 1 0
     11 | 1 0 1 1
     12 | 1 1 0 0
     13 | 1 1 0 1
     14 | 1 1 1 0
     15 | 1 1 1 1

    That kind of sets of n-digit numbers we will call 'blocks'.
    For whole blocks we can easily calculate sum of ones with the formula 2^(n-1) * (1 + 0.5*(n-1))
    But 'left' and 'right' digits can be somewhere inside of their blocks, so we have to sum only part of ones in block.

    For example, in case of range <10, 35> we have to split our calculation in 3 parts:
    1) Sum of the incomplete 4-digit-block, which contains number 10.
    Number 10 splits that block on two parts and we sum ones only from second part (for numbers 10-15).
    2) Sum of 5-digit-block (ones in numbers: 16-31)
    3) Sum of the incomplete 6-digit-block, which contains number 35.
    Number 35 splits that block on two parts and we sum ones only from first part (for numbers 32-35).

    :return: sum of ones in binary representation of all numbers in range <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: number of digits in binary representation of integer"""
    return len(str(bin(number))) - 2


def calculate_starting_digit(n_digits):
    """
    We know, that the block of n-digits-numbers contains of 2^(n-1) numbers
    To calculate first number of 4-digits-block we have to count numbers from previous blocks and add 1:
    2^(1-1) + 2^(2-1) + 2^(3-1) + 1 = 1 + 2 + 4 + 1 = 8
    :return: first number of n_digits-block
    """
    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):
    """
    We use of following properties:
    - First column of block is always filled with ones.
    - Second column contains of dwo parts: half column of zeroes and half column of ones.
        If we split next column in half, each part will follow above pattern.
        If we split next column into four pieces, each part will follow the same pattern from second column and so on.
    
    We iterate through consecutive columns, moving 'middle_row' indicator as we split columns in smaller parts.
    As we calculating second part of block, we add all ones under our indicator (including one on indicator) and ommit ones above.
    
    :param n_digits: number of digits in binary representation
    :param position: position of number in n_digits-block
    :param front_part: indicates whether we calculate normally ('second part' of block - from position to the end)
            or we subtract second part from sum of ones in whole block and return 'first part'
    :return: In block split in two parts by position we return sum of one form second or first part
    """
    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):
    """
    :return: sum of ones in all block from digits_start-block to digits_stop-block
    """
    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):
    # Your code here!
    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):
    # Your code here!
    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)