### 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

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"); } }