can anyone help me to crack any formula or code rather than O(n) to count the sum of number of set bits in upto Nth
N Bit
Ex: 1 -> 1
2 -> 1 + 1 (this 1 is previous one as we are summing those)
3 -> 4
4 -> 5
5 -> 7
|
|
Nth term formula???
I tried to crack the pattern like:
for first bit 2^0: 1 and 0 makes pattern of 01010101---------Nth
for second bit 2^1: 1 and 0 makes pattern of 00110011---------Nth
for third bit 2^2: 1 and 0 makes pattern of 00001111---------Nth
Let's look for dependencies. Results for 0001111** (k ones) patterns are k*2^(k-1), so result for patterns containing the only one "1" (2^k) is 1 + k*2^(k-1). So we can separate the most significant one bit (MSB), get count for numbers upto corresponding power of two, then add both count for right tail value and that right tail value itself (because of MSB). Python code:
def cnt_ones(n):
if n==0: return 0
leftbit = 1
bitnum = 0
cnt = 0
while leftbit*2 <= n: #find power of two for MSB
leftbit <<= 1
bitnum += 1
while leftbit: #now check bits from left to right
if n & leftbit:
cnt += 1 + (leftbit//2) * bitnum + (n & (leftbit - 1))
# MSB bit itself
#count for numbers before this power of two
# tail value
leftbit >>= 1
bitnum -= 1
return cnt
0 0
1 1
2 2
3 4
4 5
5 7
6 9
7 12 #3*2^2
8 13 #1+3*2^2
9 15
10 17
11 20
12 22
13 25
14 28 # 1 + 3*2^2 + (14-8) + count(14-8)
15 32
16 33
17 35
18 37
...
30 75
31 80
32 81
33 83
Addition:
Why numbers upto k ones give k*2^(k-1) bits:
Consider k-bits values from 0000 to 1111. There are 2^k of them. Every bit is "0" in the half of values, and is "1", so we can count 2^(k-1) ones for every bit number, and multiply by k for all k bits.
Why check bits from left to right?
If we have binary value 1110, we can count ones for values in range 0000...1000 as above, then add count of ones in range 1001..1110. The last range contains 110b=6dec values, so we have to account for 6 one bits at the left, and count ones in 001..110 range and so on.