[C]백준_24389 : 2의 보수

Alal11·2023년 3월 4일
0
post-thumbnail

출처

https://www.acmicpc.net/problem/24389


문제

컴퓨터는 뺄셈을 처리할 때 내부적으로 2의 보수를 사용한다. 어떤 수의 2의 보수는 해당하는 숫자의 모든 비트를 반전시킨 뒤, 1을 더해 만들 수 있다. 이때, 32비트 기준으로 처음 표현했던 수와 그 2의 보수의 서로 다른 비트 수를 출력하라.


입력

첫째 줄에 정수 N(1 ≤ N ≤ 109)이 주어진다.


출력

첫째 줄에 N과 N의 보수의 서로 다른 비트 수를 출력한다.


예제 입출력


힌트

32비트 22의 보수를 살펴보자. 22는 이진수로 0000 0000 0000 0000 0000 0000 0001 0110이다. 이 비트를 반전시키면 1111 1111 1111 1111 1111 1111 1110 1001, 1을 더하면 1111 1111 1111 1111 1111 1111 1110 1010이 된다.

이 때 0000 0000 0000 0000 0000 0000 0001 0110과 1111 1111 1111 1111 1111 1111 1110 1010의 서로 다른 비트 수는 30개이다.


알고리즘 분류

  • 수학
  • 비트마스킹

➡️문제 분석

n을 입력받고, n과 n의 2의 보수의 이진수를 배열에 넣고 이를 바교하여 서로 다른 비트 수를 구해본다.


➡️코드(⭕)

#include <stdio.h>

int main()
{
	int n, cnt = 0, diff_bit = 0;

	int binary[33] = { 0 };		// 정수 n의 2진수 담을 배열
	int result[33] = { 0 };		// n의 보수 담을 배열

	scanf("%d", &n);

	for (int i = 0; ; i++)
	{
		if (n % 2 == 0)			// n % 2가 0일 때
		{
			binary[i] = 0;
			result[i] = 1;
		}
		else					// n % 2가 1일 때
		{
			binary[i] = 1;
			result[i] = 0;
		}
		cnt++;			// 몇 번째 자리까지 변경되었는지 세어줌
		
		if (n == 1)			// n이 1이 되면 반복 종료
			break;

		n = n / 2;			// n을 2로 나눈 몫을 다시 n에 대입
	}

	for (int i = 31; i >= cnt; i--)		// cnt 전까지 반복하연서 초기화 해줌
	{
		binary[i] = 0;
		result[i] = 1;
	}
	result[0]++;			// 0과 1을 바꾼 다음 +1 해줘서 n의 보수의 완성시킴

	for (int i = 0; i < 32; i++)
	{
		// n의 보수에서 비트가 2인 부분이 있으면 0으로 바꾸고 다음 비트에 +1 해줌
		if (result[i] == 2)
		{
			result[i] = 0;
			result[i + 1]++;
		}
		// n의 2진수와 n의 보수의 2진수의 서로 다른 비트 수를 세어줌
		if (binary[i] != result[i])
			diff_bit++;
	}
	printf("%d\n", diff_bit);

	return 0;
}

➡️코드 분석

  1. n의 이진수를 담을 배열 binary와 n의 보수를 담을 배열 result를 NULL 값까지 포함하여 크기 33으로 선언해주고, n을 입력받는다.

  2. 조건식 없이 i를 0부터 1씩 증가시키며 반복문을 돌리는데, n을 2로 나눈 나머지가 0일 때와 1일 때로 나눠서 각각 배열의 인덱스 i일 때 값에 0 또는 1을 넣어준다.

  3. 몇 번째 자리까지 값이 진행되었는지 cnt로 세어주고, 만약 n이 1이라면 반복문을 탈출하고, 아니라면 n을 2로 나눈 몫을 다시 n에 넣어주고 계속 반복한다.

  4. i=31부터 cnt까지 인덱스로 하는 각각 배열의 값을 0과 1로 모두 바꿔주고, 마지막으로 2의 보수 배열인 result의 첫 번째 값에 +1을 해줘서 완성시킨다.

  5. i=0부터 31까지 반복해주는데 n의 보수에서 해당 인덱스의 비트가 2라면, 0으로 바꾸고 다음 비트에 +1을 해준다.

  6. 마지막으로 binary와 result 배열의 요소 값을 비교하여 값이 다르면 diff_bit로 개수를 세어주고 최종값을 출력한다.


➡️end

문제 자체는 간단했지만 코드로 구현하려니 조금 길어지는 문제였다..! 뭔가 더 효율적으로 간단하게 푸는 방법이 있을 것 같은데 다른 분들의 코드도 참고해보는 것이 좋을 것 같다.

0개의 댓글