ITMO 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).

Примеры

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

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

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000010

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

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000010001000

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

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

A + B = 

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000100000

B - A = 

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000