[C언어 연습문제]강좌 8. Bitwise Operators(과제를 통한 비트 연산자의 활용)

학습(Study) & 목표(Objective)

C에서 비트 연산자를 사용하는 문제를 풀어보려고 합니다. CPU 내부에는 사칙연산(덧셈, 뺄셈, 곱셈, 나눗셈)이 비트 수준에서 수행됩니다. C 프로그래밍에서 비트 수준의 연산을 수행하려면, 비트 연산자를 사용해야 합니다.

• AND 비트 연산자는 & 입니다. 해당하는 2개의 피연산자가 모두 1이면, 1을 반환합니다. 피연산자 중 하나라도 0이면, 0을 반환합니다.

• OR 비트 연산자는 | 입니다. 해당하는 2개의 피연산자가 하나라도 1이면, 1을 반환합니다. 
  

• XOR 비트 연산자는 ^ 입니다. 두 피연산자의 해당 비트가 반대이면, 1을 반환합니다.

예를 들어 int형 정수 3과 5가 있으면, 아래처럼 되겠죠.

3 = 00000011 (In Binary, 2진수)

5 = 00000101 (In Binary, 2진수)

AND 연산

00000011

00000101 (&)

------------

00000001 = 1

OR 연산

00000011

00000101 (|)

------------

00000111 = 7

XOR 연산

00000011

00000101 (^)

------------

00000110 = 6

과제(Task)

주어진 집합 S = { 1, 2, 3, 4, ... , n }에서 다음 값을 찾습니다.

• a&b의 최댓값은 int형 정수 k보다 작습니다. (a < b) a, b는 집합 S의 원소입니다.
• a|b의 최댓값은 int형 정수 k보다 작습니다. (a < b) a, b는 집합 S의 원소입니다.
• a^b의 최댓값은 int형 정수 k보다 작습니다. (a < b) a, b는 집합 S의 원소입니다.

1. 두 개의 정수를 입력받는다.

2. 첫 번째 정수는 n을 입력받는다.

3. 두 번째 정수는 k를 입력받는다.

4. 집합 S = { 1, 2, 3, 4, ... , n}에서 k보다 작은 a&b, a|b, a^b의 값을 구하라.

자세한 내용은 아래 출력 예제를 참고해보세요.

입력 형식(Input Format)

한 줄에 공백으로 구분하여 2개의 정수를 입력받습니다.

입력받은 원소는 int형 변수 n과 k입니다.

제약 조건(Constraints)

출력 형식(Output Format)

• 첫 줄에는 a&b가 가능한 값 중 최댓값을 출력합니다.
• 두 번째 줄에는 a|b가 가능한 값 중 최댓값을 출력합니다.
• 세 번째 줄에는 a^b가 가능한 값 중 최댓값을 출력합니다.

입력 예제(Sample Input)

5 4

출력 예제(Sample Output)

2

3

3

설명

n = 5, k = 4 일 때,

S = {1, 2, 3, 4, 5} 입니다.

가능한 경우의 수를 나열하면 아래와 같습니다.

1. a = 1, b = 2, a & b = 0; a | b = 3; a ^ b = 3;

2. a = 1, b = 3; a & b = 1; a | b = 3; a ^ b = 2;

3. a = 1, b = 4; a & b = 0; a | b = 5; a ^ b = 5;

4. a = 1, b = 5; a & b = 1; a | b = 3; a ^ b = 4;

5. a = 2, b = 3; a & b = 2; a | b = 3; a ^ b = 6;

6. a = 2, b = 4; a & b = 0; a | b = 6; a ^ b = 6;

7. a = 2, b = 5; a & b = 0; a | b = 7; a ^ b = 7;

8. a = 3, b = 4; a & b = 0; a | b = 7; a ^ b = 7;

9. a = 3, b = 5; a & b = 1; a | b = 7; a ^ b = 6;

10. a = 4, b = 5; a & b = 4; a | b = 5; a ^ b = 1;

위의 제약조건에 따라 k는 4보다 같거나 작아야 합니다.

a&b의 최댓값은 5번째인 2이네요.

a|b의 최댓값은 7이지만, 4보다 작아야 하므로, 3이 나옵니다.

a^b의 최댓값도 7이지만, 4보다 작아야 하니, 3이라고 볼 수 있습니다.

주어진 코드

#include <stdio.h>
#include <stdlib.h>
//Complete the following function.
void calculate_the_maximum(int n, int k)
{
  //Write your code here.
}
int main()
{
    int n, k;
  
    scanf("%d %d", &n, &k);
    calculate_the_maximum(n, k);
 
    return 0;
}

답안 코드

#include <stdio.h>
#include <stdlib.h>
 
void calculate_the_maximum(int n, int k)
{
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        int x = i&j, y = i|j, z = i^j;
 
        if (x < k && x > maximum_and) {
            maximum_and = x;
        }
        if (y < k && y > maximum_or) {
            maximum_or = y;
        }
        if (z < k && z > maximum_xor) {
            maximum_xor = z;
        }
    }
}
 
printf("%d\n%d\n%d\n", maximum_and, maximum_or, maximum_xor);
}

해결 코드

#include <stdio.h>
#include <stdlib.h>
 
void calculate_the_maximum(int n, int k)
{
    int a = 0, b = 0;
    int eval_and = 0, eval_or = 0, eval_xor = 0;
 
    // 문제에 보면 a < b 조건이 있으므로,
    // for문의 조건을 a <= n-1, b <= n 으로 주었다.
    for(a = 1; a <= n-1; a++)
    {
        int nEval = 0;
        for(b = a+1; b <= n; b++)
        {
            // 실행 테스트가 가능하다고 가정했을 때,
            // 아래와 같이 Log 개념으로 printf를 찍으면서 값을 확인해주면
            // 좀 더 수월하게 해결점을 찾을 수 있다.
            nEval = a & b;
            if(eval_and < nEval && nEval < k)
                eval_and = a & b;
 
            //printf("[DEBUG] a :  %d, b : %d, eval_and : %d\n", a, b, eval_and);
 
            nEval = a | b;
            if(eval_or < nEval && nEval < k)
                eval_or = a | b;
 
            //printf("[DEBUG] a :  %d, b : %d, eval_or : %d\n", a, b, eval_or);
 
            if(eval_xor < nEval && nEval < k)
                eval_xor = a ^ b;
 
            //printf("[DEBUG] a :  %d, b : %d, eval_xor : %d\n", a, b, eval_xor);
        }
    }
 
    printf("%d\n%d\n%d", eval_and, eval_or, eval_xor);
}
 
int main()
{
    int n = 0, k = 0;
  
    scanf("%d %d", &n, &k);
    calculate_the_maximum(n, k);
 
    return 0;
}

결국, 과제를 해결하기 위해선, 과제의 의도를 파악해서 원리를 알아서 해결해야 합니다.

사실, 위 문제의 정답을 찾는데 비트 연산자 동작 원리를 세세하게까지 이해할 필요는 없죠.

1. a = 1, b = 2, a & b = 0; a | b = 3; a ^ b = 3;

여기서 왜 a & b가 0이고, a | b가 3이고, a ^ b가 3이 나오는지만 이해하고 넘어가면 될 것 같습니다.

1 = 0001 (binary)

2 = 0010 (binary)

a & b = 0000(binary), a | b = 0011(binary), a ^ b = 0011(binary)

이런 식으로 이해하시면 될 것 같습니다. 이러한 bit 연산을 bit 연산자를 이용하면 컴퓨터가 알아서 계산해준다는 내용이었습니다.

자세한 내용이 알고 싶거나 모르는 게 있으시면 댓글 남겨주세요~