[2019.01.23] Bitwise AND

Problem

Objective 
Welcome to the last day! Today, we're discussing bitwise operations. Check out the Tutorial tab for learning materials and an instructional video!

Task 
Given set . Find two integers,  and  (where ), from set  such that the value of  is the maximum possible and also less than a given integer, . In this case,  represents the bitwise AND operator.

Input Format

The first line contains an integer, , the number of test cases. 
Each of the  subsequent lines defines a test case as  space-separated integers,  and , respectively.

Constraints

Output Format

For each test case, print the maximum possible value of  on a new line.

Sample Input

3
5 2
8 5
2 2

Sample Output

1
4
0

Explanation

 

All possible values of  and  are:

The maximum possible value of  that is also  is , so we print  on a new line.

How I solved the problem

# 너무 어려운 비트 연산자..........

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*;   public class Solution {           private static final Scanner scanner = new Scanner(System.in);       public static void main(String[] args) {         int t = scanner.nextInt();         scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");           for (int tItr = 0; tItr < t; tItr++) {             String[] nk = scanner.nextLine().split(" ");               int n = Integer.parseInt(nk[0]);               int k = Integer.parseInt(nk[1]);               if (((k-1) | k) > n && (k%2 == 0)) {                 System.out.println(k - 2);             } else {                 System.out.println(k - 1);             }         }           scanner.close();     } }   Colored by Color Scripter

cs

# Discussion에 있던 자세한 설명을 첨부함.. 한 번 더 봐야겠다..!

I’ll try to explain this to my understanding and capacity.

S – Set of numbers from 1 to N [Eg: 1,2,3…N]

N – The last number in the set

K – Threshold number [i.e limit for the answer to be obtained] and this value can be K <= N

Since our answer should be < K, the possible answer would be <= K-1.

We know that while doing an AND operation between 2 numbers, the answer would be <= LOWEST NUMBER of those 2 numbers. And we need to find this LOWEST NUMBER which is <= K-1

So we need to find an AND pair which would result with our required answer.

STEP 1: Since K-1 is the highest possible answer, we will take it as one of the 2 numbers. The other number should be > K-1 due to the AND property and it would be >= K. It’s best to take a number whose binary equivalent is similar to K-1’s binary value. So K would be the best choice.

Note: By doing an OR operation between 2 numbers, the answer would be >= HIGHEST NUMBER of the 2 numbers.

STEP 2: To find the other number we perform OR operation between the highest possible answer and the immediate larger number to it.

i.e [(K-1) OR (K-1)+1] which is nothing but [(K-1) OR K] and its result would be >= K.

STEP 3: Now we got the AND pair which are K-1 and K (minimum possible result of the above OR operation) and our AND result would be <= K-1.

For most cases we will get the final answer as K-1 itself but not for all cases.

a) When K is odd, the final answer will definitely be K-1 because if K is odd, K-1 will be even. Here only the LSB of the binary equivalent will be different. Eg: K=5(0101) ; K-1=4(0100)

b) When K is even, K-1 will be odd and both number's binary values might not be similar. Eg: K=8(1000) ; K-1=7(0111)

c) K-1 will be the answer only when the result of OR operation is <= N. If its > N, we would end up using a number which is not in the given number set for the AND operation which might result in a wrong final answer.

So these cases occur when {(K-1 OR K) > N} and when K is even.

For these scenarios, the highest possible answer would not be K-1 and it'll be the next lesser number K-2. The AND pairs for such scenarios would be K-2 and K-1 resulting with a final answer K-2.

For the above cases, K-1 cannot be the highest possible answer so we take next the lesser number K-2 as the highest possible answer and we start again from STEP 1 replacing K-1 with K-2 and K with K-1.

1.N=5, K=2 ; K-1 = 1

0010	2(K)
0001	1(K-1)
-----OR----
0011	3(OR result)

3 < N 

0011	3(OR result)
0001	1(K-1)
-----AND----
0001	1(final answer)



2.N=8, K=5 ; K-1 = 4

0101	5(K)
0100	4(K-1)
-----OR----
0101	5(OR result)

5 < N 

0101	5(OR result)
0100	4(K-1)
-----AND----
0100	4(final answer)


 
3.N=2, K=2 ; K-1 = 1 ; K-2 = 0

0010	2(K)
0001	1(K-1)
-----OR----
0011	3(OR result)

3 > N 

0001	1(K-1)
0000	0(K-2)
-----OR----
0001	1(OR result)

0001	1(OR result)
0000	0(K-2)
-----AND----
0000	0(final answer)



4.N=21, K=20 ; K-1 = 19 ; K-2 = 18

10100	20(K)
10011	19(K-1)
-----OR----
10111	23(OR result)

23 > N 

10011	19(K-1)
10010	18(K-2)
-----OR----
10011	19(OR result)

10011	19(OR result)
10010	18(K-2)
-----AND----
10010	18(final answer)

[출처 : https://www.hackerrank.com ]