BinarySearch - 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;
}