[2019.01.23] Bitwise AND

1 Day 1 Algorithms

[2019.01.23] Bitwise AND

곰돌찌 2019. 1. 23. 09:06

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

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

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

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

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

저작자표시