재미있는 도전. 🙂

임의의 길이의 정수를 원한다고 가정합니다. 다음 접근 방식을 제안합니다.

데이터 유형 “int”의 이진 특성을 고려하십시오. 간단한 이진 연산을 사용하여 CPU의 회로가 무언가를 추가 할 때 수행하는 작업을 에뮬레이션하는 것을 고려하십시오. 더 심도있는 관심이 있다면 반가산기 및 완전 가산기에 대한이 위키피디아 기사를 읽어보십시오 . 당신은 그와 비슷한 일을하게 될 것입니다.하지만 당신은 그렇게 낮은 수준으로 내려갈 수 있습니다.하지만 게으 르기 때문에 저는 그냥 포기하고 더 간단한 해결책을 찾을 것이라고 생각했습니다.

그러나 더하기, 빼기, 곱하기에 대한 알고리즘 세부 정보로 들어가기 전에 데이터 구조를 찾아 보겠습니다. 물론 간단한 방법은 std :: vector에 저장하는 것입니다.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

고정 된 크기의 벡터를 만들 것인지 미리 할당 할 것인지 고려할 수 있습니다. 다양한 연산을 위해 벡터의 각 요소 인 O (n)을 거쳐야하기 때문입니다. 작업이 얼마나 복잡 할 지 직접 알고 싶을 수 있으며 고정 n이 바로 그 작업을 수행합니다.

그러나 이제는 숫자에 대한 몇 가지 알고리즘에 대해 설명합니다. 논리 수준에서 할 수 있지만 그 마법의 CPU 성능을 사용하여 결과를 계산합니다. 그러나 Half-와 FullAdders의 논리 그림에서 우리가 인수 할 것은 운반을 다루는 방식입니다. 예를 들어 + = 연산자를 구현하는 방법을 고려하십시오 . BigInt <> :: value_의 각 숫자에 대해이를 추가하고 결과가 어떤 형태의 캐리를 생성하는지 확인합니다. 우리는 그것을 비트 단위로 수행하지 않을 것이지만 BaseType의 특성 (long, int, short 등)에 의존합니다. 오버플로됩니다.

당연히 두 개의 숫자를 더하면 결과는 그 숫자 중 더 큰 숫자보다 커야합니다. 그렇지 않은 경우 결과가 오버플로되었습니다.

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& 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;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

다른 산술 연산은 유사합니다. 도대체 stl-functor std :: plus 및 std :: minus, std :: times 및 std :: divides, …를 사용할 수도 있지만 캐리에 유의하십시오. 🙂 더하기 및 빼기 연산자를 사용하여 곱셈과 나눗셈을 구현할 수도 있지만, 각 반복에서 더하기 및 빼기에 대한 이전 호출에서 이미 계산 한 결과를 다시 계산하기 때문에 매우 느립니다. 이 간단한 작업을위한 좋은 알고리즘이 많이 있습니다. 위키피디아 나 웹을 사용하세요.

물론, 당신은 다음과 같은 표준 통신 구현해야합니다 operator<<단지에 VALUE_에 각 값을 이동을 (상기에서 시작, n 비트 떠났다 value_.size()-1… 오와 캐리 🙂 기억 operator<– 당신도 확인, 여기에 약간을 최적화 할 수 있습니다를 size()첫 번째 와 대략적인 자릿수 . 등등. 그런 다음 befriendig std :: ostream으로 클래스를 유용하게 만드십시오 operator<<.

이 접근 방식이 도움이되기를 바랍니다!