C에서 임의 길이의 정수를 어떻게 구현할 수 있습니까?

C에서 임의 길이의 정수 구현

일반적인 long int의 용량을 초과하는 숫자를 처리해야 하는 작업에 직면했을 때 많은 프로그래머는 기존 오픈 소스 구현에 의존합니다. 그러나 사용자 정의 BigInt 클래스를 만드는 과제는 수치 연산의 복잡성에 대한 귀중한 통찰력을 제공합니다.

접근 방식

BigInt 구현을 위한 기본 접근 방식에는 숫자를 나타내는 것이 포함됩니다. 문자열로, 더 작은 숫자(예: 한 자리 숫자)로 나누어 배열에 저장합니다. 이를 통해 비교 연산자를 간단하게 구현할 수 있습니다. 문제는 덧셈, 곱셈과 같은 더 복잡한 연산을 구현하는 것입니다.

덧셈

덧셈을 수행하기 위해 우리는 CPU에서 사용하는 이진 연산을 모방합니다. BigInt 값 배열의 각 요소가 추가되고 오버플로가 다음 요소로 전달됩니다. 예를 들어 = 연산자 구현을 고려해보세요.

BigInt& operator+=(const BigInt& operand) {
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size()); count++) {
    BT op0 = count < value_.size() ? value_.at(count) : 0,
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result - carry < std::max(op0, op1)) {
      BT carry_old = carry;
      carry = digits_result;
      digits_result =
          (op0 + op1 + carry) >> sizeof(BT) * 8; // NOTE [1]
    } else
      carry = 0;
  }

  return *this;
}

곱셈

곱셈은 반복되는 덧셈을 사용하여 수행할 수 있습니다. 또는 Karatsuba 방법과 같은 효율적인 알고리즘을 사용할 수 있습니다.

추가 고려 사항

BigInt 클래스는 연산자<< 연산자

위 내용은 C에서 임의 길이의 정수를 어떻게 구현할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!