[HackerRank][Python] Day 29 : Bitwise AND

어려운 문제는 아니지만 내가 보통 푸는 방법과 다르게 풀어서 정리해두려고 한다.

문제

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.

Function Description
Complete the bitwiseAnd function in the editor below.

bitwiseAnd has the following paramter(s):
- int N: the maximum integer to consider
- int K: the limit of the result, inclusive

Returns
- int: the maximum value of  within the limit.

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

•  
•  
•  

Sample Input

STDIN   Function
-----   --------
3       T = 3
5 2     N = 5, K = 2
8 5     N = 8, K = 5
2 2     N = 8, K = 5

Sample Output

1
4
0

 

풀이

bitwiseAnd 함수는 (N,K)를 입력으로 받아 [1,2,3 ... ,N-1, N]의 배열중에서 두개를 뽑아 bitwise AND 연산을 하는데, 그중 K보다 작으면서 제일 큰 값을 리턴해야하는 함수이다.

처음의 아이디어는 이중 포문을 돌면서 각각의 element끼리 & 연산을 하고 배열에 저장하여 K보다 작으면서 제일 큰 값을 출력하도록 하였다. 하지만 이는 시간초과를 발생하였고, 

bitwise and의 특징을 생각해보다보니, K보다 작은 값(i라고 하자)의 비트를 유지하면서 ( 10이라고 하면 1010 즉 2,4번째 1을 유지하는 것) N보다 작은 값이 존재한다면 i를 리턴해주면 된다.

예시1) 10(1010) & 11(1011) -> 1010 리턴

예시2) 10 (1010) & 26 (11010) -> 1010 리턴 

2,4번째 비트를 1로 유지하면서 다른 0인 비트를 바꾸어보면 된다. 

def bitwiseAnd(N, K):
    # Write your code here
    for i in range(K-1,-1,-1):
        num = i
        num2 = 1
        while(num2 <= N):
            if (num & num2)==0 and (num+num2 <= N):
                return i
            num2 = num2 *2
    return 0;