Added a new section to bit-manipulation.md

ganeshvarbalaji · web-flow · commit 65a6065bba8d · 2024-06-13T12:38:04.000+05:30
Added a new section "Count set bits upto n" under the Useful Tricks section after the Brian Kernighan's algorithm. The Brian Kernighan's algorithm explains how to count the set bits of an integer n. The new added section explains how to count the set bits of all integers from 1 upto the number n, without giving a TLE during contest submissions. The Solution was inspired by the following problem on geeksforgeeks: https://www.geeksforgeeks.org/problems/count-total-set-bits-1587115620/1
diff --git a/src/algebra/bit-manipulation.md b/src/algebra/bit-manipulation.md
@@ -186,6 +186,59 @@ int countSetBits(int n)
 }
 ```
 
+### Count set bits upto $n$
+To count the number of set bits of all numbers upto the number $n$ (inclusive), we can run the Brian Kernighan's algorithm on all numbers upto $n$. But this will result in a "Time Limit Exceeded" in contest submissions. 
+
+We can use the fact that for numbers upto $2^x$ (i.e. from $1$ to $2^x - 1$) there are $x*2^{x-1}$ set bits. This can be visualised as follows.
+```
+0 ->   0 0 0 0
+1 ->   0 0 0 1
+2 ->   0 0 1 0
+3 ->   0 0 1 1
+4 ->   0 1 0 0
+5 ->   0 1 0 1
+6 ->   0 1 1 0
+7 ->   0 1 1 1
+8 ->   1 0 0 0
+```
+
+We can see that the all the columns except the leftmost have $4$ (i.e. $2^2$) set bits each, i.e. upto the number $2^3 - 1$, the number of set bits is $3*(2^{3-1})$.
+
+With the new knowledge in hand we can come up with the following algorithm:
+- Find the highest power of $2$ that is lesser than or equal to the given number. Let this number be $x$.
+- Calculate the number of set bits from $1$ to $2^x - 1$ by using the formua $x*(2^{x-1})$.
+
+The next steps needs more explanation.
+- Count the no. of set bits in the most significant bit from $2^x$ to $n$ and add it.
+- Subtract $2^x$ from $n$ and Recurse with the algorithm using the new $n$.
+
+```cpp
+int countSetBits(int n){
+	if(n <= 0) return 0;
+	
+	int count = 0;
+	
+	// Find the highest power of 2 that is
+	// less than or equal to the given n.
+	int x = 0;
+	while ((1 << x) <= n) x++;
+	x--;
+	
+	// Count set bits of all the numbers
+	// from 1 to 2^x - 1
+	count = x * (1 << (x - 1));
+	
+	// Count set bits in the most significant
+	// bit of the numbers from 2^x to n.
+	count += (n - (1 << x) + 1);
+	
+	// Recurse for remaining numbers from 2^x to n
+	count += countSetBits(n - (1 << x));
+	
+	return count;
+}
+```
+
 ### Additional tricks
 
 - $n ~\&~ (n + 1)$ clears all trailing ones: $0011~0111_2 \rightarrow 0011~0000_2$.
