Блок задач

5. Проекты

Темы
Сложность 9

Проект «64-битная арифметика на базе 32-битной»

Реализовать функции работы с 64-битными числами на базе 32-битной арифметики, не используя типы __int64 и long long.

Примерный интерфейс:

typedef struct _LongLong {
    unsigned long lo, hi;
} Longlong;

/* присваивает (*pl1) <- (*pl2) */
void ll_assign(Longlong *pll, Longlong *pll2);

/* присваивает (*pl1) <- x (32-битное число) */
void ll_assign_long(Longlong *pl, long x);

/* увеличение на 1 */
void ll_inc(Longlong *pl);

/* уменьшение на 1 */
void ll_dec(Longlong *pl);

/* (*pl) = -(*pl) */
void ll_negate(Longlong *pl);

/* (*pl) = |(*pl)| */
void ll_abs(Longlong *pl);

/* сдвиг влево числа (*pl) на n разрядов */
void ll_shiftleft(Longlong *pl, int n);

/* сдвиг вправо числа (*pl) на n разрядов */
void ll_shiftright(Longlong *pl, int n);

/* беззнаковый сдвиг вправо числа (*pl) на n разрядов */
void ll_ushiftright(Longlong *pl, int n);

/* знак числа (-1 если меньше 0, 0 если 0, 1 если больше 0) */
int ll_sign(Longlong *pl);

/* операторы сравнения (возвращают 1, если условие истинно, иначе 0) */
int ll_eq(Longlong *px, Longlong *py);          /* x == y */
int ll_neq(Longlong *px, Longlong *py);         /* x != y */
int ll_lt(Longlong *px, Longlong *py);          /* x < y */
int ll_gt(Longlong *px, Longlong *py);          /* x > y */
int ll_le(Longlong *px, Longlong *py);          /* x <= y */
int ll_ge(Longlong *px, Longlong *py);          /* x >= y */

/* побитовые операторы над x и y (результат в res)  */
int ll_and(Longlong *pres, Longlong *px, const Longlong *py);
int ll_or(Longlong *pres, Longlong *px, const Longlong *py);
int ll_xor(Longlong *pres, Longlong *px, const Longlong *py);

/* сложение */
void ll_add(Longlong *pres, Longlong *px, Longlong *py);
void ll_add1(Longlong *pres, Longlong *px, long y);

/* вычитание */
void ll_sub(Longlong *pres, Longlong *px, Longlong *py);
void ll_sub1(Longlong *pres, Longlong *px, long y);

/* умножение */
void ll_mul(Longlong *pres, Longlong *px, Longlong *py);
void ll_mul1(Longlong *pres, long x, long y);
void ll_umul1(Longlong *pres, unsigned long x, unsigned long y); /* беззнаковое */

/* беззнаковое деление */
void ll_udiv0(Longlong *pres, Longlong *px, unsigned short sy);
void ll_udiv1(Longlong *pres, Longlong *px, unsigned long ly);
void ll_udiv(Longlong *pres, Longlong *px, Longlong *py);

/* деление со знаком */
void ll_div1(Longlong *pres, Longlong *px, long ly);
void ll_div(Longlong *pres, Longlong *px, Longlong *py);

Число в структуре Longlong хранится в двоичном дополнительном коде. Из этого следует, что многие функции автоматически способны работать как со знаковыми, так и с беззнаковыми числами. Для умножения и деления предусмотрено разделение на знаковую и беззнаковую часть.