C++에서 나눗셈 없이 두 숫자의 빠른 평균 구하기

이 문제에서는 두 개의 숫자 A와 B가 주어지며, 우리의 과제는 나눗셈 연산자를 사용하지 않고 두 숫자의 빠른 평균을 계산하는 프로그램을 작성하는 것입니다.

예제를 통한 문제 이해

입력: A = 34, B = 54

출력: 44

해결 접근 방법

일반적으로 평균은 두 숫자를 더한 뒤 2로 나누어 계산합니다. 하지만 이 문제에서는 나눗셈 연산자를 사용하지 않고 평균을 구해야 합니다.

이때 활용할 수 있는 것이 바로 오른쪽 시프트 연산자(>>)입니다. 나눗셈 연산자 대신 이진수 표현을 오른쪽으로 한 비트 시프트하면 2로 나눈 것과 동일한 효과를 얻을 수 있습니다.

오른쪽 시프트가 나눗셈과 같은 이유

이진수에서 숫자를 오른쪽으로 한 비트 시프트하면 각 비트의 자릿값이 절반으로 줄어들기 때문에, 결과적으로 2로 나눈 값과 같아집니다. 예를 들어 10진수 88(이진수 1011000)을 한 비트 오른쪽 시프트하면 101100, 즉 10진수 44가 됩니다.

솔루션 동작을 보여주는 프로그램

#include <iostream>
#include <stdio.h>
using namespace std;

int calcAvgWODiv(int A, int B) {
    int average = (A + B) >> 1;
    return average;
}

int main() {
    int A = 123 , B = 653;
    cout<<"The average of the number is "<<calcAvgWODiv(A, B);
    return 0;
}

출력 −

The average of the number is 388

참고: 오버플로 주의 사항

A와 B가 매우 큰 정수라면 A + B를 계산하는 과정에서 정수 오버플로가 발생할 수 있습니다. 이 경우 다음 공식을 사용하면 오버플로 없이 안전하게 평균을 구할 수 있습니다.

int safeAvg(int A, int B) {
    return (A & B) + ((A ^ B) >> 1);
}

이 방식은 두 수의 공통 비트와 서로 다른 비트의 절반을 분리하여 더하기 때문에, 중간 합이 자료형 범위를 초과하지 않습니다.