[알고리즘] 4. 비트연산으로 2진수 덧셈 (XOR, AND, Shift, Binary Add)

분명히 공부했는데

분명히 본 적이 있는데

하면서 먼지쌓인 정보처리기사 책을 펼쳤더니

"그래 이거였어! 생각난다" 가 아니라

"내가 이걸 공부해서 합격했었다고..??!!"라는

충격을 먹은 적.. 없으신가요? (저는 오늘)

 

안녕하세요,

센치한개발자입니다.

 

이번 알고리즘은 방송없이 2진수 덧셈을 비트연산에 대해서 알아보려고 합니다. 

(방송으로 하려니 저도 말이 꼬여서.. )

 

오늘 "뎃셈 "+" 연산을 사용하지 않고 비트연산을 통해 두 2진수를 더하는 원리를 저도 다시금 익히게 되었습니다.

 

일단 자바 소스부터 한번 보시죠~

public static void main(String[] args) {
        System.out.println(addBinaryPlus("1101","1011"));
        System.out.println(addBinaryNonPlus("1101","1011"));
    }

    //일반적인 덧셈연산
    public static String addBinaryPlus(String a, String b) {

        int aInt = Integer.parseInt(a, 2);
        int bInt = Integer.parseInt(b, 2);
        int sum = aInt + bInt;

        return Integer.toBinaryString(sum);
        
        //숫자가 커진다면 다음과 같이 사용합니다.
        /* 
         BigInteger aInt = new BigInteger(a, 2);
         BigInteger bInt = new BigInteger(b, 2);

         BigInteger sum = aInt.add(bInt);

         return sum.toString(2);
        */
    }

    //비트연산으로 덧셈 (최초 매개변수가 String 이라고 가정했을때)
    public static String addBinaryNonPlus(String a, String b) {

        int aInt = Integer.parseInt(a, 2);
        int bInt = Integer.parseInt(b, 2);

        return Integer.toBinaryString(addBin(aInt, bInt));
    }
    
    //재귀용 비트연산 함수
    public static int addBin(int a, int b) {
        if(b == 0) return a;
        //1. 두 비트 XOR 연산 : 두 비트가 다르면 1, 같으면 0
        //즉, 1+0, 0+1은 = 1이고 1+1, 0+0은 0이므로 두 비트의 올림수를 제외하고 덧셈을 할 수 있다.
        int sum = a^b;

        //2. AND 연산 : 두 비트가 모두 1이면 1 (==두 비트가 같을때)
        //1 + 1 의 비트는 올림수가 되므로 왼쪽으로 1 시프트 연산 (<<)
        int carry = (a&b) << 1;

        return addBin(sum, carry);
    }
 }

 

1101 과 1011 이라는 두 개의 2진수 바이너리

1101 과 1011 이라는 두 개의 2진수 바이너리가 있다고 가정했을때

보통의 방법은 이 두 수를 "+" 를 이용하여 addBinaryPlus 함수와 같이 1차적인 방법으로 코딩하는 것이 가장 먼저 떠오르는 방법입니다.

2진수라는 것을 알려주고 (parseInt) 단순히 + 연산으로 더한 뒤에 2진수 String으로 toBinaryString 해보면

가볍게(?) 덧셈 연산이 됩니다만...

 

여기서 한걸음 더 나아가,

비트 연산의 원리를 이용하면 진기(이해하면 그냥 평범한 것을..)한 경험을 하게 됩니다.

문제 출제의도가 2진수 덧셈 알고리즘의 해법을 "비트연산"으로 해결했는가를 판단하는 것이라면

재귀함수인 addBin 와 같이 코딩해볼 수 있을 것 같습니다.

 

덧셈을 위한 비트연산 해법의 핵심은 XOR, AND 연산 이렇게 2가지 입니다.

 

XOR : 두 비트가 다르면 1, 같으면 0 

AND : 두 비트가 모두 1이면 1, 아니면 0 

 

1번 XOR 연산에서

1 + 0, 0 + 1은 1을 반환하므로 올림수가 발생하는 1 + 1 을 제외하고 덧셈이 가능하고,

 

2번 AND연산을 통해

올림수가 발생해서 왼쪽의 비트를 +1 해줘야하는 1 + 1 연산 결과에 << 왼쪽 시프트 연산(비트를 한쪽으로 옮김) 을 해줍니다.

*. 왼쪽으로 시프트하면 우측은 0으로 채우게 됩니다.

 

보통 시프트 연산은 

"int변수 << 1"

처럼 간결하게 사용하는데,

"(a&b) << 1"

처럼 사용하면 AND 연산의 올림수 결과를 왼쪽으로 1칸 시프트하게 됩니다.

 

음...그리고

본 재귀함수의 종료 조건은 AND가 0이라서 더이상 올림수가 없을때입니다.

 

추가적으로, 숫자가 커지는 경우를 대비한다면 변수 타입을 애초헤 BigInteger로 처리해서

다음과 같이 함수가 바뀔 수 있을 것 같습니다.

public static String addBinaryNonPlus(String a, String b) {

        BigInteger aInt = new BigInteger(a, 2);
        BigInteger bInt = new BigInteger(b, 2);

        return addBin(aInt, bInt).toString(2);
}

public static BigInteger addBin(BigInteger a, BigInteger b) {
        if(b == BigInteger.ZERO) return a;

        BigInteger sum = a.xor(b);

        BigInteger carry = a.and(b).shiftLeft(1);

        return addBin(sum, carry);
}