Count ones in a segment

• Time : $O(log(right) + log(left))$
• Space : $O(1)$

long long dp(long long x) {
    if(x == 0) return 1;
    return dp(x-1) * 2 + (1ll<<x);
}
long long helper(long long x, long long bit, long long cnt, bool lo) {
    if(bit == -1) return cnt;
    if(lo) return cnt * (1ll<<(bit + 1)) + dp(bit);
    if(x & (1ll<<bit)) return helper(x, bit - 1, cnt, true) + helper(x, bit - 1, cnt + 1, false);
    return helper(x, bit - 1, cnt, false);
}
long long countOnes ( int left, int right )
{
    return helper(right, 32, 0, 0) - helper(left-1, 32, 0, 0);
}