덧셈 연산 없이 비트 연산자로 덧셈 구현

XOR 연산은 두 비트가 다르면 1, 같으면 0을 반환한다.

비트 두개를 더한다고 생각할때 올림수를 제외하여 생각하면 XOR 연산 결과와 동일하다.

 

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0  <--- 이때 올림이 발생한다. 일단 이것은 제외.

 

올림이 발생한 경우 AND 연산을 통해 1비트 왼쪽으로 옮겨주면 올림이 된것을 표현할 수 있습니다.

보면 AND 연산으로 1의 자리에 1이 나올텐데 이것을 1비트 왼쪽으로 옮기면 올림이 된 상태가 됩니다.

 

이제 예를 보겠습니다.

결과로 11101이 나오는데 이 수는 11100 + 1로 나타납니다.

신기하게 + 1은 각 자리의 비트를 XOR 연산한 결과이고,

11100은 각 자리의 비트를 AND 연산하여 왼쪽으로 1비트씩 옮긴 상태입니다.

 

즉, XOR연산과 AND 연산으로 덧셈을 구현할 수 있다는 것입니다.

XOR연산의 결과와 (AND 연산 + 왼쪽으로 1비트 이동) 을 더하면 덧셈을 구현할 수 있다는 것입니다.

 

 

구현 코드

int add(int a, int b)
{
	if (b == 0)
		return a;
	/*else if (a == 0)
		return b;
		*/
	int sum = a ^ b;
	int carry = (a & b) << 1;
	return add(sum, carry);
}

sum은 위의 예에서 11100으로 XOR연산의 결과이고

carry는 1로 AND 후 왼쪽으로 1비트 이동의 결과입니다.

이것을 재귀적으로하면 carry가 0이 되는 경우가 생기는데 이때가 재귀 함수의 종료입니다.

 

실행 결과