BIT2-Search Bit Sum

Search Bit Sum

below given code is for bit2 spoj or Search Bit Sum spoj

in the below given code __lg() gives the last bit position of number eg: 7- 111 so last bit position is 2 starting from zero .

and 1LLU << i it means that we are shifting 1 to left by i and then converting it to unsigned long long .

and while loop in main function is actually binary search prototype for searching the number k;
In function totalbit formula for calculating total bit sum i got it from here

this was asked in amazon interview .

#include <stdio.h>
#include <iostream>
using namespace std;
unsigned long long totalbit(unsigned long long n){
    unsigned long long ans = 0;
    int x = 0;
    for(int i = __lg(n); i >= 0; --i)
        if(n & 1LLU << i)
            ans += ((1LLU << i) >> 1) * i + 1 + (1LLU << i) * x++;
    return ans;
}

int main(){
    int t;
    unsigned long long n, l, u, m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%llu",&n);
        l = 0; 
        u = n + 1;
        while(l != u)
        {
            m = (l + u ) / 2;
            if(totalbit(m) >= n) u = m;
            else l = m + 1;
        }
        if(totalbit(l) == n) 
            printf("%llu\n",l);
        else 
            printf("Does Not Exist.\n");
    }
}