То, что вы действительно хотите сделать, это обрабатывать каждую цифру в порядке возрастания важности.Чтобы упростить это, вы должны реализовать следующие функции:
/* Return the number of fractional bits in bs */
int bs_fractbits(const char *bs);
/* Return the number of integer bits in bs */
int bs_intbits(const char *bs);
/* Return the bit in bs corresponding to value 2**i,
0 if outside the bit string */
int bs_bit(const char *bs, int i);
/* Return -1 if bs is negative,
0 if bs is zero or NULL,
+1 if bs is positive */
int bs_sign(const char *bs);
/* Return -1 if bs1 < bs2,
0 if bs1 == bs2,
+1 if bs1 > bs2. */
int bs_cmp(const char *bs1, const char *bs2);
Чтобы поддерживать отрицательные значения, вам необходимо реализовать сложение и вычитание (из "битов без знака"):
Добавление: результат содержит столько дробных битов, сколько содержится в терминах с наибольшим количеством дробных битов, и, возможно, на один целочисленный бит больше, чем в терминах с наибольшим количеством целых битов.Начните с младшего значащего бита в любом из этих терминов и продвигайтесь до самого старшего бита в любом из этих терминов, суммируя каждый бит и сохраняя «бит переноса», точно так же, как вы делали бы вручную .Если в конце перенос будет ненулевым, вы получите этот дополнительный бит.
Вычитание: всегда вычитайте меньшее из большего.Если это меняет порядок условий, отмените результат.Результат имеет не более столько дробных бит, сколько термин, который имеет большинство дробных бит, и самое большее столько целочисленных бит, как термин, который имеет большинство целочисленных бит.Это похоже на сложение, за исключением того, что вы вычитаете биты, и вместо «переносить бит» вы используете «бит заимствования».Поскольку вы вычитаете меньшее значение без знака из большего значения без знака, «бит заимствования» будет равен нулю в конце.
Умножение: целочисленная часть содержит число целочисленных битов и числодробные биты, поскольку термины имеют в сумме (суммированные).Вы можете реализовать операцию как умножение двух целочисленных значений без знака и просто вставить бит в конце.(Таким образом, в результате получается столько дробных битов, сколько в общей сложности содержится во входных терминах.) Обычно это включает двойной цикл, как при умножении long вручную.
Обратите внимание, что та же логика также работает, если вы используете большее основание вместо 2. "перенос" / "заимствование" - это цифра от нуля до единицы меньше, чем основание.
Лично,Я бы очень хотел использовать структуру для описания каждой строки цифр:
typedef struct {
int idigits; /* Number of integral digits before point */
int fdigits; /* Number of fractional digits after point */
int size; /* Number of chars dynamically allocated at data */
char *point; /* Location of decimal point */
char *data; /* Dynamically allocated buffer */
} digitstring;
#define DIGITSTRING_INIT { 0, 0, 0, NULL, NULL }
с дополнительным флагом, если необходимо поддерживать строки отрицательных цифр.
Цифра D с числовым значением D × B i , где B - основание (количество используемых уникальных цифр) и i , являющаяся положением указанной цифры, находится в point[-i], если i < 0 (и -i <= fdigits), или в point[-i-1], если i >= 0 (и i < idigits).point[0] - это точка десятичной запятой, если она есть.
Например, если у нас есть строка 0100.00, тогда idigits = 4, fdigits = 2, и единственная ненулевая цифра находится в позиции2.(Позиция 0 находится слева от десятичной точки, а -1 справа). Поля
size и data позволяют повторно использовать динамически распределенный буфер.Каждое объявление цепочки цифр должно быть инициализировано, digitstring value = DIGITSTRING_INIT;, потому что нет функции инициализации;таким образом, у вас меньше шансов утечки памяти (если вы не забудете освободить цепочку цифр, когда она больше не нужна):
/* Free the specified digit string. */
static inline void digitstring_free(digitstring *ds)
{
if (ds) {
if (ds->data)
free(ds->data);
ds->idigits = 0;
ds->fdigits = 0;
ds->size = 0;
ds->point = NULL;
ds->data = NULL;
}
}
Чтобы использовать строку цифр в качестве строки C, используйте вспомогательную функцию для полученияуказатель на самую значимую цифру в строке цифр:
/* Return a pointer to a printable version of the digit string. */
static const char *digitstring_str(const digitstring *ds, const char *none)
{
if (ds && ds->point)
return (const char *)(ds->point - ds->idigits);
else
return none;
}
Я обнаружил, что вместо сбоя часто полезно передать дополнительный параметр, который используется только для возвращаемого значения, когда возвращаемое значениеиначе не определено.Например, если у вас есть инициализированная цифровая строка foo без какого-либо содержимого, то digitstring_str(&foo, "0") возвращает строковый литерал "0".
Основной смысл структуры цифровой строки состоит в том, чтобы иметь функции доступа, которые получаюти установите каждую отдельную цифру:
/* Get the value of a specific digit. */
static inline unsigned int digitstring_get(const digitstring *ds, const int position)
{
if (ds) {
if (position < 0) {
if (-position <= ds->fdigits)
return digit_to_value(ds->point[-position]);
else
return 0;
} else {
if (position < ds->idigits)
return digit_to_value(ds->point[-position-1]);
else
return 0;
}
} else
return 0;
}
/* Set the value of a specific digit. */
static inline void digitstring_set(digitstring *ds, const int position, const unsigned int value)
{
if (!ds) {
fprintf(stderr, "digitstring_set(): NULL digitstring specified.\n");
exit(EXIT_FAILURE);
} else
if (position < 0) {
if (-position > ds->fdigits) {
fprintf(stderr, "digitstring_set(): Digit position underflow (in fractional part).\n");
exit(EXIT_FAILURE);
}
ds->point[-position] = value_to_digit(value);
} else {
if (position >= ds->idigits) {
fprintf(stderr, "digitstring_set(): Digit position overflow (in integer part).\n");
exit(EXIT_FAILURE);
}
ds->point[-position-1] = value_to_digit(value);
}
}
Выше value_to_digit() - вспомогательная функция, которая преобразует числовое значение в соответствующий символ, а digit_to_value() преобразует символ в соответствующее числовое значение.
Все операции (от разбора до арифметических операторов) действительно нуждаются в «конструкторе», который создает новую строку цифр с достаточным количеством цифр.(Количество цифр заранее известно для каждой операции и зависит только от количества значащих цифр в терминах.) Для этого я создал функцию, которая создает ноль нужного размера:
/* Clear the specified digit string to zero. */
static inline void digitstring_zero(digitstring *ds, int idigits, int fdigits)
{
int size;
char *data;
if (!ds) {
fprintf(stderr, "digitstring_zero(): No digitstring specified.\n");
exit(EXIT_FAILURE);
}
/* Require at least one integral digit. */
if (idigits < 1)
idigits = 1;
if (fdigits < 0)
fdigits = 0;
/* Total number of chars needed, including decimal point
and string-terminating nul char. */
size = idigits + 1 + fdigits + 1;
/* Check if dynamically allocated buffer needs resizing. */
if (ds->size < size) {
if (ds->data)
data = realloc(ds->data, size);
else
data = malloc(size);
if (!data) {
fprintf(stderr, "digitstring_zero(): Out of memory.\n");
exit(EXIT_FAILURE);
}
ds->data = data;
ds->size = size;
} else {
data = ds->data;
size = ds->size;
}
/* Fill it with zeroes. */
memset(data, value_to_digit(0), idigits + 1 + fdigits);
/* Pad the unused space with nul chars, terminating the string. */
memset(data + idigits + 1 + fdigits, '\0', size - idigits - 1 - fdigits);
/* Assign the decimal point. */
ds->point = data + idigits;
/* If there are no decimals, no need for a decimal point either. */
if (fdigits > 0)
ds->point[0] = decimal_point;
else
ds->point[0] = '\0';
/* After setting the desired digits, use digitstring_trim(). */
ds->idigits = idigits;
ds->fdigits = fdigits;
}
Это обеспечит, чтобы в строке цифр было достаточно места для указанного количества цифр, перераспределив ее динамически выделенный буфер, если необходимо, и повторно использовав ее, если она уже достаточно велика.
Идея состоит в том, что для реализации операции сначала нужно выяснить,максимальное количество целых и дробных цифр, которое может иметь результат.Вы используете выше, чтобы создать строку цифр результата, затем digitstring_set(), чтобы установить каждую цифру в их соответствующие значения.Как правило, вы будете работать с возрастающей цифрой значимости, что означает увеличение «позиции» цифр.
Если у нас есть дополнительные вспомогательные функции int digits(const char *src), который возвращает число последовательных действительных цифровых символов, начиная с src, и int decimal_points(const char *src), который возвращает 1, если src указывает на десятичную точку, и0 в противном случае мы можем разобрать входные строки в строки цифр, используя
/* Parse a string into a digit string, returning the pointer
to the first unparsed character, or NULL if an error occurs. */
static const char *digitstring_parse(digitstring *ds, const char *src)
{
const int zero = value_to_digit(0);
const char *idigit, *fdigit;
int idigits, fdigits, fextra, n;
/* Fail if nothing to parse. */
if (!src)
return NULL;
/* Skip leading whitespace. */
while (isspace((unsigned char)(*src)))
src++;
/* Fail if nothing to parse. */
if (*src == '\0')
return NULL;
/* Scan integer digits. */
idigit = src;
src += digits(src);
idigits = (int)(src - idigit);
/* Decimal point? */
fextra = 0;
n = decimal_points(src);
if (n > 0) {
src += n;
/* Scan fractional digits. */
fdigit = src;
src += digits(src);
fdigits = (int)(src - fdigit);
if (fdigits < 1)
fextra = 1;
} else {
fdigit = src;
fdigits = 0;
}
/* No digits? */
if (idigit == 0 && fdigit == 0)
return NULL;
/* Trim leading zeroes. */
while (idigits > 1 && *idigit == zero) {
idigits--;
idigit++;
}
/* Trim trailing zeroes. */
while (fdigits > 1 && fdigit[fdigits - 1] == zero)
fdigits--;
/* Create the necessary digit string, */
digitstring_zero(ds, idigits, fdigits + fextra);
/* copy the integer digits, if any, */
if (idigits > 0)
memcpy(ds->point - idigits, idigit, idigits);
/* and the fractional digits, if any. */
if (fdigits > 0)
memcpy(ds->point + 1, fdigit, fdigits);
/* Return a pointer to the first unparsed character. */
return src;
}
После обновления его цифр можно вызвать вспомогательную функцию для удаления любых лишних начальных нулей:
static inline void digitstring_ltrim(digitstring *ds)
{
if (ds && ds->point) {
const int zero = value_to_digit(0);
while (ds->idigits > 1 && ds->point[-ds->idigits] == zero)
ds->idigits--;
}
}
Добавление двух(беззнаковые) строки цифр, возможно, с повторным использованием одного из терминов, теперь довольно просто реализовать:
static void digitstring_add(digitstring *to, const digitstring *src1, const digitstring *src2)
{
digitstring result = DIGITSTRING_INIT;
unsigned int carry = 0;
int i, idigits, fdigits;
if (!to || !src1 || !src2) {
fprintf(stderr, "digitstring_add(): NULL digitstring specified.\n");
exit(EXIT_FAILURE);
}
/* For addition, the result has as many digits
as the longer source term. */
idigits = (src1->idigits >= src2->idigits) ? src1->idigits : src2->idigits;
fdigits = (src1->fdigits >= src2->fdigits) ? src1->fdigits : src2->fdigits;
/* Result needs possibly one more integer digit,
in case carry overflows. */
digitstring_zero(&result, idigits + 1, fdigits);
/* Addition loop, in order of increasing digit significance. */
for (i = -fdigits; i < idigits; i++) {
const unsigned int sum = digitstring_get(src1, i)
+ digitstring_get(src2, i)
+ carry;
digitstring_set(&result, i, sum % RADIX);
carry = sum / RADIX;
}
digitstring_set(&result, idigits, carry);
/* Trim leading zeroes. */
digitstring_ltrim(&result);
/* At this point, we can discard the target, even if it is actually
one of the sources, and copy the result to it. */
digitstring_free(to);
*to = result;
}
, где RADIX - используемый коэффициент (число уникальных цифр, 2 для двоичного).Обратите особое внимание на цифровую петлю.-fdigits - наименее значимая позиция в результате , а idigits-1 - наиболее значимая позиция.Нам нужны функции доступа, потому что исходные термины могут вообще не содержать этих цифр (тогда они логически равны нулю).
Эти функции были протестированы для работы как со строками двоичных, так и с восьмеричными числами.Мне нравится эта реализация, потому что она пропускает десятичную точку, если все термины являются целыми числами (поэтому вы получаете 12 + 33 = 45), но (из-за fextra в digitstring_parse()), если какой-либо из терминов имеет десятичную точку, то результатбудет иметь хотя бы одну дробную цифру (поэтому 12. + 33 = 45.0).