Битовые манипуляции для больших целочисленных классов?

У меня проблема с алгоритмом для большого целочисленного класса на С++. Моя первоначальная идея заключалась в использовании массивов/списков, но это очень неэффективно. Затем я обнаружил такие вещи, как следующий класс: http://www.codeproject.com/KB/cpp/CppIntegerClass.aspx

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

В основном мой вопрос: как использовать манипуляции с битами для создания большого целочисленного класса? Как это работает??

Спасибо!


c++ bit-manipulation biginteger
person Lockhead    schedule 13.12.2010    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

По моему опыту, самая очевидная битовая вещь, необходимая при реализации чего-то подобного, — это битовое тестирование для проверки переполнения. Допустим, вы представляете свое большое двоичное число в виде массива uint16_t, то есть фрагментов по 16 бит. При реализации сложения вы начнете с наименее значащего конца обоих чисел и сложите их. Если сумма больше 65 535, вам нужно «перенести» единицу в следующую uint16_t, как при сложении десятичных чисел по одной цифре за раз.

Это можно реализовать с помощью такого теста:

const uint16_t *number1;
const uint16_t *number2;

/* assume code goes here to set up the number1 and number2 pointers. */

/* Compute sum of 16 bits. */
uint16_t carry = 0;
uint32_t sum = number1[0] + number2[0];

/* One way of testing for overflow: */
if (sum & (1 << 16))
 carry = 1;

Здесь выражения 1 << 16 создают маску, сдвигая 1 шестнадцать шагов влево. Побитовый оператор & и проверяет сумму по маске; результат будет ненулевым (т. е. истинным в C++), если бит 16 установлен в sum.

person unwind    schedule 13.12.2010
comment
Но не будет ли результат слишком большим для любого стандартного типа данных? Как мне справиться с этим? - person Lockhead; 13.12.2010