# HitBit Editorial

Author : Atul Mishra

Tester : Abhinesh Garhwal

Editorialist : Atul Mishra

Difficulty :
Cakewalk

Prerequisites :
Bit Manipulation

Problem :
Sum of all the numbers from range(l,r) whose kth bit is set.

Quick Explanation :
Check the kth bit and add.

Explanation:
The problem can be solved by multiple ways :

Method 1:

Given a range(1,10), convert each number into its binary equivalent and check the kth bit. one can convert a number directly to its binary representation through using bitset.

Code :

``````    #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll l,r,k;
scanf("%lld %lld %lld",&l,&r,&k);
ll sum=0;
for (int i = l;i<=r; i++)
{
bitset<32> arr(i);
if(arr[k-1]==1)
sum=sum+i;

}

printf("%lld\n",sum);
}

}
``````

Method 2:

``````#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){

int tc;
scanf("%d",&tc);
while(tc--)
{
ll l,r;
int k;
scanf("%lld %lld %d",&l,&r,&k);
k--;
ll j = 1<<k; //shift k bit left j
ll sum=0;
for(ll i=l;i<=r;i++)
{
ll res = i & j; //i AND j
if(res==j)
{
sum+=i;
}
}
printf("%lld\n",sum);
}

return 0;
``````

}

I donâ€™t think O(n) approach can pass the test case where the constraints are 1 < l,r < 10e9??Right?

Yes, it do passes the test cases

//