Лабораторная работа 2: ITMO Endian

Вы уже успели познакомиться с различными целочисленными типами (int32_t, int8_t, uint16_t), и выяснили, что они могут храниться в прямом, обратном и дополнительном коде, а также, что порядок байт в них может быть разным: например, big endian и little endian.

В данной работе вам предстоит спроектировать и реализовать свой целый беззнаковый целочисленный тип uint239_t, способ хранения которого - ITMO Endian.

Диапазон значений данного типа: $[0; 2^{239} - 1]$.

Размер типа: 35 байт.

Для вышеуказанного типа требуется реализовать следующий набор функций и операторов

1. Конвертация из типа uint32_t.
2. Конвертация из строки (для M3110-14 гарантируется, что число в строке $< 2^{64}$).
3. Сложение.
4. Вычитание.
5. Умножение (только для M3100-09).
6. Деление (только для M3100-09).
7. Вывод числа в поток.
8. Получение сдвига.
9. Проверка на равенство.
10. Проверка на неравенство.

Формат ITMO Endian

В ITMO-endian каждый байт содержит 7 значимых бит (младшие) и один служебный бит (старший).

uint239_t занимает ровно 35 байт. Из-за того, что 239 не делится нацело на 7, в байтах uint239_t содержится 6 padding бит, всегда равных нулю.

Таким образом, uint239_t, записанный в двоичном виде содержит:

• 239 значимых бит.
• 35 служебных бит, отвечающих за сдвиг.
• 6 padding бит, всегда равных нулю.

Важно заметить, что padding биты учавствуют в сдвиге.

Например, число 2047 в формате ITMO Endian примет следующий вид (служебные биты выделены красным, padding биты синим):

$$ \large{2047 = \langle \textcolor{red}{0} \textcolor{blue}{000000} \underbrace{0\dots0}_{260} \ \textcolor{red}{0} 0001111 \ \textcolor{red}{0} 1111111 \rangle, \qquad \text{Сдвиг} = 0} $$

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

Например, следующие последовательности бит также кодируют 2047:

$$ \large{2047 = \langle \textcolor{red}{0} \textcolor{blue}{00000} \underbrace{0\dots0}_{260} \ \textcolor{red}{0} 0011111 \ \textcolor{red}{1} 111111\textcolor{blue}{0} \rangle, \qquad \text{Cдвиг} = 1} $$

$$ \large{2047 = \langle \textcolor{red}{0} \textcolor{blue}{0000} \underbrace{0\dots0}_{260} \ \textcolor{red}{1} 0111111 \ \textcolor{red}{0} 11111\textcolor{blue}{00} \rangle, \qquad \text{Cдвиг} = 2} $$

$$ \large{2047 = \langle \textcolor{red}{0} \textcolor{blue}{000} \underbrace{0\dots0}_{260} \ \textcolor{red}{1} 1111111 \ \textcolor{red}{1} 1111\textcolor{blue}{000} \rangle, \qquad \text{Cдвиг} = 3} $$

Арифметические операции над ITMO Endian

Арифметические операции над ITMO Endian работают согласно следующим правилам:

• Числа, закодированные в ITMO Endian, складываются, вычитаются, умножаются и делятся согласно правилам стандартной арифметики.
• Во время произведения операций, сдвиг результирующего числа рассчитывается из сдвигов операндов: является суммой сдвигов операндов при сложении и умножении, и разностью сдвигов операндов при вычитании и делении.
• Переполнение значимых бит - Undefined Behavior.

Операция	Операция для сдвига	Пример
Сложение	Сложение	239 (сдвиг 3) + 30 (сдвиг 5) = 269 (сдвиг 8).
Вычитание	Вычитание	239 (сдвиг 3) - 30 (сдвиг 5) = 209 (сдвиг $2^{35} - 2$, т.к. происходит переполнение.
Умножение	Сложение	123 (сдвиг 6) * 10 (сдвиг 4) = 1230 (сдвиг 10).
Деление	Вычитание	42 (сдвиг 7) / 5 (сдвиг 2) = 8 (сдвиг 5).

Инструкция по выполнению

Вам дан шаблон проекта, состоящие из трех директорий:

• bin
• lib
• tests

Менять стуктуру проекта, добавлять новый файлы запрещается.

Требуется:

1. Реализовать тип uint239_t, описав его в заголовочном файле lib/number.h (обратите внимание, что такая структура там уже есть, требуется дополнить ее описание)
2. Реализовать вышеуказанные функции и операторы, написав реализацию в lib/number.cpp

Тесты

Проект содержит базовый набор тестов, который позволит убедиться, что реализация функций выполненна без явных ошибок. Для запуска тестов в командной строке можно выполнить следующую операцию:

cmake --build . --target number_tests && ctest -V

или воспользоваться средствами вашей IDE

Пока все тесты не будут проходить, показывать лабораторную нельзя (группы для которых не требуется умножение и деление могут закомментировать ненужные тесты, см. комментарий в коде).

Тесты при желании можно дополнять, но это не обязательно.

Тесты также дополняют задание, демонстрируя ожидаемое поведение операторов и функций

Если этого не хватило

В директории bin находится консольное приложение, которое вы также можете использовать по вашему усмотрению (например чтобы проверить свой код). Для запуска выполнить следующую команду:

cmake --build . --target labwork2 && bin/labwork2

или воспользоваться IDE

Примечание

Реализация арифметических операций описна в коде как перегрузка соответствующих операторов. На данный момент мы не успели обсудить на лекциях операторы и их перегрузку, поэтому на данный момент следует воспринимать запись

uint239_t operator+(const uint239_t& lhs, const uint239_t& rhs)

как функцию, которая принимает два аргумента, складывает их и возвращает результат того же типа.

Ограничения

• Запрещается использование стандартных контейнеров (std::vector, std::list и тд)
• Запрещается использование std::bitset

Примеры

Примеры чисел

1 со смещением 1:

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000010

1 смещением 3:

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000010001000

Примеры выполнения операций

Пусть А это первое число из примера выше, B - второе, тогда

A + B = 

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000100000

B - A = 

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000

Дополнительная информация

• С большой вероятностью для реализации вам потребуются побитовые операции
• Если возникнет желание (не является частью задания) дополнить тесты, документацию по GoogleTest можно найти здесь

Deadlines

1. 15.10.24 23:59 - 0.8
2. 22.10.24 23:59 - 0.65
3. 29.10.24 23:59 - 0.5