Каков наиболее эффективный способ вычесть знаковые интегральные данные в двоичном формате (биты)?

Question

Я работаю в C на ПК, стараюсь использовать как можно меньше C ++, работаю с двоичными данными, хранящимися в формате без знака, хотя другие форматы, безусловно, возможны, если они того стоят. Цель состоит в том, чтобы вычесть два двоичных значения со знаком (которые могут быть целыми числами, целыми числами со знаком, длинными, знаковыми длинными значениями, короткими знаками и т. Д.) В двоичном формате без преобразования в другие форматы данных. Тем не менее, необработанные данные просто упаковываются как unsigned char, при этом пользователь, в основном, знает, какой из целочисленных форматов со знаком следует использовать для чтения (то есть мы знаем, сколько байтов нужно прочитать одновременно). Несмотря на то, что данные хранятся в виде массива без знака, данные должны читаться со знаком как два целых числа с дополнением.

Одним из распространенных способов, которым нас часто учат в школе, является добавление негатива. Отрицание, в свою очередь, часто учат выполнять в виде переворачивания битов и сложения 1 (0x1), что приводит к двум сложениям (возможно, плохо?); или, как указывают другие сообщения, переключение битов после первого нуля, начиная с MSB. Мне интересно, есть ли более эффективный способ, который нелегко описать как ручку и бумагу, но работает из-за способа хранения данных в битовом формате. Вот несколько прототипов, которые я написал, что, возможно, не самый эффективный способ, но который суммирует мой прогресс на основе методологии учебника.

Дополнения передаются по ссылке на случай, если мне придется вручную их расширять, чтобы сбалансировать их длину. Любые отзывы будут оценены! Заранее спасибо за рассмотрение.

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

Первое, на что нужно обратить внимание, это то, что знаковый и неподписанный значения не имеют значения для сгенерированной битовой комбинации в дополнении к двум. Все, что меняется, - это интерпретация результата.

Второе, на что следует обратить внимание, - это то, что сложение переносится, если результат меньше, чем любой из входных данных, когда выполняется с арифметикой без знака.

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;
    }
}