백준 24389: 2의 보수 [java]

비트마스킹 문제를 정복하기 위해 보던 난이도 순서대로 푸는 도중에 "보수"라는 부분이 나와서 찾아보았다.

 

2의 보수란??

---

컴퓨터가 음수를 저장하기 위해 사용하는 방법

ex) 문제를 기준으로 32비트 머신이 있다고 생각해보자.

그렇다면 표현 가능한 수는 총 2^32개가 된다.

양수만을 저장하면 0 ~ (2^32 - 1)까지 차례로 저장할 수 있지만 음수를 저장하는 것도 필요하다.

그래서 2^32개 의 절반을 음수을 위해 할당한다. 

<int형의 범위가 -2,147,483,648 ~ 2,147,483,647인 것 처럼..>

 

맨 앞의 비트가 0이면 양수 / 1이면 음수가 된다.

 

십진법에서 이진수로 변환하는 것은 중학교때 배웠으니 넘어가고 

음수를 나타내는 법만 알아보자.

 

예를 들어 5라는 숫자가 있다면 4비트로 표현하면 0101이 된다.

이것을 음수로 바꾸는 것도 쉽다.

"NOT x" + 1을 해주면 끝이다.  그 전 포스팅을 봤다면 '~'연산자가 떠오를 것이다.

[잘 모르겠다면 이전 포스팅을 참고하자 2024.01.22 - [컴퓨터 공학/Algorithm] - [Algorithm] Bit와 BitMask (java)]

 

0101 -- NOT x --> 1010 -- "+ 1" --> 1011

계산하면 1011이 된다.

 

그러면 이제 문제를 풀어보자

---

 

문제

---

문제는 브론즈 1문제로 수학, 비트마스킹 알고리즘으로 분류되어있다.

 

접근방법

---

• "NOT N"에 1을 더해준다. : 보수 저장 <~연산자 : 각 비트를 1은 0으로 0은 1로 변환>
• 비트가 같은 부분을 구해준다.  <^ 연산자 : 다르면 1, 같으면 0 반환>
• 숫자를 2진수로 표현한 문자열로 반환.
• 만약 1이라면(비트가 다르다면 개수를 ++ 해준다)

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args)throws Exception{
		new Main().sol();
	}

	private void sol() throws Exception{
		int N = Integer.parseInt(br.readLine());

		int reverseN = ~N + 1;

		int same = N ^ reverseN;
		
		int cnt = 0;

		for(char ch : Integer.toBinaryString(same).toCharArray()){
			if(ch == '1') cnt++;
		}
		System.out.println(cnt);
	}
	
}

오늘도 하나 배워서 성장하길 바랍니다.

읽어주셔서 감사합니다.

 

- fin -