В моей программе я использую BitArrays для представления 160-битных чисел. Я хочу иметь возможность добавлять, вычитать, увеличивать и уменьшать эти числа, каков алгоритм для этого?Добавление в бит-массив
На данный момент меня не интересуют размножение и деление, но я мог бы быть в будущем, поэтому бонусные баллы за это.
Я реализации в C#, но псевдокод хорошо, если вы не знакомы с языком
Поскольку вы используете C#, вы можете захотеть взглянуть на BigInteger, который был добавлен в недавно выпустила .NET 4.0.
Омг, это так полезно O_O Thankyou! – Martin
увеличивающие и уменьшающие вы можете написать вручную, и добавление, substracing вы можете сделать это с помощью метода записи. Вы знаете этот метод, потому что вы используете в базовой школе этот метод работает на всех цифровых системах, не только для основания 2 и 10.
Как это:
100100
010110 +
--------
111010
Массивы беззнаковых 8-битных байтов может сделать это намного Полегче. Тогда вам просто нужно добавить/вычесть из младшего значащего байта и переносить дескриптор.
Существует много информации на binary addition.
В качестве альтернативы, вы можете сэкономить некоторую боль и re-use чужого imlpementation :-)
Как выглядит массив байтов? Это быстрее, но алгоритмы в основном одинаковы, независимо от того, используете ли вы биты, байты, слова, что угодно. –
Действительно, перенос является основной проблемой при добавлении, и это то же самое с битами или байтами. – Martin
. Я не так хорошо знаком с реализацией C# в BitArray, но догадался из вашего сообщения, что он не включает арифметические операторы? ..unsigned char's _do_ имеют собственные арифметические операторы, которые вы можете использовать. –
Существует лучший способ, математика средней школы использует стандартный подход «пульсация», который имеет тот недостаток, что вам приходится работать по одному бит за раз. «Carry смотреть вперед» это термин, который вы хотите Google или просто читать:
http://en.wikipedia.org/wiki/Carry_look-ahead_adder
Она группирует биты и делает некоторые умные логики, чтобы значительно сократить количество шагов, чтобы добавить номера вместе. Существует параллельный процесс вычитания. Я просто не могу запомнить имя.
Carry look-ahead не сохраняет никаких шагов, на самом деле он использует больше шагов. Полезно только увеличивать параллелизм сложения, что не очень полезно в программном обеспечении для размеров номеров, о которых говорит плакат (он очень популярен в аппаратных сумматорах). Добавление переноса может потенциально быть полезным, если на плакате есть много номеров, которые нужно добавить (или будет делать умножение), но это звучит не так. –
BitArrays - не лучший инструмент для расчетов. –
То же, что и в средней школе, с двоичным, а не десятичным (или если вы хотите лучше воспользоваться оборудованием, в базе 2 ** 16, 2 ** 32 или что вам удобно). –
Я знаю, что бит-массивы не идеальны, но огромное количество моего кода выполняет индивидуальное свертывание бит, и я очень редко делаю какие-либо арифметические операции. Следовательно, бит-массивы – Martin