무제한의 부호없는 정수 링크드 목록 구현입니다. 뺄셈이 작동하지 않습니다

Question

그래서 저는 작업중인 프로젝트 오일러 문제에 대한 링크드리스트를 사용하여 전체 무제한의 부호없는 정수 클래스를 구현했습니다. 모든 논리 비트 연산이 올바른지 확인했습니다 (그러나 볼 수 있으면 게시 할 수 있음). 이미 모든 운영자와 운영을 구현했습니다. 그러나 빼기 (및 그것을 사용하는 모든 것, 즉 나누기 및 모듈러스)는 작동하지 않습니다.

LimitlessUnsigned limitless = 0x88888888u; 
    limitless = limitless << 4; 

    LimitlessUnsigned tester = 0x88888884u; 
    tester = tester << 4; 

    //limitless = limitless >> 5; 
    LimitlessUnsigned another = limitless - tester; 

내가 디버거에서 다음과 같은 값을 얻을 : 나는 다음 테스트를 실행하면, 이것은 내가 무엇을 얻을

another LimitlessUnsigned 
integerList std::__1::list<unsigned int, std::__1::allocator<unsigned int> >  
[0] unsigned int 0b11111111111111111111111111111111 
[1] unsigned int 0b00000000000000000000000001000000 
limitless LimitlessUnsigned 
integerList std::__1::list<unsigned int, std::__1::allocator<unsigned int> >  
[0] unsigned int 0b00000000000000000000000000001000 
[1] unsigned int 0b10001000100010001000100010000000 
tester LimitlessUnsigned 
integerList std::__1::list<unsigned int, std::__1::allocator<unsigned int> >  
[0] unsigned int 0b00000000000000000000000000001000 
[1] unsigned int 0b10001000100010001000100001000000 

내가 뺄셈의 정의와 2의 뭔가를 놓친 것 같다 경의. 이 코드는 32 비트를 추가 할 때까지 작동합니다. 나는 처음 32에서 다음 32로 오버플로를 고려하고있다. 그러나 나는 (내가해야한다고 생각했듯이) 가장 높은 비트에서 오버플로를 버리고있다. 분명히, 나는 이것을 정확하게하지 않을 것이다. 아래는 관련 소스 코드입니다.

void LimitlessUnsigned::Sub(const LimitlessUnsigned& other) 
{ 
    if(*this <= other) 
    { 
    *this = 0u; 
    return; 
    } 

    LimitlessUnsigned temp = other; 

    while(temp.integerList.size() > integerList.size()) 
    integerList.push_front(0u); 

    while(integerList.size() > temp.integerList.size()) 
    temp.integerList.push_front(0u); 

    temp.TwosComp(); 
    Add(temp, true); 
} 
void LimitlessUnsigned::Add(const LimitlessUnsigned& other, bool allowRegisterLoss) 
{ 
    LimitlessUnsigned carry = *this & other; 
    LimitlessUnsigned result = *this^other; 

    while(carry != 0u) 
    { 
    carry.ShiftLeft(1, allowRegisterLoss); 
    LimitlessUnsigned shiftedcarry = carry; 
    carry = result & shiftedcarry; 
    result = result^shiftedcarry; 
    } 

*this = result; 
} 


void LimitlessUnsigned::Not() 
{ 
    for(std::list<unsigned>::iterator iter = integerList.begin(); iter != integerList.end(); ++iter) 
    {  
     *iter = ~*iter;  
    } 
} 

void LimitlessUnsigned::TwosComp() 
{ 
    Not(); 
    Add(1u, true); 
} 

void LimitlessUnsigned::ShiftLeft(unsigned shifts, bool allowRegisterLoss) 
{ 
    unsigned carry = 0u; 
    bool front_carry = false; 

    while(shifts > 0u) 
    {  
    if((integerList.front() & CARRY_INT_HIGH) == CARRY_INT_HIGH) 
     front_carry = true;  

    for(std::list<unsigned>::reverse_iterator iter = integerList.rbegin(); iter != integerList.rend(); ++iter) 
    {  
    unsigned temp = *iter; 

     *iter = *iter << 1; 
     *iter = *iter | carry;  

     if((temp & CARRY_INT_HIGH) == CARRY_INT_HIGH) 
     carry = CARRY_INT; 
     else 
     carry = 0u; 
    } 

    carry = 0u; 

    if(front_carry && !allowRegisterLoss) 
    { 
     front_carry = false; 
     integerList.push_front(1u); 
    } 

    --shifts;  
    } 
} 

업데이트 나는 마지막으로 문제를 해결했다. 여기 내 블로그 게시물은 소스 코드와 함께입니다 :

http://memmove.blogspot.com/2013/04/unlimited-unsigned-integer-in-c.html

Answer 1

폭이 동일하지 않을 때 제로 확장을 사용하면 추가 2의 보수를 복용 후. 감손 (현재는 가수)을 피감수만큼 확대 할 때 부호 확장을 사용해야하며 제로 확장은 필요하지 않습니다. 이것은 2의 보수 값이이 컨텍스트에서 음수로 취급되어야하기 때문입니다 (모든 것이 다른 곳에서 서명되지 않았음에도 불구하고). 양자 택일로 (그리고 아마 전체적인 디자인과 조화하여), 감정 및 피폭은 2의 보완 사업으로 시작하기 전에 동일한 폭이어야합니다. 이 같은

당신이하고있는 일 :

0110 - 10 = 0110 + (~(10) + 1) 
      = 0110 + (01 + 1) 
      = 0110 + 10 
      = 0110 + 0010 
      = 1000 

가해야 할 때 :

0110 - 10 = 0110 + (~(10) + 1) 
      = 0110 + (01 + 1) 
      = 0110 + 10 
      = 0110 + 1110 <= sign-extended subtrahend 
      = 0100 

또는 대안 : 옛적에 한 번

0110 - 10 = 0110 - 0010 <= widths equalized 
      = 0110 + (~(0010) + 1) 
      = 0110 + (1101 + 1) 
      = 0110 + 1110 
      = 0100 

Answer 2

제어 데이터에서 일부 엔지니어 Corporation (CDC)는 단일 사이클 가산기를 발명했습니다 (그 전에는 덧셈기가 1 비트 당 1 사이클을 carr 전파 y)와 CDC가 발명품 특허를 취득했습니다. 그런 다음 엔지니어는 크레이 (Cray)에 고용되었으며 빠른 추가 기능을 원했습니다. 그래서 영리한 엔지니어들은 차감기를 빌려주는 배후의 빠른 모습을 고안했고 Cray는이를 특허했습니다.

이야기의 사기는 더하기와 빼기가 같은 것이며, 빼기 코드는 추가 코드와 거의 같아야합니다.