Introduction:
Welcome to the last day of the 30 Days of Code challenge! Today's task involves bitwise operations. Bitwise operations are fundamental in computer science and involve manipulating individual bits of binary numbers. Let's dive into the final challenge!
The Challenge:
Given a set {1, 2, ..., N}, find two integers, A and B (where A < B), from the set such that the value of A&B is the maximum possible and also less than a given integer, K. Here, & represents the bitwise AND operator.
Constraints:
1 ≤ T ≤ 10^3 (number of test cases)
2 ≤ N ≤ 10^3 (maximum integer to consider)
2 ≤ K ≤ N (limit of the result, inclusive)
Format & Sample:
Input Format:
The first line contains an integer, T, the number of test cases.
Each of the subsequent T lines defines a test case as two space-separated integers, N and K, respectively.
Input Format:
3
5 2
8 5
2 2
Output Format:
1
4
0
Explanation:
All possible values of A and B are:
For the first test case (N=5, K=2):
A=1, B=2, A&B=0
A=1, B=3, A&B=1
A=1, B=4, A&B=0
A=1, B=5, A&B=1
A=2, B=3, A&B=2
...
The maximum possible value of A&B that is also less than or equal to K is 1.
Code Breakdown:
Read the number of test cases, T, from input.
Loop over each test case and read the values of N and K.
Implement the bitwiseAnd function to find the maximum value of A&B within the limit.
Print the result for each test case.
Reading Input:
int main() {
int T;
cin >> T; // Read the number of test cases
for (int t_itr = 0; t_itr < T; t_itr++) {
int N, K;
cin >> N >> K; // Read N and K for each test case
Printing Output:
// Call the bitwiseAnd function and print the result
int res = bitwiseAnd(N, K);
cout << res << "\n";
}
return 0;
}
Final Code:
#include <bits/stdc++.h>
using namespace std;
int bitwiseAnd(int N, int K) {
if (((K - 1) | K) <= N) {
return K - 1;
} else {
return K - 2;
}
}
int main() {
int T;
cin >> T; // Read the number of test cases
for (int t_itr = 0; t_itr < T; t_itr++) {
int N, K;
cin >> N >> K; // Read N and K for each test case
// Call the bitwiseAnd function and print the result
int res = bitwiseAnd(N, K);
cout << res << "\n";
}
return 0;
}
This completes the final day of the 30 Days of Code challenge. Congratulations on completing the challenge! Bitwise operations are essential in low-level programming and algorithmic optimizations. Great job!