2s комплимент общая форма

Question

Предположим, у меня есть система, которая имеет целые числа, которые работают в mod n. Таким образом, мои целые числа, добавляющие один к n-1, фактически равны нулю.

Предположим, что вы определяете, что двойной комплимент числа является числом при добавлении к себе, равен нулю. То есть:

x + C(x) = 0 (here C(x) is the twos compliment of x) 

Что я должен делать, чтобы получить два комплимента x?

Реальная проблема:

Если х число в двоичной системе я мог бы просто инвертировать все биты х, а затем добавьте к этому номеру.

Это немного сложнее, если х означает число трианов. Проблема заключается в том, что он не соответствует четному количеству бит, поэтому вы пытаетесь перевернуть 2/3 бит или что-то еще, что я не знаю, что будет означать физически.

Итак, мой вопрос заключается в следующем: как я могу взять комплимент двух разных произвольных оснований?

Answer 1

я буду считать, что вы работаете на базе s для некоторого целого s > 0 и что вы пытаетесь выразить величины по модулю s^(n+1) для некоторого фиксированного целого n > 0. Другими словами, используйте не более n+1 мест (или цифр).

Таким образом, вы представляете целые числа в этой системе в качестве последовательностей [xn ... x0] где каждый xi является цифрой между 0 и s-1. Например, если s=3 и n=4, представление [01201] будет соответствовать десятичному числу 0*3^4 + 1*3^3 + 2*3^2 + 0*3^1 + 1*3^0 = 27 + 18 + 1 = 46.

Вообще говоря десятичное значение представления выше будет:.

x = xn*s^n + ... + x0*s^0 

Теперь ваша задача состоит в нахождении представления -x по модулю s^(n+1) (помните, что мы только можем использовать s+1 «цифры»

определить для каждой цифры xi его дополнение кs как

c(xi) = s - 1 - xi 

Обратите внимание, что в двоичном случае, когда s=2, дополнение к 2 соответствует тому же определению. Также обратите внимание, что

xi + c(xi) = s - 1           eq(1) 

Теперь позвольте мне использовать более простое обозначение здесь и вызвать yi = c(xi). Тогда последовательность

y = [yn ... y0] 

является то, что мы могли бы назвать дополнения к s из x.Также представлено сообщение -x - 1 по модулю s^(n+1) и поэтому для получения -x вам нужно будет добавить только 1 в y. Например, в случае x=[01201] мы имели бы y=[21021], потому что цифры цифр 3-1=2 в каждом положении.

Причина проста:

[yn ... y0] + [xn ... x0] 
      = yn*s^n + ... + y0*s^0 + xn*s^n + ... + x0*s^n 
      = (yn+xn)*s^n + ... + (y0+x0)*s^0 
      = (s-1)*sˆn + ... + (s-1)*s^0    ; by eq(2) 
      = s^(n+1) + ... + sˆ1 - (s^n + ... + s^0) 
      = s^(n+1) - 1 
      = -1 modulo s^(n+1) 

Итак, все работает так же, как они работают, когда s=2 и, скажем, по модулю 2^32 (32 бита). В этом смысле нет ничего особенного в двоичном случае.