How to count the total number of set bits for the number

user_16685119 0
Viewed 505
  • Given a positive integer A, the task is to count the total number of set bits in the binary representation of all the numbers from 1 to A.
 A = 3
 DECIMAL    BINARY  SET BIT COUNT
    1          01        1
    2          10        1
    3          11        2

1 + 1 + 2 = 4

  • I got correct output

Code is below

def solve(A):
     ad = ''
     for i in range(A + 1):
         ad += str(bin(i).replace('ob',''))
     return ad.count('1')

With Bit-wise

  def solve(A):
        count = 0
        for i in range(A + 1):
            while i > 0:
                i= i & (i-1)
                count += 1
        return (count)
  • In both scenarios I am getting Time Limit Exceeded.
time-complexity python
3 Answers

This would work in O(log(A)) so you shouldn't have Time Limit Exceeded :

def solve(A):
  count = 0
  n = A
  i = 0
  while n > 0:
    if (n & 1) == 1:
      f = ((1 << i) >> 1) * i
      g = (((1 << i) - 1) & A) + 1
      count += f + g
    n >>= 1
    i += 1
  return count

The total number of set bits between 0 and 2^n excluded is 2^(n-1)*n. Because in this particular case, 50% of bits are set in each column and other 50% are unset, and there is n columns.

For a number A which is not a power of 2, we can break down the calculation into several passes, one for each set bit in the number A in question, and use the expression for exact power of 2 (variable f). We must also take care of an additional column of 1 each time (variable g).

Schema to see why it works

user_167043670

I was working on a solution similar to covstag's one, but my way of calculating the sum of bits set for a power of 2 was definitely clumsier. So I stole the idea and adapted it to my solution; the result is just slightly faster, but perhaps easier to understand:

def solve(A):
    loop = 0
    current = 0
    bits = f'{A:b}'
    expo = len(bits) - 1
    for b in bits[:-1]:
        if b == '1':
            power = 2**(expo-1)
            current += expo * power + 1 + 2 * power * loop
            loop += 1
        expo -= 1
    if bits[-1] != '0':
        current += loop + 1
    return current
user_158442960

This would work:

def solve(A):
    return sum(int(b) for n in range(1, A + 1) for b in f"{n:b}" if b == '1')

This is another, very classic, way:

def solve(A):
    result = 0
    for n in range(1, A + 1):
        while n > 0:
            result += n % 2
            n //= 2
    return result

In yours first solution, you can improve it a little:

def solve(A):
    result = 0
    for i in range(A + 1):
         result += bin(i).count('1')
    return result

or even to

def solve(A):
    return sum(bin(i + 1).count('1') for i in range(A))

which is similar to my first attempt, maybe even better.

user_121185460
Related