Представление отрицательных чисел в СОК

Рассмотрим правила выполнения операций вычитания в системе остаточных классов для чисел А и В, удовлетворяющих условию А-В Í[0, ];

А = (a₁, a₂,...,a_n),

В = (b₁, b₂,...,b_n),

A-B = (g₁, g₂,...,g_n),

при этом А<ρ, B< ρ, 0<=А-В< ρ.

Как и ранее, получаем для А-В:

g_i = a_i - b_i - ,

g_i º a_i - b_i (mod p_i).

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

При отрицательной разности цифр берется ее дополнение к основанию. При этом знак результата в результате никак не отражен.

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

Рассмотрим варианты введения отрицательных чисел.

Пусть p₁, p₂,... p_n - основания системы счисления.

= p₁, p₂,...,p_n - диапазон представимых чисел.

Пусть p₁ =2. Обозначим через Р величину

Р= / p₁= / 2

или Р= p₂ p₃... p_n.

В СОK Р=(1, 0, 0,..., 0).

Будем оперировать числами, лежащими в диапазоне 0≤ |N| <P.

Примем в качестве нуля число Р и представим положительные числа N= |N| как N' = P + |N|, отрицательные числа N = - |N| как N' =P - |N|.

Таким образом, N' =P+N - искусственная форма (общая форма представления положительных и отрицательных чисел).

Следовательно, мы всегда будем иметь дело с положительными числами, так как |N|<P.

Но числа в интервале [0,P) в искусственной форме будут отображать отрицательные, а в интервале [P, ) - положительные числа.

Операцию сложения и вычитания можно выполнять следующим образом:

N′₁ = P + N₁,

N′₂ = P + N₂,

N′₁ + N′₂ = P + N₁ + P + N₂ = 2P + (N₁ + N₂).

Для суммы N₁ + N₂ искусственная форма:

(N₁ + N₂)′ = P + (N₁ + N₂),

(N′₁ + N′₂) = N′₁ + N′₂ - P

или

(N₁ + N₂) ′ =N′₁ + N′₂ + P, (5)

т.к. P = (1, 0, 0,..., 0).

Пример. N₁ = 17, N₂ = 41. Пусть p₁ = 2, p₂ = 3, p₃ = 5, p₄ = 7.

Образуем искусственные формы заданных чисел.

P = 3∙5∙7 = 105

N′₁ = (1, 0, 0, 0) + (1, 2, 2, 3) = (0, 2, 2, 3),

N′₂ = (1, 0, 0, 0) + (1, 2, 1, 6) = (0, 2, 1, 6),

согласно (5) (N₁ + N₂) ′ = (0, 2, 2, 3) + (0, 2, 1, 6) + (1, 0, 0, 0) = (1, 1, 3, 2) - искусственная форма N₁ + N₂, что можно проверить, перейдя к десятичной системе счисления.

(17 + 41)′ = (58)′ = 105 + 58 = (1, 0, 0, 0) + (0, 1, 3, 2) = (1, 1, 3, 2)

Пример. N₁ = 17, N₂ = - 41. Пусть p₁ = 2, p₂ = 3, p₃ = 5, p₄ = 7.

Образуем искусственные формы заданных чисел.

N′₁ = (0, 2, 2, 3),

N′₂ = (1, 0, 0, 0) - (1, 2, 1, 6) = (0, 1, 4, 1),

(N₁ + N₂)′ = (0, 2, 2, 3) + (0, 1, 4, 1) + (1, 0, 0, 0) = (1, 0, 1, 4),

(17 - 41)′ = (-24)′ = 105 - 24 = (1, 0, 0, 0) - (0, 0, 4, 3) = (1, 0, 1, 4).

Проверим, перейдя к десятичной системе счисления:

(17 - 41)′ = - (24)′ = 105 - 24 = (1, 0, 0, 0) - (0, 0, 4, 3) = (1, 0, 1, 4).

Переход из положительного числа в отрицательное и обратно, то есть образование его дополнительного кода, производится вычитанием данного числа из числа (1, p₂, p₃,...,p_n).

+41 = (1, 2, 1, 6);

- 41 = (1, 3, 5, 7) - (1, 2, 1, 6) = (0, 1, 4, 1) = 64.

Следует отметить, что если вычитаемое уже было представлено в искусственной форме, то для получения дополнительного кода надо его вычитать из числа (2, p₂,..., p_n).

---

Дата добавления: 2015-10-28