18
\$\begingroup\$

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 , so the shortest code in bytes wins.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Technically speaking, if we're allowed to assume the upper bound of the input number (mostly due to the maximum number the language can handle), isn't everything O(1) (which kinda defeats the purpose of the challenge)? \$\endgroup\$
    – Bubbler
    Jun 10 at 1:50
  • \$\begingroup\$ May I consider all +, -, *, / operators with numbers less than n given run in O(1)? \$\endgroup\$
    – tsh
    Jun 10 at 1:53
  • \$\begingroup\$ @Bubbler I think it's ok that the algorithm itself is O(log n). Like you said, as long as it does not defeat the purpose of the challenge. \$\endgroup\$ Jun 10 at 2:18
  • \$\begingroup\$ @tsh I think it's safe to assume that, yes. \$\endgroup\$ Jun 10 at 2:33
  • 3
    \$\begingroup\$ Ironically, despite insistence upon a poly-logarithmic complexity, an O(n) solution in only 10 bytes of x86 assembly will keep up with or outperform most submissions. \$\endgroup\$
    – Cody Gray
    Jun 10 at 10:52
13
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ The formula can be combined wrt 2^(b-1) so this may help compress the code; B(b)×(b×2^(b−1)+1+S(b)×2^b) => B(b)×((b+2S(b))×2^b−1+1) \$\endgroup\$
    – Tragamor
    Jun 10 at 14:16
  • \$\begingroup\$ @Tragamor This is already factorized that way in the golfed code. What I'm doing is essentially b+2*i<<b, which is \$(b+2\times i)\times 2^b\$. \$\endgroup\$
    – Arnauld
    Jun 10 at 14:34
  • \$\begingroup\$ Thanks for explaining; I hadn't picked up the bitwise shifting, and had been scratching my head at the code :-) \$\endgroup\$
    – Tragamor
    Jun 10 at 14:39
13
\$\begingroup\$

K (ngn/k), 45 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
\$\endgroup\$
0
6
\$\begingroup\$

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).

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ -2 bytes, suggested by ReGuess \$\endgroup\$ Jun 10 at 23:06
  • \$\begingroup\$ Oh, that's nice, being habitual of 1<<i I didn't even realised we can we use shift for other numbers too. \$\endgroup\$ Jun 10 at 23:30
  • 1
    \$\begingroup\$ Apologies for the extra edits. I didn't realize this was your own post. We don't typically allow golfs in suggested edits so I accidentally overrode it, but since you are the owner of the answer and you accepted it, I've allowed the edit through. :) \$\endgroup\$
    – hyper-neutrino
    Jun 10 at 23:56
2
\$\begingroup\$

Charcoal, 28 bytes

NθIΣE⮌↨θ²⁺×÷θX²⊕κX²κ×ι⊕﹪θX²κ

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.

Nθ                              Input `n` as an integer
       θ                        `n`
      ↨ ²                       Converted to base 2
     ⮌                          Reversed so LSB first
    E                           Map over bits
            θ                   Input `n`
           ÷                    Integer divide by
              ²                 Literal 2
             X                  Raised to power
                κ               Index `k`
               ⊕                Incremented
          ×                     Multiplied by
                  ²             Literal 2
                 X              Raised to power
                   κ            Index `k`
         ⁺                      Plus
                     ι          Current bit
                    ×           Multiplied by
                        θ       Input `n`
                       ﹪        Modulo
                          ²     Literal `2`
                         X      Raised to power
                           κ    Index `k`
                      ⊕         Incremented
   Σ                            Take the sum
  I                             Cast to string
                                Implicitly print
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ This looks like a good answer, but does it fit the O(polylog n) constraint? Running f(10**20) is really quite slow, so I have a feeling the f(n/2)+f(n/2-1) is giving it a worse complexity. \$\endgroup\$ Jun 12 at 6:10
  • \$\begingroup\$ Does writing \$ a(n) = a( \lfloor \frac { n - 1 } 2 \rfloor ) + a( \lfloor \frac n 2 \rfloor ) + \lfloor \frac { n + 1 } 2 \rfloor \$ make the code shorter? \$\endgroup\$
    – Neil
    Jun 12 at 9:33
  • \$\begingroup\$ @dingledooper The floating-point arithmetic is causing rounding errors, resulting in linear complexity. it's logarithmic if it sticks to integer arithmetic. (My suggested change also results in linear complexity, unfortunately.) \$\endgroup\$
    – Neil
    Jun 12 at 9:41
  • \$\begingroup\$ (Presumably switching to Python 2 is the golfiest way to achieve integer arithmetic.) \$\endgroup\$
    – Neil
    Jun 12 at 9:45
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.