이번 글에서는 하나의 숫자가 주어졌을 때, 그 숫자에 1을 더하는 과정에서 몇 개의 비트가 변경되는지 계산하는 방법을 알아보겠습니다.
숫자의 이진수 표현은 주어진 수를 0과 1의 형태로 변환하는 것을 의미하며, 다양한 방법으로 구할 수 있습니다. 대표적인 방법 중 하나는 주어진 수를 2로 나눈 나머지를 확인하는 것입니다. 나머지가 0이 아니면 해당 자리의 비트는 1로 설정되고, 나머지가 0이면 비트는 0으로 설정됩니다.
비트의 덧셈 규칙
0 + 1 = 1 1 + 0 = 1 0 + 0 = 0 1 + 1 = 10 (자리올림 1비트 발생)
예시
입력 예제 1
입력 − num = 10 출력 − count is : 1
설명 − 10의 이진수 표현은 1010이며, 여기에 1을 더하면 1011이 됩니다. 단 하나의 비트만 변경되었으므로 결과는 1입니다.
입력 예제 2
입력 − num = 5 출력 − count is : 2
설명 − 5의 이진수 표현은 101이며, 여기에 1을 더하면 110이 됩니다. 두 개의 비트가 변경되었으므로 결과는 2입니다.
알고리즘 접근 방법
정수형 변수를 선언하여 숫자를 입력받습니다. (예:
int num)변경된 비트의 개수를 저장할 변수를 선언합니다. (예:
int count)또 다른 변수를 선언하고,
n ^ (n + 1)연산으로 XOR 값을 계산하여 저장합니다.XOR 값에 대해
__builtin_popcount()함수를 호출합니다. 이 함수는 정수의 이진수 표현에서 1로 설정된 비트(세트 비트)의 개수를 세어주며, GCC 컴파일러에서 기본 제공되는 내장 함수입니다.계산된 count 값을 반환합니다.
결과를 출력합니다.
구현 예제 코드
#include <iostream>
using namespace std;
// 변경된 비트의 개수를 찾는 함수
int changedbit(int n){
int XOR = n ^ (n + 1);
// XOR 값에서 세트 비트(1)의 개수를 셉니다.
int count = __builtin_popcount(XOR);
return count;
}
int main(){
int n = 10;
cout << "count is: " << changedbit(n);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다 −
count is: 1
동작 원리 이해하기
이 방법이 왜 작동하는지 간단히 살펴보겠습니다. 어떤 수 n에 1을 더하면, 가장 오른쪽에 있는 0인 비트가 1로 바뀌고 그 아래(오른쪽)에 있던 모든 1인 비트들은 자리올림(carry)에 의해 0으로 바뀝니다. 따라서 n ^ (n + 1)의 결과는 정확히 변경된 비트들만 1로 표시됩니다. 여기에 세트 비트를 세어주면 곧바로 변경된 비트의 개수를 얻을 수 있습니다.