Count total set bits in all numbers from 1 to n | GeeksforGeeks
http://stackoverflow.com/questions/9812742/finding-the-total-number-of-set-bits-from-1-to-n
http://tech-queries.blogspot.com/2010/12/number-of-set-bits-till-n.html
https://www.quora.com/What-is-the-fastest-way-to-count-the-total-number-of-set-bits-in-an-array-of-a-ten-thousand-16-bit-integers
Read full article from Count total set bits in all numbers from 1 to n | GeeksforGeeks
Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.
The way to solve these sorts of problems is to write out the first few values, and look for a pattern
Number binary # bits set F(n) 1 0001 1 1 2 0010 1 2 3 0011 2 4 4 0100 1 5 5 0101 2 7 6 0110 2 9 7 0111 3 12 8 1000 1 13 9 1001 2 15 10 1010 2 17 11 1011 3 20 12 1100 2 22 13 1101 3 25 14 1110 3 28 15 1111 4 32
It takes a bit of staring at, but with some thought you notice that the binary-representations of the first 8 and the last 8 numbers are exactly the same, except the first 8 have a
0 in the MSB (most significant bit), while the last 8 have a 1. Thus, for example to calculate F(12), we can just take F(7) and add to it the number of set bits in 8, 9, 10, 11 and 12. But that's the same as the number of set-bits in 0, 1, 2, 3, and 4 (ie. F(4)), plus one more for each number!# binary 0 0 000 1 0 001 2 0 010 3 0 011 4 0 100 5 0 101 6 0 110 7 0 111 8 1 000 <--Notice that rightmost-bits repeat themselves 9 1 001 except now we have an extra '1' in every number! 10 1 010 11 1 011 12 1 100
Thus, for
8 <= n <= 15, F(n) = F(7) + F(n-8) + (n-7). Similarly, we could note that for 4 <= n <= 7, F(n) = F(3) + F(n-4) + (n-3); and for 2 <= n <= 3, F(n) = F(1) + F(n-2) + (n-1). In general, if we set a = 2^(floor(log(n))), then F(n) = F(a-1) + F(n-a) + (n-a+1)
This doesn't quite give us an
O(log n) algorithm; however, doing so is easy. If a = 2^x, then note in the table above that for a-1, the first bit is set exactly a/2 times, the second bit is set exactly a/2 times, the third bit... all the way to the x'th bit. Thus, F(a-1) = x*a/2 = x*2^(x-1). In the above equation, this gives usF(n) = x*2x-1 + F(n-2x) + (n-2x+1)
Where
x = floor(log(n)). Each iteration of calculating F will essentially remove the MSB; thus, this is an O(log(n)) algorithm.
For 1 Byte numbers, our pre-computed array will be like:
PRE[8] = {0,1,4,12,32,80,192,448};
It means if N is 0,1,3,7,15,31,63,127 then answer will be 0,1,4,12,32,80,192,448 respectively. Notice that in input N, all possible bits are 1s.
now if N is say 6 (110) then how will I compute my answer?
000, 001, 010, 011, 100, 101, 110
We are seeing that max power of 2 less than 6 is 4. And maximum number with all bits set is 3 (4-1).
Now lets take the HSB(1) out form numbers greater than 3, than it will look like
000, 001, 010, 011, 1#00, 1#01, 1#10
Now we can say that
No_of_bits_till (6) = PRE[2] + (6-3) + No_of_bits_till (6 XOR 4)
No_of_bits_till (6) = PRE[2] + (6-3) + No_of_bits_till (2)
Simply if we see for 53 (110101) then this relationship will be
No_of_bits_till (53) = PRE[5] + (53 - 31) + No_of_bits_till (53 XOR 32)
In this manner we have final recursive relation as
No_of_bits_till (N) = PRE[x] + (N-(2^x -1)) + No_of_bits_till (N XOR 2^x)Where x is max possible power of 2 such that 2^x < N
- int PRE[33] = {0,1,4,12,32,80,192,448,1024,2304,5120,11264};
- int maxpowof2(int n)
- {
- int cnt=0;
- while(n)
- {
- n=n>>1;
- cnt++;
- }
- return 1<<(cnt-1);
- }
- int noof1s(int n)
- {
- if (n == 0)
- return 0;
- int mx_pow_2 = maxpowof2(n);
- int cnt = 0;
- while (1<<cnt != mx_pow_2)
- cnt++;
- return (PRE[cnt] + (n-mx_pow_2+1) + noof1s(n^mx_pow_2));
- }
/* Returns position of leftmost set bit. The rightmost position is considered as 0 */unsigned int getLeftmostBit (int n){ int m = 0; while (n > 1) { n = n >> 1; m++; } return m;}/* Given the position of previous leftmost set bit in n (or an upper bound on leftmost position) returns the new position of leftmost set bit in n */unsigned int getNextLeftmostBit (int n, int m){ unsigned int temp = 1 << m; while (n < temp) { temp = temp >> 1; m--; } return m;}// The main recursive function used by countSetBits()unsigned int _countSetBits(unsigned int n, int m);// Returns count of set bits present in all numbers from 1 to nunsigned int countSetBits(unsigned int n){ // Get the position of leftmost set bit in n. This will be // used as an upper bound for next set bit function int m = getLeftmostBit (n); // Use the position return _countSetBits (n, m);}unsigned int _countSetBits(unsigned int n, int m){ // Base Case: if n is 0, then set bit count is 0 if (n == 0) return 0; /* get position of next leftmost set bit */ m = getNextLeftmostBit(n, m); // If n is of the form 2^x-1, i.e., if n is like 1, 3, 7, 15, 31,.. etc, // then we are done. // Since positions are considered starting from 0, 1 is added to m if (n == ((unsigned int)1<<(m+1))-1) return (unsigned int)(m+1)*(1<<m); // update n for next recursive call n = n - (1<<m); return (n+1) + countSetBits(n) + m*(1<<(m-1));}
Time Complexity: O(nLogn)
// Returns count of set bits present in all numbers from 1 to nunsigned int countSetBits(unsigned int n){ int bitCount = 0; // initialize the result for(int i = 1; i <= n; i++) bitCount += countSetBitsUtil(i); return bitCount;}// A utility function to count set bits in a number xunsigned int countSetBitsUtil(unsigned int x){ if (x <= 0) return 0; return (x %2 == 0? 0: 1) + countSetBitsUtil (x/2);}https://www.quora.com/What-is-the-fastest-way-to-count-the-total-number-of-set-bits-in-an-array-of-a-ten-thousand-16-bit-integers
Read full article from Count total set bits in all numbers from 1 to n | GeeksforGeeks
