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

Question

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.

This is called a [popcount](https://stackoverflow.com/questions/9829578/fast-way-of-counting-non-zero-bits-in-positive-integer), FYI — ggorlen, Aug 19 '21 at 14:27

score 5 · Accepted Answer · answered Aug 19 '21 at 19:22

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

can you tell algorithm if (n & 1) == 1: f = ((1 << i) >> 1) * i g = (((1 << i) - 1) & A) + 1 count += f + g n >>= 1 i += 1 — Maws, Aug 20 '21 at 15:40

score 2 · Answer 2 · answered Aug 20 '21 at 08:05

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

can u tell algo 2**(expo-1) – – Maws Sep 01 '21 at 15:45 — Maws, Sep 01 '21 at 15:45

Roman Pavelka · Answer 3 · 2021-08-19T11:03:33.417

1

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.

edited Aug 19 '21 at 11:03

answered Aug 19 '21 at 10:40

Roman Pavelka

3,736
2
11
28

what is for b in f"{n:b}" – Maws Aug 19 '21 at 12:05
i got invalid syntax at f" – Maws Aug 19 '21 at 12:08
@Maws, it is a formatting string and `b` stands for binary, you can use `bin(n)` instead of it. It is supported from Python 3.6. See here for more information: https://stackoverflow.com/questions/699866/python-int-to-binary-string/63485151#63485151 – Roman Pavelka Aug 19 '21 at 12:23
I got error TypeError: 'str' object is not callable – Maws Aug 19 '21 at 13:08
1

That means that you overwrote some name used above before, i.e. you did something as `bin = "abc"` or `sum = "xyz"` or `range = "def"` or something like that... Try that in clean environment. – Roman Pavelka Aug 19 '21 at 13:22

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

3 Answers3