Problem Link :
Contest : https://www.codechef.com/CYPH2016/problems/HITBIT
Practice : https://www.codechef.com/problems/HITBIT
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;
}