С++ побитовое сложение, вычисляет окончательное количество репрезентативных битов

В настоящее время я разрабатываю утилиту, которая обрабатывает все арифметические операции над наборами битов. Набор битов может автоматически изменять размер, чтобы соответствовать любому числу, поэтому он может выполнять сложение/вычитание/деление/умножение и по модулю на очень больших наборах битов (я придумал загрузить внутрь фильм 700Mo, чтобы рассматривать его как простое целое число)

Однако я столкнулся с одной проблемой: мне нужно, чтобы мое дополнение изменило размер моего битового набора, чтобы он соответствовал точному количеству битов, необходимых после добавления, но я не мог придумать абсолютный закон, чтобы точно знать, сколько битов потребуется для хранить все, зная только количество битов, которые обрабатывают оба числа (будь то его представление положительное или отрицательное, это не имеет значения)

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

Заранее спасибо. jav974


c++ addition bit-manipulation
person jav974    schedule 29.05.2013    source источник
comment
Два варианта: Либо 2-проходный, сначала вычислите количество битов, вычислив, выполняет ли перенос самый последний бит, затем распределите результат, а затем выполните фактическое добавление. Другой вариант — выделить max(len(a),len(b)) + 1 бит для результата, что может быть на один бит слишком много, но кого это волнует...   -  person leemes    schedule 29.05.2013
comment
это намного больше, чем один бит, и это нарушает логику, которую я поставил после: / ваше решение идеально подходит для умножения, вот как я его реализовал   -  person jav974    schedule 29.05.2013

Ответы (2)


arrow_upward
2
arrow_downward

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

И вы тоже: нет никакого способа указать «только количество битов, которые обрабатывают оба числа».

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

1010111011101 +
..10111010101
..^ start here

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

1001111011101 +
..10111010101
..^ start here

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

Когда знаки различаются:

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

Это предполагает, что бит знака отделен от битов подсчета величины.

person Tony Delroy    schedule 29.05.2013
comment
Да, бит знака является отдельным при подсчете величины. - person jav974; 29.05.2013
comment
:'( это именно то, о чем я думал, я не могу позволить себе больше усилий для изменения размера набора, чем просто выполнить добавление, которое является очень легкой операцией ... в любом случае, если у вас / у кого-то еще есть другая идея или уверенность в не в состоянии знать, что с одной функцией лайнера или что-то в этом роде... - person jav974; 29.05.2013
comment
Что ж, как говорит Лимес, при добавлении значений с одинаковым знаком вы знаете в пределах 1 бита, не проверяя значения. Я понимаю, что ваш существующий код может не справляться с начальными нулями, но, возможно, его стоит изменить. Учитывая два фактически случайных числа, подходы к сканированию, как правило, имеют примерно 50/50 шансов разрешить себя с каждым дополнительным битом, который вы проверяете, поэтому амортизированная стоимость низка, но легко представить, что кто-то использует это таким образом, который будет постоянно вызывать почти наихудший результат. -производительность корпуса. - person Tony Delroy; 29.05.2013
comment
@ jav974: одна вещь, которая меня только что поразила ... по крайней мере, для добавления с другим знаком, сканирование, выполненное, чтобы увидеть, сколько цифр требуется для результата, на самом деле не тратится впустую - вы можете продолжить с точки, которая определена, начиная с скопировать результаты во вновь выделенный буфер результатов. Это по-прежнему O (n) по количеству битов и на самом деле не медленнее, чем если бы вы заранее знали количество битов в результате. - person Tony Delroy; 29.05.2013
comment
под и на самом деле не медленнее я имею в виду после этого не медленнее - т.е. как только количество битов известно, оставшаяся работа такая же, как если бы вы знали количество битов заранее . - person Tony Delroy; 29.05.2013

arrow_upward
0
arrow_downward

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

Вот объяснение с использованием беззнакового символа:

Для максимального беззнакового символа:

   11111111 (255)
+  11111111 (255)
= 111111110 (510)

Естественно, если max + max = (биты max + 1), то для x и y между 0 и max биты результата равны max + 1 (очень максимум)

это работает так же с целыми числами со знаком.

person jav974    schedule 29.05.2013