Почему х & amp; (-x) равна наибольшей степени 2, делящему x? (C ++) [дубликат]

Позволяет получить ответ 10-12 в двоичной форме с использованием 8 бит: что мы действительно сделаем, это 10 + (-12)

Нам нужно получить часть комплимента из 12, чтобы вычесть его из 10 12 в двоичном формате 00001100. 10 в двоичном формате - 00001010.

Чтобы получить часть комплимента из 12, мы просто отменим все биты, затем добавим 1. 12 в двоичном обратном - 11110011. Это также обратный код (дополнение). Теперь нам нужно добавить один, который теперь 11110100.

Итак, 11110100 - это комплимент 12! Легко, когда вы думаете об этом таким образом.

Теперь вы можете решить вышеупомянутый вопрос 10-12 в двоичной форме.

00001010
11110100
-----------------
11111110  

Как и большинство объяснений, которые я видел, те, что выше, понятны о том, как работать с дополнением 2, но на самом деле не объясняют, что они математически. Я попытаюсь сделать это, по крайней мере, для целых чисел, и я расскажу о некоторых предпосылках, которые, вероятно, знакомы в первую очередь.

Вспомните, как это работает для десятичного: & nbsp; & nbsp; 2345 - способ записи & nbsp; ; & nbsp; 2 & times; 103 + 3 & times; 102 + 4 & times; 101 + 5 & times; 100.

Таким же образом двоичный метод является способом записи чисел, используя только 0 и 1, следуя одной и той же общей идее, но заменяя те 10s выше на 2s. Затем в двоичном формате 1111 является способом записи & nbsp; & nbsp; 1 & times; 23 + 1 & times; 22 + 1 & times; 21 + 1 & times; 20, и если вы это сделаете, то получится равным 15 (база 10). Это потому, что он равен 8 + 4 + 2 + 1 = 15.

Это хорошо и полезно для положительных чисел. Это даже работает для отрицательных чисел, если вы готовы просто придерживаться знака минус перед ними, как люди делают с десятичными числами. Это можно сделать даже на компьютерах, но я не видел таких компьютеров с начала 1970-х годов. Я оставлю причины для другого обсуждения.

Для компьютеров оказалось более эффективным использовать представление дополнения для отрицательных чисел. И вот что-то, что часто упускается из виду. Дополняющие обозначения включают в себя какой-то разворот цифр числа, даже подразумеваемых нулей, которые идут до нормального положительного числа. Это неудобно, потому что возникает вопрос: все они? Это может быть бесконечное число цифр, которые нужно учитывать.

К счастью, компьютеры не представляют бесконечности. Числа ограничены определенной длиной (или шириной, если хотите). Итак, вернемся к положительным двоичным числам, но с конкретным размером. Я буду использовать 8 цифр («бит») для этих примеров. Таким образом, наш двоичный номер действительно будет & nbsp; 00001111or & nbsp; & nbsp; 0 & times; 27 + 0 & times; 26 + 0 & times; 25 + 0 & times; 24 + 1 & times; 23 + 1 & times; 22 + 1 & times; 21 + 1 & times; 20

Чтобы сформировать отрицательное дополнение дополнения 2, мы сначала дополним все (двоичные) цифры до формы 11110000 и добавим 1 к форме 11110001, но как мы должны понимать, что это означает -15 ?

Ответ заключается в том, что мы меняем значение бит высокого порядка (самый левый). Этот бит будет 1 для всех отрицательных чисел. Изменение будет заключаться в изменении знака его вклада в значение числа, в котором оно появилось. Итак, теперь наш 11110001 понимается как & nbsp; & nbsp; -1 & times; 27 + 1 & times; 26 + 1 & times; 25 + 1 & times; 24 + 0 & times; 23 + 0 & times; 22 + 0 & times; 21 + 1 & times; 20Notice, что перед выражением? Это означает, что бит знака несет вес -27, то есть -128 (основание 10). Все остальные позиции сохраняют тот же вес, что и в двоичных числах без знака.

Разработка нашего -15, это & ​​nbsp; -128 + 64 + 32 + 16 + 1 Попробуйте его на калькуляторе. это -15.

Из трех основных способов, которые я видел отрицательные числа, представленные в компьютерах, 2-го дополнения выигрывают руки для удобства в общем использовании. Впрочем, это странность. Поскольку это двоичный код, должно быть четное количество возможных комбинаций бит. Каждое положительное число может быть сопряжено с отрицательным, но есть только один ноль. Отрицание нуля приводит к нулю. Таким образом, есть еще одна комбинация, число с 1 в знаке и 0 везде. Соответствующее положительное число не будет соответствовать количеству используемых битов.

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

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

Два дополнения обнаруживаются добавлением одного к 1-м дополнению к указанному числу. Предположим, что нам нужно найти два дополнения к 10101, затем найти его дополнение, то есть 01010 добавить 1 к этому результату, то есть 01010+1=01011, что является окончательным ответом.

Интересно, может ли это быть объяснено лучше, чем статья в Википедии.

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

Сначала рассмотрим целое число без знака, записанное в 4 бита. У вас может быть следующее

0000 = 0
0001 = 1
0010 = 2
...
1111 = 15

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

Знак Величина и избыточное обозначение

Чтобы сохранить отрицательные числа, вы можете попробовать несколько вещей. Во-первых, вы можете использовать нотацию знака знака, которая назначает первый бит в качестве знакового бита для представления +/- и остальных бит для представления величины. Таким образом, используя 4 бита снова и предполагая, что 1 означает - и 0 означает +, тогда у вас есть

0000 = +0
0001 = +1
0010 = +2
...
1000 = -0
1001 = -1
1111 = -7

. Итак, вы видите проблему там? У нас положительный и отрицательный 0. Большая проблема заключается в добавлении и вычитании двоичных чисел.

Что такое

0010
1001 +
----

?

Другая система - превышение нотации . Вы можете хранить отрицательные числа, вы избавляетесь от двух проблем с нулями, но сложение и вычитание остаются трудными.

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

Преобразование десятичного в дополнение к двум

1. Преобразование числа в двоичный (пока игнорируйте знак), например. 5 - 0101, а -5 - 0101
2. Если число положительное, значит, вы закончили. например 5 - 0101 в двоичном формате с использованием двухкомпонентной нотации.
3. Если число отрицательное, то 3.1 найти дополнение (инвертировать 0 и 1), например. -5 - 0101, поэтому найти дополнение 1010 3.2 Добавить 1 в дополнение 1010 + 1 = 1011. Следовательно, -5 в дополнении 2-го порядка 1011.

Итак, что, если вы хотите do 2 + (-3) в двоичном формате? 2 + (-3) - -1. Что бы вы сделали, если бы вы использовали значение знака для добавления этих чисел? 0010 + 1101 =?

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

 2  =  0010
 -3 =  1101 +
 -------------
 -1 =  1111

Преобразование двух дополнений в десятичные

Преобразование 1111 в десятичный: / g25]

1. Число начинается с 1, поэтому оно отрицательно, поэтому мы находим дополнение 1111, которое равно 0000.
2. Добавьте 1 к 0000, и получим 0001.
3. Преобразование 0001 в десятичный, что равно 1.
4. Применить знак = -1.

Tada!

Представьте, что у вас есть конечное количество бит / триты / цифры / что угодно. Вы определяете 0, так как все цифры равны 0, и естественно подсчитывают вверх:

00
01
02
..

В конце концов вы переполнитесь.

98
99
00

У нас есть две цифры и может представлять все числа из 0 до 100. Все эти цифры положительные! Предположим, мы тоже хотим представить отрицательные числа?

То, что у нас действительно есть, - это цикл. Число до 2 равно 1. Число до 1 равно 0. Число до 0 равно ... 99 .

Итак, для простоты предположим, что любое число более 50 является отрицательным. «0» - «49» - от 0 до 49. «99» равно -1, «98» равно -2, ... «50» равно -50.

Это представление является дополнением десяти. Компьютеры обычно используют дополнение двух, что является одним и тем же, за исключением использования битов вместо цифр.

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

Вы также можете использовать онлайн-калькулятор для вычисления двоичного представления двоичного представления двоичного числа: http://www.convertforfree.com/twos-complement-calculator/

ССЫЛКА: https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

Я инвертирую все биты и добавляю 1. Программно:

  // in C++11
  int _powers[] = {
      1,
      2,
      4,
      8,
      16,
      32,
      64,
      128
  };

  int value=3;
  int n_bits=4;
  int twos_complement = (value ^ ( _powers[n_bits]-1)) + 1;

Самый простой ответ:

1111 + 1 = (1) 0000. Таким образом, 1111 должен быть -1. Тогда -1 + 1 = 0.

Это прекрасно, чтобы понять все это для меня.

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

Итак, в дополнении 2, если один равен 0x0001, тогда -1 равен 0x1111, потому что это приведет к суммарной сумме 0x0000 (с переполнением 1 ).

У меня была такая же проблема пару недель назад. Я закончил тем, что читал об этом в Интернете из разных источников, пытаясь собрать эти кусочки и написать об этом сам, чтобы убедиться, что я правильно понял. Мы используем два дополнения по двум причинам:

1. Чтобы избежать множественных представлений 0
2. Чтобы избежать отслеживания бит переноса (как в дополнении) в случае переполнения .
3. Выполнение простых операций, таких как сложение и вычитание, становится легким.

Если вы хотите более подробное объяснение этого вопроса, попробуйте статью, написанную мной здесь . Надеюсь, это поможет!

Глядя на систему дополнений двух с математической точки зрения, это действительно имеет смысл. [10]

Пример: 63 - 24 = x

Добавим дополнение к 24, которое действительно справедливо (100 - 24). В дополнение к этому, идея состоит в том, чтобы по существу «изолировать» разницу.

). Итак, все, что мы делаем, это добавление 100 по обе стороны от уравнения.

Теперь уравнение равно 100 + 63 - 24 = x + 100, поэтому мы удаляем 100 (или 10 или 1000 или что-то еще).

Из-за неудобной ситуации, заключающейся в том, чтобы вычесть одно число из длинной цепочки нулей, мы используем систему «уменьшенного радиального дополнения» в десятичной системе, дополнение девяти.

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

Пример: 99999 - 03275 = 96724

Это является причиной, после дополнения девяти мы добавляем 1. Как вы, наверное, знаете из детской математики, 9 становится 10 путем «кражи» 1. Таким образом, в основном это всего лишь десять дополнений, которые берут 1 из разницы.

In Двоичное, дополнение двух равнозначно десятому дополнению, в то время как дополнение к дополнению девяти. Основное отличие состоит в том, что вместо того, чтобы пытаться изолировать разницу с степенями десяти (добавив 10, 100 и т. Д. В уравнение), мы пытаемся изолировать разницу с степенями двух.

Это для по этой причине мы инвертируем биты. Точно так же, как наш minuend представляет собой цепочку из девяток в десятичной форме, наш minuend является цепочкой из двоичных.

Пример: 111111 - 101001 = 010110

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

Когда мы используем отрицательные двоичные числа, мы действительно просто говорим:

0000 - 0101 = x

1111 - 0101 = 1010

1111 + 0000 - 0101 = x + 1111

. Чтобы «изолировать» x, нам нужно добавьте 1, потому что 1111 - это один от 10000, и мы удаляем ведущий 1, потому что мы просто добавили его к исходной разности.

1111 + 1 + 0000 - 0101 = x + 1111 + 1

10000 + 0000 - 0101 = x + 10000

Просто удалите 10000 с обеих сторон, чтобы получить x, это базовая алгебра.

Дополнения 2: Когда мы добавляем дополнительный с 1 дополнением числа, мы получим дополнения 2. Например: 100101 это дополнение 1 011010, а дополнение 2 - 011010 + 1 = 011011 (добавив одно с дополнением 1) . Для получения дополнительной информации эта статья объясняет это графически.

Мне понравился ответ lavinio, но смещение бит добавляет некоторую сложность. Часто существует выбор движущихся битов при соблюдении знакового бита или при этом не соблюдающий знаковый бит. Это выбор между обработкой чисел как подписанных (от -8 до 7 для nibble, от -128 до 127 для байтов) или беззнаковых чисел с полным диапазоном (от 0 до 15 для nibbles, от 0 до 255 для байтов).

2 очень полезен для поиска значения двоичного файла, однако я подумал о гораздо более сжатом способе решения такой проблемы (никогда не видел, чтобы кто-либо публиковал его):

принимает двоичный код, например: 1101, который [предполагается, что пространство «1» является знаком], равным -3.

, используя дополнение 2, мы сделали бы это ... flip 1101 to 0010 ... add 0001 + 0010 ===> дает нам 0011. 0011 в положительном двоичном = 3. поэтому 1101 = -3!

Что я понял:

вместо всех щелчков и добавления, вы можете просто сделать основной метод для решения для положительного двоичного кода (скажем, 0101 ) (23 * 0) + (22 * 1) + (21 * 0) + (20 * 1) = 5.

Выполняйте точно такое же понятие с отрицательным! (с небольшим завихрением)

принимают 1101, например:

для первого числа вместо 23 * 1 = 8, do - (23 * 1) = -8.

затем продолжаем, как обычно, делать -8 + (22 * 1) + (21 * 0) + (20 * 1) = -3

Многие ответы до сих пор хорошо объясняют, почему два дополнения используются для представления отрицательного числа, но не сообщают нам, что такое номер дополнения, особенно не почему добавляется «1», а на самом деле часто добавляется неправильно путь.

Путаница возникает из-за плохого понимания определения номера дополнения. Дополнительным дополнением является недостающая часть, которая сделает что-то завершенным.

Радиус-дополнение n-го числа x в радиусе b является, по определению, b ^ n-x. В двоичном выражении 4 представляет собой 100, который имеет 3 цифры (n = 3) и радиус 2 (b = 2). Таким образом, его радиус-дополнение является b ^ n-x = 2 ^ 3-4 = 8-4 = 4 (или 100 в двоичном виде).

Однако в бинарном представлении дополнение радиуса не так просто, как получение его уменьшенного дополнения радикса, которое определяется как (b ^ n-1) -y, всего на 1 меньше, чем у дополнения radix. Чтобы получить уменьшенное дополнение радикса, вы просто переворачиваете все цифры.

100 -> 011 (уменьшенный (один) радиус-дополнение)

, чтобы получить дополнение radix (two), мы просто добавьте 1, как определено определение.

011 +1 -> 100 (дополнение двух).

Теперь, используя это новое понимание, давайте взглянем на пример, данный Винсентом Ramdhanie (см. Выше второй ответ)

/ * начало Vincent

Преобразование 1111 в десятичный:

Число начинается с 1, поэтому оно отрицательное, поэтому мы найдите дополнение 1111, которое равно 0000. Добавьте 1 к 0000, и мы получим 0001. Преобразуем 0001 в десятичную, что равно 1. Примените знак = -1. Tada!

end of Vincent * /

Следует понимать как

Число начинается с 1, поэтому оно отрицательное. Итак, мы знаем, что это два дополнения к некоторому значению x. Чтобы найти х, представленное его дополнением, нам сначала нужно найти его дополнение.

дополнение двух х: 1111 дополнение к х: 1111-1 -> 1110; x = 0001, (перевернуть все цифры)

применить знак -, а ответ = -x = -1.