2진수의 사칙연산

참고 : [IT Series] 2진수 4칙연산(더하기,빼기,곱하기,나누기) 원리

덧셈

• 자릿수(carry) + 덧셈 (xor) 로 표현 가능

  int bitwise_add(int a, int b) {
    while (b != 0) {  // 더이상 자리올림 값이 없을 떄까지 반복
        int carry = a & b;  // 자리올림 계산
        a = a ^ b;          // 자리올림을 제외한 덧셈
        b = carry << 1;     // 자리올림을 왼쪽으로 한 비트 이동
    }
    return a;
  }

  

뺄셈

• 2의 보수를 계산하고 덧셈 과정 진행

  int bitwise_subtract(int a, int b) {
    // b의 2의 보수 계산
    int b_complement = ~b + 1;
    // a와 b의 2의 보수 더하기
    return a + b_complement;
  }

곱셈

• 더하기로 분리하여 계산
• 마지막 bit가 1이면, 결과값 더하기.
• 곱하는 값은 >> 연산을 통해 더한 부분 제거
• 곱해지는 값은 << 연산을 통해 자릿수 올리기

  int bitwise_multiply(int a, int b) {
    int result = 0;
    while (b != 0) {
        if (b & 1) { // b의 마지막 비트가 1인 경우
            result = result + a;
        }
        a <<= 1; // a를 왼쪽으로 시프트
        b >>= 1; // b를 오른쪽으로 시프트
    }
    return result;
  }

  

나눗셈

• 빼기로 분리하여 계산

  • 피제수의 부호를 확인하고 양수 변환

  • 피제수를 >> 연산해서 앞자리부터 값이 제수보다 큰지 비교

  • 크다면 몫에 해당 비트 위치를 더하고,

  • 피제수에 제수를 해당 비트 위치만큼 << 연산한 값을 뺌

  • 자릿수 만큼 반복 (마지막 피제수는 나머지 값이 됨)

    int bitwise_divide(int dividend, int divisor) {
    if (divisor == 0) {
      throw std::invalid_argument("Divisor cannot be zero.");
    }
    
    int quotient = 0;
    int remainder = 0;
    
    // 피제수의 부호를 확인하고 양수로 변환
    bool is_negative = (dividend < 0) ^ (divisor < 0);
    dividend = abs(dividend);
    divisor = abs(divisor);
    
    for (int i = 31; i >= 0; --i) {
      // divisor를 왼쪽으로 i만큼 시프트하여 dividend와 비교
      if ((dividend >> i) >= divisor) {
          // quotient에 해당 비트 위치를 더함
          quotient += (1 << i);
          // dividend에서 시프트된 divisor를 뺌
          dividend -= (divisor << i);
      }
    }
    
    // 몫의 부호를 결정
    return is_negative ? -quotient : quotient;
    }