Являются ли эти дополнения дистрибутивными?

Question

Я знаю, что ассоциативной и коммутативной:

То есть,

(~x1 + ~x2) + ~x3 = ~x1 + (~x2 + ~x3) 

и

~x1 + ~x2 = ~x2 + ~x1 

Однако, за исключением случаев, которые я пробовал, это, кажется, не дистрибутивной, т.е.

~x1 + ~x2 != ~(x1 + x2) 

Это правда? Есть ли доказательство?

У меня есть C код следующим образом:

int n1 = 5; 
int n2 = 3; 
result = ~n1 + ~n2 == ~(n1 + n2); 

int calc = ~n1; 
int calc0 = ~n2; 
int calc1 = ~n1 + ~n2; 
int calc2 = ~(n1 + n2); 

printf("(Part B: n1 is %d, n2 is %d\n", n1, n2); 
printf("Part B: (calc is: %d and calc0 is: %d\n", calc, calc0); 
printf("Part B: (calc1 is: %d and calc2 is: %d\n", calc1, calc2); 
printf("Part B: (~%d + ~%d) == ~(%d + %d) evaluates to %d\n", n1, n2, n1, n2, result); 

который дает следующий результат:

Part B: (n1 is 5, n2 is 3 
Part B: (calc is: -6 and calc0 is: -4 
Part B: (calc1 is: -10 and calc2 is: -9 
Part B: (~5 + ~3) == ~(5 + 3) evaluates to 0 

Answer 1

De Morgan's laws От:

~(x1 + x2) = ~x1 * ~x2 

Answer 2

Проверьте статью Wikiepdia на Ones' complement. Добавление в дополнение дополняет конец, где вы должны добавить бит переполнения к младшему бит.

С ~ (НЕ) эквивалентен - (нивелирует) в дополнении один, мы можем переписать как:

-x1 + -x2 = -(x1 + x2) 

, который является правильным.

Answer 3

Компенсация используется для представления отрицательных и положительных чисел в регистрах фиксированной ширины. Для распространения над дополнением должно применяться следующее: ~a + ~b = ~(a + b). Состояние OP + представляет собой добавление двух двоичных чисел. Это само по себе расплывчато, однако, если мы считаем, что это означает добавление двоичных чисел без знака, то нет, один комплимент не является дистрибутивным.

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

Посмотрите, что ~0 + ~0 != ~(0 + 0): ~0 равно нулю. Однако ~0 представлены всеми. Добавление его к себе удваивает его - то же, что и сдвиг влево - и, таким образом, вводит нуль в правой руке. Но это уже не один из двух нулей.

Однако 0 равно нулю, а 0 + 0 также равно нулю, и таким образом ~(0 + 0). Но левая сторона не равна нулю, поэтому распределение не выполняется.

С другой стороны, ... Рассмотрите два комплимента: переверните все биты и добавьте один. Если уделить особое внимание негативам в своем комплименте, то эта версия «двоичного дополнения» похожа на комплимент двух и является дистрибутивной, так как вы в итоге получили знакомый quotient ring, как и в двух комплиментах.

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

Answer 4

[Я знаю, что это на самом деле старое, но у меня был тот же вопрос, и так как верхние ответы были противоречивыми ...]

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

Все, что вы используете для хранения суммы, требует большего объема памяти, чем то, что вы суммируете, чтобы не уронить бит переноса. Затем сверните биты переноса обратно в число бит, которое вы используете, чтобы сохранить ваши операнды, чтобы получить правильную сумму. Это называется «концевой перенос» в арифметике комплимента.

Из статьи Википедии (https://en.wikipedia.org/wiki/Signed_number_representations#Ones «_complement):

Чтобы сложить два числа, представленные в этой системе, один делает обычный двоичный дополнение, но в этом случае необходимо сделать конец вокруг нести: это , добавьте любой результат переноса в итоговую сумму. Чтобы понять, почему это необходимо, рассмотрим следующий пример, показывающий случай добавления -1 (11111110) до +2 (00000010):

 binary decimal 
    11111110  –1 
+ 00000010  +2 
───────────  ── 
    1 00000000  0 ← Not the correct answer 
      1  +1 ← Add carry 
───────────  ── 
    00000001  1 ← Correct answer 

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

Я немного изменил код, чтобы облегчить выполнение самой математики для проверки и проверки работоспособности. Это может потребовать немного больше мысли с использованием целочисленных типов данных со знаком или для учета заимствований за границей вместо их переноса. Я не зашел так далеко, так как мое приложение касается контрольных сумм (т. Е. Без знака и только для добавления).

unsigned short n1 = 5; //using 16-bit unsigned integers 
unsigned short n2 = 3; 

unsigned long oc_added = (unsigned short)~n1 + (unsigned short)~n2; //32bit 
/* Fold the carry bits into 16 bits */ 
while (oc_added >> 16) 
    oc_added = (oc_added & 0xffff) + (oc_added >> 16); 

unsigned long oc_sum = ~(n1 + n2); //oc_sum has 32 bits (room for carry) 
/* Fold the carry bits into 16 bits */ 
while (oc_sum >> 16) 
    oc_sum = (oc_sum & 0xffff) + (oc_sum >> 16); 

int result = oc_added == oc_sum; 

unsigned short calc = ~n1; 
unsigned short calc0 = ~n2; 
unsigned short calc1 = ~n1 + ~n2; //loses a carry bit 
unsigned short calc2 = ~(n1 + n2); 

printf("(Part B: n1 is %d, n2 is %d\n", n1, n2); 
printf("Part B: (calc is: %d and calc0 is: %d\n", calc, calc0); 
printf("Part B: (calc1 is: %d and calc2 is: %d\n", calc1, calc2); 
printf("Part B: (~%d + ~%d) == ~(%d + %d) evaluates to %d\n", n1, n2, n1, n2, result);