Sum of indices of second least significant bit

Question

This is a pure code-golf question.

Input: A non-negative integer n

Output: Sum of the indices of the second least significant set bit in the binary representation of the integers 0...n. If the number doesn't have two set bits then the contribution to the sum should be zero.

Your code should be runnable on a standard linux machine using free software and shouldn't take more than n+1 seconds to run.

Sample answers for n from 0..20

0 0 0 1 1 3 5 6 6 9 12 13 16 18 20 21 21 25 29 30

Here is some sample ungolfed python code.

def get_2nd_least_bit(x):
    sum = 0
    for i in range(0,x.bit_length()):
        sum += (x >> i) & 1
        if sum == 2 :
            return i 
    return 0
for x in xrange(20):
    print sum(get_2nd_least_bit(i) for i in xrange(x+1)),

Answer 1

k [21 chars]

{+/{(&|0b\:x)1}'!x+1}

Example

{+/{(&|0b\:x)1}'!x+1}[3]
1

{+/{(&|0b\:x)1}'!x+1}[7]
6

{+/{(&|0b\:x)1}'!x+1}[10]
12

{+/{(&|0b\:x)1}'!x+1}[500]
1410

Answer 2

GolfScript (31 chars)

,{)2base-1%.,,\`{=}+,1=}%0+{+}*

This takes input on the stack and leaves output on the stack. Online demo which wraps it in a loop to output the first 12 values.

That implementation does the obvious thing of computing the base-2 representation of the integers in range. A more interesting approach, which sadly I haven't been able to golf as far, is to analyse the sequence. It's a sum of indices: let i2(n) be the index of the second LSB of n. We have i2(2^x) = 0 (given as a special case). What can we say about the values which i2 takes between 2^x and 2^(x+1)?

• Case 1: 2^x < k < 2^x + 2^(x-1). Then k ^ (2^x + 2^(x-1)) = k - 2^(x-1). If i2(k - 2^(x-1)) < x-1 then i2(k) = i2(k - 2^(x-1)); otherwise i2(k) = x = 1 + i2(k - 2^(x-1)).
• Case 2: k = 2^x + 2^(x-1). Obviously i2(k) = x since there are two bits set.
• Case 3: 2^x + 2^(x-1) < k < 2^(x+1) has bit x-1 set and at least one less significant bit set, so i2(k) = i2(k - 2^x).

In other words: the sequence of indices between consecutive powers of two can be found by splicing together three sequences: the previous sequence under the substitution s/x-1/x/; the sequence [x]; and the previous sequence unmodified.

• []
• [] + [1] + [] = [1]
• [2] + [2] + [1] = [2 2 1]
• [3 3 1] + [3] + [2 2 1] = [3 3 1 3 2 2 1]
• [4 4 1 4 2 2 1] + [4] + [3 3 1 3 2 2 1] = [4 4 1 4 2 2 1 4 3 3 1 3 2 2 1]
• etc.

This leads to (40 chars)

([]{,2$<}{..0+0=:x+{.x=+}%\+}/1,*<0+{+}*

(Note for GS aficionados: a rare use for unfold!)

Answer 3

J (and mathematics), way too much (aka. 45 chars), cubic memory and terrible runtime

+/,(*v>(2&^*1+a*2:)+/2^i.)"0]a=.i.v=.".1!:1]1

If I wanted to aim for length, I could of course do it the obvious, straightforward way and get something considerably shorter... however, I found it more interesting to investigate the properties of "index of second least significant set bit".

The J program above is an instance of the formula derived below. The idea is to build a huge table of numbers per bit index, then filter out those below the number we seek, then multiply by the bit index, then sum it all up.

---

So, I started with the slightly different case "index of the least significant set bit" (LSSB), because it's always best to start simple when looking for patterns... I plotted the index of the LSSB for numbers [0..40]:

          1111111111222222222233333333334
01234567890123456789012345678901234567890
-0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0   =  2k + 1
  1   1   1   1   1   1   1   1   1   1    =  4k + 2
    2       2       2       2       2      =  8k + 4
        3               3               3  = 16k + 8
                4
                                5

(Here, - means N/A.) Well, that's a very obvious pattern. Joining the cases together we get 2^v * (2k + 1) for row v, for integers k (or, 2^v * m for odd m, if you prefer). This is sequence A007814 in OEIS.

Okay, so, back to our real case of the second least significant set bit (2LSSB). Let's do a similar plot for this case and see if there's any pattern here too, and if so, how it relates to the previous pattern.

          1111111111222222222233333333334
01234567890123456789012345678901234567890
--- -   -       -               -
   1   1   1   1   1   1   1   1   1   1
     22      22      22      22      22
         33 3            33 3
                 44 4   4
                                 55 5   5

Well... huh. That looks a bit strange, but there's still some sort of repetition going on. Let's take a look at what numbers get assigned which indices.

0: 0 1 2 4 8 16 32             ...  2^k
1: 3 7 11 15 19 23 27 31 35 39 ...  4k +  2 + {1}           =  2*(2k + 1) + 2^{0}
2: 5 6 13 14 21 22 29 30 37 38 ...  8k +  4 + {1,2}         =  4*(2k + 1) + 2^{0,1}
3: 9 10 12 25 26 28            ... 16k +  8 + {1,2,4}       =  8*(2k + 1) + 2^{0,1,2}
4: 17 18 20 24                 ..? 32k + 16 + {1,2,4,8}     = 16*(2k + 1) + 2^{0,1,2,3}
5: 33 34 36 40                 ..? 64k + 32 + {1,2,4,8,16}  = 32*(2k + 1) + 2^{0,1,2,3,4}

Okay, yeah, definitely a pattern. The general case here is 2^v * (2k + 1) + 2^j, j < v. While we're at it, let's do one more just to see how this all generalises for the n:th least significant set bit.

                                                                                                    111111111111111111111111111111
          111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999000000000011111111112222222222
0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789
 01 012 4       012 4   8      16                               012 4   8      16              32   ...
  012   012 4   8               012 4   8      16              32                                   ...
------- --- -   --- -   -       --- -   -       -               --- -   -       -               -                                       =   2^k + 2^l, l < k                                 0
                                                                                                                                                                                             1
       2       2       2       2       2       2       2       2       2       2       2       2       2       2       2       2        =   8*k +  4 + {3}                                   2
           3 33            3 33            3 33            3 33            3 33            3 33            3 33            3 33         =  16*k +  8 + {3,5,6}                               3
                   4 44  44 4                      4 44  44 4                      4 44  44 4                      4 44  44 4           =  32*k + 16 + {3,5,6,9,10,12}                       4
                                   5 55  55 5    55 5   5                                          5 55  55 5    55 5   5               =  64*k + 32 + {3,5,6,9,10,12,17,18,20,24}           5
                                                                   6 66  66 6    66 6   6        66 6   6       6                       = 128*k + 64 + {3,5,6,9,10,12,17,18,20,24,...}       6

Phew. 40 digits didn't cut it for finding patterns here, so I had to extend it a bit. Sorry about that horizontal scrollbar. Here's the table to the far right again, to spare you from having to scroll back and forth.

   2^k + 2^l, l < k                                 0
                                                    1
   8*k +  4 + {3}                                   2
  16*k +  8 + {3,5,6}                               3
  32*k + 16 + {3,5,6,9,10,12}                       4
  64*k + 32 + {3,5,6,9,10,12,17,18,20,24}           5
 128*k + 64 + {3,5,6,9,10,12,17,18,20,24,...}       6

Huh. That's weird, what are those numbers? They're certainly not powers of two... maybe I should've been able to guess it from the earlier two tables, but instead I went to OEIS and found it's actually the set of sums of two distinct powers of two. So it seems like a qualified guess to generalise this by taking the sum of n distinct powers of two for the index of the n:th least significant set bit. All in all, the final expression looks like so:

Answer 4

Ruby, 64

Here's a regex-based solution. I hope it's correct, the spec could use some test cases...

p (0..gets.to_i).inject{|s,n|n.to_s(2)=~/10*10*$/?s+$&.size-1:s}

Examples:

>echo 3 | ruby sum-of-indices.rb
1
>echo 7 | ruby sum-of-indices.rb
6
>echo 10 | ruby sum-of-indices.rb
12
>echo 500 | ruby sum-of-indices.rb
1410

Answer 5

Postscript, 179

Not to compete in golf, just for fun. I like it, that 1's indexes (which are post-match lengths in a string scanned left to right starting with most significant bits) are accumulated on stack and so to find second least significant, one operand is popped, next added to sum, the rest are discarded (stack cleared).

/s 0 def 0 1(%stdin)(r)file token pop {2 32 string cvrs mark exch {(1)search{pop pop dup}{pop exit}ifelse}loop counttomark 2 ge{pop length s add/s exch def}if cleartomark}for s =

Un-golfed, and with timer attached:

/s 0 def 
0 1 
(%stdin) (r) file
token pop
realtime 4 1 roll
{
    2 32 string cvrs
    mark exch
    {
        (1) search
        {pop pop dup}{pop exit}ifelse
    } loop
    counttomark 2 ge {pop length s add /s exch def} if
    cleartomark
} for 
s =
realtime
(Time elapsed, s: )=
exch sub 1000 div =

And:

echo 10 | gs -q -dBATCH sum.ps
12
Time elapsed, s:
0.0

echo 500 | gs -q -dBATCH sum.ps
1410
Time elapsed, s:
0.0

echo 1000000 | gs -q -dBATCH sum.ps
2999655
Time elapsed, s:
3.218

Answer 6

Smalltalk (Smalltalk/X) (105 chars)

(0 to:20) 
    injectAndCollect:0 
    into:[:sumSoFar :n | 
            sumSoFar + 
            (([(n clearBit:n lowBit) lowBit] ifError:0) - 1 max:0)
         ]

-> 0 0 0 1 1 3 5 6 6 9 12 13 16 18 20 21 21 25 29 30 34

injectAndCollect:into: is not part of Ansi Smalltalk, though.

Answer 7

JavaScript, 69 68

for(s=k=prompt(r=0);k--;r=k&k+1)for(s-=!r;r*!(r&2);r/=2)s++;alert(s)

The approach is to strip the lowest bit (the result is stored in r) then count the trailing zeroes.

Longer alternate, 79 chars

for(k=prompt(s=0);k--;s+=/.(0*)$/.exec((k&k+1).toString(2))[1].length);alert(s)

The takes the r from above, converts it to a binary string, and uses a regular expression to count the trailing zeroes. I include it because I like the idea of doing the counting with string processing.

Answer 8

32-bit x86 assembly code, 22 bytes

Accepts input in ecx register, output is in eax register.

00000000 33 c0    xor   eax, eax
00000002 e3 11    jecxz 00000015
00000004 51       push  ecx
00000005 0f bc d1 bsf   edx, ecx
00000008 0f b3 d1 btr   ecx, edx
0000000B 0f bc d1 bsf   edx, ecx
0000000E 74 02    je    00000012
00000010 03 c2    add   eax, edx
00000012 59       pop   ecx
00000013 e2 ef    loop  00000004
00000015 c3       ret