BinarySearch - Set Bits

[https://binarysearch.com/problems/Set-Bits](https://binarysearch.com/problems/Set-Bits) ## Problem Given an integer n, return the total number of set bits in all integers between 1 and n inclusive. Constraints $ n ≤ 2 ^ {27} $ ## Solution The i-th least significant bit can be calculate as $$ (\frac{n}{2 ^ i}) * 2 ^{i - 1} + n \bmod 2 ^ {i} - (2 ^ {i - 1} - 1) $$ if and only if $$ n \bmod ( 2 ^ {i} ) >= (2 ^ {i - 1} - 1) $$ ``` int solve(int n) { int two = 2, ans = 0; int tmp = n; while (tmp) { ans += (n / two) * (two >> 1); if ((n & (two - 1)) > (two >> 1) - 1) ans += (n & (two - 1)) - (two >> 1) + 1; two <<= 1, tmp >>= 1; } return ans; } ```