C++. Сборник рецептов

 q.reset();
 r.reset();
 if (x.none()) {
  return;
 }
 if (x == y) {
  q[0] = 1;
  return;
 }
 r = x;
 if (bitsetLt(x, y)) {
  return;
 }
 // подсчитать количество значащих цифр в делителе и делимом
 unsigned int sig_x;
 for (int i=N-1; i>=0; i--) {
  sig_x = i;
  if (x[i]) break;
 }
 unsigned int sig_y;
 for (int i=N-1; i>=0; i--) {
  sig_y = i;
  if (y[i]) break;
 }
 // выровнять делитель по отношению к делимому
 unsigned int n = (sig_x — sig_y);
 y <<= n;
 // обеспечить правильное число шагов цикла
 n += 1;
 // удлиненный алгоритм деления со сдвигом и вычитанием
 while (n--) {
  // сдвинуть частное влево
  if (bitsetLtEq(y, r)) {
   // добавить новую цифру к частному
   q[n] = true;
   bitset.Subtract(r, y);
  }
  // сдвинуть делитель вправо
  y >>= 1;
 }
}

Пример 11.37 показывает, как можно использовать заголовочный файл bitset_arithmetic.hpp.

Пример 11.37. Применение функций bitset_arithmetic.hpp

#include 'bitset_arithmetic.hpp'
#include <bitset>
#include <iostream>
#include <string>
using namespace std;
int main() {
 bitset<10> bits1(string('100010001'));
 bitset<10> bits2(string('000000011'));
 bitsetAdd(bits1, bits2);
 cout << bits1.to_string<char, char_traits<char>, allocator<char> >() << endl;
}

Программа примера 11.37 выдает следующий результат.

0100010100

Обсуждение

Шаблон класса bitset содержит основные операции по манипулированию битовыми наборами, но не обеспечивает арифметические операции и операции сравнения. Это объясняется тем, что в библиотеке нельзя заранее точно предвидеть, какой числовой тип будет использоваться для представления произвольного битового набора согласно ожиданиям программиста.

В функциях примера 11.36 считается, что bitset представляет собой целый тип без знака, и здесь обеспечиваются операции сложения, вычитания, умножения, деления и сравнения. Эти функции могут составить основу для представления специализированных целочисленных типов, и именно для этого они используются в рецепте 11.20.

В примере 11.36 я использовал не самые эффективные алгоритмы. Я применил самые простые алгоритмы, потому что их легче понять. В существенно более эффективной реализации использовались бы аналогичные алгоритмы, которые работали бы со словами, а не с отдельными битами.

Смотри также

Рецепт 11.20.

11.20. Представление больших чисел фиксированного размера

Проблема

Требуется выполнить операции с числами, размер которых превышает размер типа long int.

Решение

Шаблон BigInt в примере 11.38 использует bitset из заголовочного файла <bitset> для того, чтобы можно было представить целые числа без знака в виде набора бит фиксированного размера, причем количество бит определяется параметром шаблона.

Пример 11.38. big_int.hpp

#ifndef BIG_INT_HPP
#define BIG_INT_HPP
#include <bitset>
#include 'bitset_arithmetic.hpp' // Рецепт 11.20
template<unsigned int N>
class BigInt {
 typedef BigInt self;
public:
 BigInt() : bits() {}
 BigInt(const self& x) : bits(x.bits) {}