Добавление в битовый массив

Question

В моей программе я использую BitArrays для представления 160-битных чисел. Я хочу иметь возможность складывать, вычитать, увеличивать и уменьшать эти числа, каков алгоритм для этого?

В данный момент меня не интересуют умножение и деление, но я могу быть в будущем, поэтому бонусные баллы за это.

Я реализую в C #, но псевдокод хорошо, если вы не знакомы с языком

Answer 1

Поскольку вы используете C #, вы можете взглянуть на BigInteger , который был добавлен в недавно выпущенный .NET 4.0.

Answer 2

Есть лучший способ, математика в старших классах школы использует стандартный подход «волнистого переноса», у которого есть недостаток, заключающийся в том, что вы должны работать по одному. «Продолжай смотреть вперед» - это термин, который вы хотите Google или просто читать:

http://en.wikipedia.org/wiki/Carry_look-ahead_adder

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

Answer 3

Массивы 8-битных байтов без знака могут сделать это намного проще. Тогда вам просто нужно сложить / вычесть из младшего байта и обработать перенос.

Существует множество информации о двоичном добавлении .

В качестве альтернативы, вы можете избавить себя от некоторой боли и повторно использовать кто-то пропустит: -)

Answer 4

Увеличивать и уменьшать вы можете писать вручную, и, добавляя, вычитая, вы можете сделать это с помощью метода записи. Вы знаете этот метод, потому что вы используете в базовой школе этот метод, работающий на всех числовых системах не только для базовых 2 и 10.

Как это:

100100
010110 +
--------
111010