Bitwise AND ( 비트연산 java )

hackerrank 튜토리얼 문제입니다.

 

1부터 주어진 정수 N까지 ( S = {1, 2, 3, 4, ..., N }  )의 비트연산을 수행하고

가장 큰 결과를 반환 하십시오.

단 반환된 결과는 주어진 정수 K보다 낮아야 합니다.

 

 

[ 제약조건 ]

• 1 <= T <= 10^3
• 2 <= N <= 10^3
• 2 <= K <= N

입력 예시

N = 5, K = 2
N = 8, K = 5
N = 2, K = 2

 

출력 예시

1
4
2

 

해설

 

N = 5, K = 2 S = {1, 2, 3, 4, 5}

1. A = 1, B = 2; A & B = 0
2. A = 1, B = 3; A & B = 1
3. A = 1, B = 4; A & B = 0
4. A = 1, B = 5; A & B = 1
5. A = 2, B = 3; A & B = 2
6. A = 2, B = 4; A & B = 0
7. A = 2, B = 5; A & B = 0
8. A = 3, B = 4; A & B = 0
9. A = 3, B = 5; A & B = 1
10. A = 4, B = 5; A & B = 4

• 1부터 주어진 정수 N( 5 ) 까지의 가능한 모든 경우의 수를 비트연산합니다.
• 위의 예시 중 가장 큰수는 4 & 5 = 4 가 됩니다.
• 하지만 주어진 정수 K( 2 ) 보다 낮아야 하므로, 4가 될 수 없으며, 마찬가지로 2도 될 수 없습니다.
• 따라서 정답은 1입니다.

 

여러분들도 해설만으로 풀 수 있다면 한번 풀어보시기 바랍니다.

 

 

 

 

 

N = 5, K = 2
N = 8, K = 5
N = 2, K = 2

1. 매개 변수 3쌍을 넘겨주기 위해서, 정수 배열 2개를 선언합니다.
2. 정수 N과 K를 계산하여, 비트연산으로 수행하는 메소드를 선언합니다.
3. 반복문을 bitwiseAnd(int N, int K) 메소드를 호출하고, 결과를 출력합니다. 

public static int bitwiseAnd(int N, int K) {
    return 0;
}

public static void main(String[] args) {
    int[] counts = { 5, 8, 2 };
    int[] lims = { 2, 5, 2 };
    for (int i = 0; i < 3; i++) {
        int bitwise = bitwiseAnd(counts[i], lims[i]);
        System.out.println("BitwiseAND => " + bitwise + "\n");
    }
}

 

 

1. 정수 N ( 5 ) => {1 ~ N} => { 1, 2, 3, 4, 5 }
   따라서 외부 반복문의 조건식은 (int i = 1; i <= 5; i++) 입니다.
2. 중복연산을 하지 않기 위해, 내부 반복문의 조건식 j 의 값은 i + 1로 초기화 합니다.

public static int bitwiseAnd(int N, int K) {
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
        
        }
    }
    return 0;
}

 

i 와 j 를 사용하여 비트연산을 수행합니다.

public static int bitwiseAnd(int N, int K) {
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            int bitwise = i & j;
            // System.out.println("A=" + i + ",B=" + j + "; A&B=" + bitwise );
        }
    }
}

 

 

1. 비트연산 수행 결과중에 최대 값이면서, 매개변수 K보다 작은 값을 반환해야하므로
   매 비트연산결과와 최대값을 비교 하고 저장하기 위한 지역변수 max를 선언합니다.
2. if (bitwise > max) 매 비트연산 결과와 최대값을 비교 후 저장합니다.
       max = bitwise;
3. if (bitwise > max && bitwise < K) 매개변수 K보다 작아야하므로 조건을 추가합니다.

public static int bitwiseAnd(int N, int K) {
    int max = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            int bitwise = i & j;
            // System.out.println("A=" + i + ",B=" + j + "; A&B=" + bitwise );
            
            if (bitwise > max && bitwise < K)
                max = bitwise;
        }
    }
    return max;
}

 

 

[ Github URL ]

https://github.com/oracle8427/algorithm/blob/main/src/main/java/study/hacker_rank/BitwiseAND.java

oracle8427/algorithm