Sum of set bits from 1 to n

Question

Given an integer \$ n \$ \$ (n \ge 1) \$, return/output the total number of set bits between \$ 1 \$ and \$ n \$ inclusive. To make the problem more interesting, your solution must run with a time complexity of \$ \mathcal{O}((\log n)^k) \$ or better, for some constant \$ k \$ (AKA poly-logarithmic time complexity).

This is OEIS A000788, not including \$ n = 0 \$. Here are the first 100 numbers:

1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186, 192, 193, 195, 197, 200, 202, 205, 208, 212, 214, 217, 220, 224, 227, 231, 235, 240, 242, 245, 248, 252, 255, 259, 263, 268, 271, 275, 279, 284, 288, 293, 298, 304, 306, 309, 312, 316, 319

This is code-golf, so the shortest code in bytes wins.

Answer 1

JavaScript (ES6),  57 54 53  52 bytes

n=>(i=0,g=b=>b--&&(n>>b&1&&b+i+i++<<b)+g(b))(32)/2+i

Try it online!

This is designed for 32-bit integers and always performs 32 iterations, no matter the input value.

The following version performs \$\lfloor log_2(n)\rfloor+1\$ iterations instead, but this is really pointless since bitwise operations on vanilla JS numbers ^[1] are limited to 32 bits anyway:

n=>(i=0,g=b=>b--&&(n>>b&1&&b+i+i++<<b)+g(b))(32-Math.clz32(n))/2+i

Try it online!

_{[1]: i.e. without using BigInts or a Big Integer library}

How?

As mentioned by Emeric Deutsch in A001787, the total sum of set bits between \$1\$ and \$2^k-1\$ is:

$$k\times 2^{k-1}$$

Below is an illustration of the first few terms:

       1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111
       V \___/ \_____________/ \_____________________________________/
count: 1   3          8                           20
sum  : 1   4          12                          32

Because we only need one extra bit to go from \$2^k-1\$ to \$2^k\$, the total sum of set bits between \$1\$ and \$2^k\$ is:

$$k\times 2^{k-1}+1$$

In order to compute the total sum of set bits between \$1\$ and an arbitrary integer \$N\$ of \$M+1\$ bits, we can use the above formula for each set bit at position \$0\le b\le M\$ in \$N\$. But we also have to take the total number of set bits at a position higher than \$b\$ into account, because they have to be counted several times.

We end up with:

$$\sum_{b=0}^{M} B(b)\times(b\times 2^{b-1}+1+S(b)\times 2^b)$$

where:

• \$B(b)\$ is the value of the bit \$b\$ (0-indexed)
• \$S(b)=\sum_{i=b+1}^{M} B(i)\$

Here is an ungolfed implementation.

In the golfed version, we go from the most to the least significant bit and keep track of the number of set bits in i. Besides, we ignore the +1 in the formula and add i at the very end of the process instead.

Answer 2

K (ngn/k), ⁴⁵ 32 bytes

{+/b*1+(q!'x)+-2!q*<q:2/=#b:2\x}

Try it online!

Golfing ideas thanks to @ngn and @coltim

The OEIS page contains a curious PARI program:

a(n)=if(n==0,0,m=logint(n,2);r=n%2^m;m*2^(m-1)+r+1+a(r));

which has a recursion depth of \$\mathcal{O}(\log n)\$ and each recursive call involves constant number of arithmetic operations (and therefore meets the time complexity requirement).

I translated this recursive formula to vectorized operations on the bit pattern of n, keeping array dimensions to the number of bits of n, so every built-in op takes polylog time of n.

1  0  1  1 0 0 // n = 44 -> 115
5  4  3  2 1 0 // m
16 8  4  2 1 0 // 2^(m-1)
12 12 4  0 0 0 // n mod 2^(m-1)
93    17 5     // m * 2^(m-1) + n mod 2^(m-1) + 1,
               // keeping only ones in the bits of n
sum = 115

How the solution works:

{+/b*1+(q!'x)+-2!(<q)*q:2/=#b:2\x}  x:n
                            b:2\x   b:bit pattern of n
                      q:2/=#b   q:reversed powers of 2
                          =#    identity matrix of size #b
                        2/      evaluate in base 2 column-wise
              -2!(<q)*q    m*2^(m-1) for m in #b-1..0
                  <q       grade up q; the power is in decreasing order
                           so it gives #b-1..0
              -2!(  )*q    multiply 2^m and divide by 2
       (q!'x)+    add n%2^m
     1+           add 1
 +/b*             add the terms corresponding to one bits

Answer 3

JavaScript (ES6), 51 bytes

f=(n,i=0,p=1<<i)=>n<p?0:f(n,i+1)+(n&p&&n%p+1+p*i/2)

Try it online!

Let we denote

$$ n = \left(\overline{b_mb_{m-1}\dots b_2b_1b_0}\right)_2 $$

Then

$$ f\left(n\right)=\sum_{i=0}^{m} b_i \cdot \left(\left(n \bmod 2^i\right) + 1 + 2^{i-1}\cdot i\right) $$

This function loops from \$0\$ to \$m\$ with constant time each loop. And we have

$$ m = \mathcal{O}\left(\log n\right) \ $$

It would be 55 bytes to handle larger numbers (BigInt).

Answer 4

Python 3, 106 104 bytes

def f(A):
 A+=1;a=0
 for i in range(32):
  x=2<<i;d,r=A//x,A%x;a+=d*x/2
  if 2*r>x:a+=r-x/2
 return a 

Try It Online!!

This is designed for 32-bit integers, here I am using float to save some bytes from "//" operator, I hope you won't mind \$x.0\$ instead of \$x\$, further bytes can be reduced if I allow hardcoding input by user.

P.S. This is my first answer, hope to hear some suggestions.

Answer 5

Charcoal, 28 bytes

ＮθＩΣＥ⮌↨θ²⁺×÷θＸ²⊕κＸ²κ×ι⊕﹪θＸ²κ

Try it online! Explanation: For a given bit position k, the sum of the bits at position k from 1 to n depends on whether the kth bit of n is 0 or 1:

• If the kth bit of n is 0, then the bits at position k are of the form 0...1...0...1...0...1...0..0. Each run of 2ᵏ⁺¹ integers contributes 2ᵏ bits.
• If the kth bit of n is 1, then the bits at position k are of the form 0...1...0...1...0...1...0...1..1. This means that there are (n mod 2ᵏ)+1 extra 1 bits to account for.

Since the number of bits is O(log n), this is the major factor in the time complexity of the algorithm.

Ｎθ                              Input `n` as an integer
       θ                        `n`
      ↨ ²                       Converted to base 2
     ⮌                          Reversed so LSB first
    Ｅ                           Map over bits
            θ                   Input `n`
           ÷                    Integer divide by
              ²                 Literal 2
             Ｘ                  Raised to power
                κ               Index `k`
               ⊕                Incremented
          ×                     Multiplied by
                  ²             Literal 2
                 Ｘ              Raised to power
                   κ            Index `k`
         ⁺                      Plus
                     ι          Current bit
                    ×           Multiplied by
                        θ       Input `n`
                       ﹪        Modulo
                          ²     Literal `2`
                         Ｘ      Raised to power
                           κ    Index `k`
                      ⊕         Incremented
   Σ                            Take the sum
  Ｉ                             Cast to string
                                Implicitly print

Answer 6

Python 3, 81 bytes

def f(A):
 c=0
 while A>1:
  a=len(bin(A))-3;A=A%(2**a);c+=2**a*a/2+A
 return c

Try it online!

For exponentials of 2 -1 every bit is flipped 50% of the time so the total sum of bits is n*(# of bits)/2 this gets done recursively. For every further recursion we also need to add up the first bits that get progessively ignored.

Answer 7

Python 3, 64 bytes

f=lambda n:n and(2*f(n//2)+n//2+1if n%2else f(n/2)+f(n/2-1)+n/2)

Try it online!

from the recurrence relation: a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1

Answer 8

Python 3.8 (59 bytes)

f=lambda n:n and(r:=2**(m:=len(bin(n))-3))*m/2+n%r+1+f(n%r)

Here is my attempt 2, since dingledooper noted that my previous attempt was not polylog time complexity.

Also, the golfiness can probably be improved by using walrus operator in python3.8

I used the formula found from "a curious PARI program on the OEIS page": a(n) = if (n==0, 0, m = logint(n, 2); r = n % 2^m; m*2^(m-1) + r + 1 + a(r));

My ungolfed code is:

def a(n):
    output = 0.0
    while n:
        logn = n.bit_length() - 1 # log(n) in base 2, golfed: len(bin(n))-3
        n = n % (2 ** logn) # strip top bit, golfed: n%r
        output += logn*2**(logn-1) + n + 1 # golfed: m*r/2+n%r+1
    return output