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

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

0 голосов
/ 13 декабря 2010

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

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

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

Спасибо!

1 Ответ

1 голос
/ 13 декабря 2010

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

Отображение этого на язык программирования, такой как 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 ++), если бит * установлен в sum.

...