Доказательство дополнения двух

Question

Можно ли по индукции доказать, что дополнение двух любой строки 0 всегда будет приводить к 0 для всех последовательностей длины n?

Я пытаюсь сделать это, используя формулу значения,т.е.

значение = -a_n-1 x 2 ^ (n-1) + суммирование {i = от 0 до n} (a_i x 2 ^ i), где n = количество битов в строке

Answer 1

Вы просите доказать, что, например, дополнение двух к 1111 1111 равно 0000 0000? Если это так, вы не можете доказать это, потому что это ложь. Двойное дополнение 1111 1111 составляет 0000 0001.

    1111 1111
->  0000 0000 <- one's complement
->  0000 0001 <- add 1

Ответ на ваше редактирование: Конечно. Но вам не нужна индукция. Обращение всех битов 0_n для получения дополнения к одному дает вам 1_n, а добавление 1 переворачивает все биты обратно в ноль (1 + 1 = 10 и бит переноса просачивается до конца, где мы его отбрасываем). QED.

Answer 2

1) Определение двух дополнений к X: перевернуть биты X и сложить 1

2) Двоичная сумма двух переменных с одним битом (http://www.play -hookey.com / digital / adder.html)) (будучи b1 первой переменной и b2 второй переменной. b1: X обозначает бит X в переменной)

r1 = b1:1 XOR b2:1
carry = b1:1 AND b2:1

2.1), если оба бита равны одному b1: 1 и b2: 1

r1 = 0  (always)
carry = 1 (always)

3) Двоичная сумма двух переменных с 2 битами

r1 = b1:1 XOR b2:1 
carry1 = b1:1 AND b2:1

r2 = (b1:2 XOR b2:2) XOR carry:1
carry2 = (b1:2 AND b2:2) OR (b1:2 AND carry:1) OR (b2:2 AND carry:1)

3.1) Из 2.1 мы можем уменьшить

carry2 = (b1:2 AND b2:2) OR (b1:2 AND 1) OR (b2:2 AND 1)
carry2 = b1:2 OR b2:2

4) Быть числом Обнулить все нули.Сброс всех битов сгенерирует число «все единицы»: Единицы

5) Бит 0 XOR Anything = Anything (таблица истинности XOR)

6) Применение (1) к числу Ноль

6.1) flip

 Flipping Zero = Ones

6.2) сумма 1

 result = Ones + N_One (N_One = 00...001)
 result:1 = 0 (from 2.1)
 carry:1 = 1 (from 2.1)

6.3) Поскольку все биты из N_One кроме N_One: 1 равны нулю.

 result:n = (Ones:n XOR N_One:n) XOR carry:(n-1) (from 3)
 result:n = (Ones:n XOR 0) XOR carry:(n-1) (definition of N_One 6.2)
 result:n = Ones:n XOR carry:(n-1)

6.4) из 3.1

carry:n = Ones:n OR N_One:n -> if carry:n-1 is 1
carry:n = 1 OR 0            -> if carry:n-1 is 1
carry:n = 1                 -> if carry:n-1 is 1

Поскольку первый перенос (перенос: 1) определяется как 1 из 6.1, все переносы определяются как 1

7) из 6.3 и 6.4

 result:n = Ones:n XOR carry:(n-1)
 result:n = 1 XOR 1
 result:n = 0

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

QED

Answer 3

Разве 2 не является дополнением 111..111 просто 1 (что означает, что 111..111 представляет -1)?