符号付き整数データをバイナリ（ビット）で減算する最も効率的な方法は何ですか？

Question

私はPC上でCで作業していますが、できるだけC++を使用せず、符号なしのchar形式で保存されたバイナリデータを使って作業しています。目的は、他のデータ形式に変換せずに、2つの符号付き整数値（int、signed int、long、signed long、signed shortなど）をバイナリで減算することです。しかし、生のデータは、符号なし整数として書かれているだけであり、ユーザは符号付き整数フォーマットのどれを読み込みに使用すべきかを基本的に知っている（すなわち、一度に読み込むバイト数を知っている）。データは符号なしchar配列として格納されますが、データは2の補数の整数として符号付きで読み込まれることを意味します。

私たちがよく学校で教えている一般的な方法の1つに、否定が追加されています。否定は、フリップビットとして実行され、1（0x1）を追加して2つの追加（おそらく悪いことがありますか？他のポストが指摘しているように、MSBから始まる第1のゼロを過ぎてビットをフリップする。私は、ペン＆ペーパの操作として簡単には記述できない、より効率的な方法があるのだろうかと思っていますが、データがビット形式で保存されるために機能します。ここに私が書いたプロトタイプがありますが、これは最も効率的な方法ではないかもしれませんが、これまでのところ、教科書の方法論に基づいて私の進歩を要約しています。

手作業でそれらの長さのバランスをとるために加算を渡す必要がある場合に備えて、加算が渡されます。すべてのフィードバックは高く評価されます！検討のために事前に感謝します。

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の補数で生成されたビットパターンに関係しないことです。そのすべての変更が結果の解釈です。

注目すべき第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; 
    } 
}