부호있는 정수 데이터를 이진 (비트)에서 빼는 가장 효율적인 방법은 무엇입니까?

Question

저는 가능한 한 적은 C++를 사용하고, unsigned char 형식으로 저장된 이진 데이터로 작업하면서 PC에서 C로 작업하고 있습니다. 다른 형식도 가치가 있다면 확실히 가능합니다. 목표는 다른 데이터 형식으로 변환하지 않고 2 개의 부호있는 정수 값 (정수, 부호있는 정수, long, 부호있는 long, 부호있는 short 등)을 2 진수에서 뺀 것입니다. 하지만 원시 데이터는 서명 된 정수 형식으로 미리 패키징되어 있습니다. 기본적으로 사용자는 서명 된 정수 형식 중 어느 것을 읽어야하는지 (즉, 한 번에 읽을 바이트 수를 알고 있음)를 알고 있습니다. 데이터가 부호없는 char 배열로 저장 되더라도 데이터는 2의 보수로 서명 된 읽기 전용입니다.

우리가 종종 학교에서 가르치는 한 가지 일반적인 방법은 부정적인 부분을 추가하는 것입니다. 부정은 차례로 플립 비트 (flipping bit)로 수행되고 1 (0x1)을 추가하여 두 개의 덧셈을 결과로하는 것으로 배웁니다. 또는 다른 게시물이 지적한대로 MSB에서 시작하여 첫 번째 0을지나 비트를 뒤집습니다. 데이터가 비트 형식으로 저장되기 때문에 펜과 종이 작업으로 쉽게 설명 할 수없는보다 효율적인 방법이 있는지 궁금합니다. 다음은 필자가 작성한 프로토 타입 중 가장 효율적인 방법은 아니지만 지금까지의 교과서 방법론을 기반으로 한 나의 진행 상황을 요약 한 것입니다.

가중치는 길이를 조정하기 위해 수동으로 연장해야하는 경우 참조로 전달됩니다. 모든 의견을 보내 주시면 감사하겠습니다! 고려해 주셔서 미리 감사드립니다.

void SubtractByte(unsigned char* & a, unsigned int & aBytes, 
       unsigned char* & b, unsigned int & bBytes, 
       unsigned char* & diff, unsigned int & nBytes) 
{ 
    NegateByte(b, bBytes); 

    // a - b == a + (-b) 
    AddByte(a, aBytes, b, bBytes, diff, nBytes); 

    // Restore b to its original state so input remains intact 
    NegateByte(b, bBytes); 
} 

void AddByte(unsigned char* & a, unsigned int & aBytes, 
      unsigned char* & b, unsigned int & bBytes, 
      unsigned char* & sum, unsigned int & nBytes) 
{ 
    // Ensure that both of our addends have the same length in memory: 
    BalanceNumBytes(a, aBytes, b, bBytes, nBytes); 
    bool aSign = !((a[aBytes-1] >> 7) & 0x1); 
    bool bSign = !((b[bBytes-1] >> 7) & 0x1); 


    // Add bit-by-bit to keep track of carry bit: 
    unsigned int nBits = nBytes * BITS_PER_BYTE; 
    unsigned char carry = 0x0; 
    unsigned char result = 0x0; 
    unsigned char a1, b1; 
    // init sum 
    for (unsigned int j = 0; j < nBytes; ++j) { 
     for (unsigned int i = 0; i < BITS_PER_BYTE; ++i) { 
      a1 = ((a[j] >> i) & 0x1); 
      b1 = ((b[j] >> i) & 0x1); 
      AddBit(&a1, &b1, &carry, &result); 
      SetBit(sum, j, i, result==0x1); 
     } 
    } 

    // MSB and carry determine if we need to extend: 
    if (((aSign && bSign) && (carry != 0x0 || result != 0x0)) || 
     ((!aSign && !bSign) && (result == 0x0))) { 
     ++nBytes; 
     sum = (unsigned char*)realloc(sum, nBytes); 
     sum[nBytes-1] = (carry == 0x0 ? 0x0 : 0xFF); //init 
    } 
} 


void FlipByte (unsigned char* n, unsigned int nBytes) 
{ 
    for (unsigned int i = 0; i < nBytes; ++i) { 
     n[i] = ~n[i]; 
    } 
} 

void NegateByte (unsigned char* n, unsigned int nBytes) 
{ 
    // Flip each bit: 
    FlipByte(n, nBytes); 
    unsigned char* one = (unsigned char*)malloc(nBytes); 
    unsigned char* orig = (unsigned char*)malloc(nBytes); 
    one[0] = 0x1; 
    orig[0] = n[0]; 
    for (unsigned int i = 1; i < nBytes; ++i) { 
     one[i] = 0x0; 
     orig[i] = n[i]; 
    } 
    // Add binary representation of 1 
    AddByte(orig, nBytes, one, nBytes, n, nBytes); 
    free(one); 
    free(orig); 
} 

void AddBit(unsigned char* a, unsigned char* b, unsigned char* c, 
unsigned char* result) { 
    *result = ((*a + *b + *c) & 0x1); 
    *c = (((*a + *b + *c) >> 1) & 0x1); 
} 

void SetBit(unsigned char* bytes, unsigned int byte, unsigned int bit, 
bool val) 
{ 
    // shift desired bit into LSB position, and AND with 00000001 
    if (val) { 
     // OR with 00001000 
     bytes[byte] |= (0x01 << bit); 
    } 
    else{ // (!val), meaning we want to set to 0 
     // AND with 11110111 
     bytes[byte] &= ~(0x01 << bit); 
    } 
} 

void BalanceNumBytes (unsigned char* & a, unsigned int & aBytes, 
         unsigned char* & b, unsigned int & bBytes, 
         unsigned int & nBytes) 
{ 
    if (aBytes > bBytes) { 
     nBytes = aBytes; 
     b = (unsigned char*)realloc(b, nBytes); 
     bBytes = nBytes; 
     b[nBytes-1] = ((b[0] >> 7) & 0x1) ? 0xFF : 0x00; 
    } else if (bBytes > aBytes) { 
     nBytes = bBytes; 
     a = (unsigned char*)realloc(a, nBytes); 
     aBytes = nBytes; 
     a[nBytes-1] = ((a[0] >> 7) & 0x1) ? 0xFF : 0x00; 
    } else { 
     nBytes = aBytes; 
    } 
} 

Answer 1

첫 번째로주의해야 할 점은 부호있는 것과 부호없는 것은 2의 보수로 생성 된 비트 패턴과 관련이 없다는 것입니다. 모든 변화는 결과의 해석입니다.

두 번째 주목해야 할 점은 부호없는 산술로 결과가 입력되면 결과가 작을 경우 더하기가 수행된다는 것입니다.

void AddByte(unsigned char* & a, unsigned int & aBytes, 
      unsigned char* & b, unsigned int & bBytes, 
      unsigned char* & sum, unsigned int & nBytes) 
{ 
    // Ensure that both of our addends have the same length in memory: 
    BalanceNumBytes(a, aBytes, b, bBytes, nBytes); 

    unsigned char carry = 0; 
    for (int j = 0; j < nbytes; ++j) { // need to reverse the loop for big-endian 
     result[j] = a[j] + b[j]; 
     unsigned char newcarry = (result[j] < a[j] || (unsigned char)(result[j]+carry) < a[j]); 
     result[j] += carry; 
     carry = newcarry; 
    } 
}