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

 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

#include

#include

using namespace std;

int main() {

 bitset<10> bits1(string("100010001"));

 bitset<10> bits2(string("000000011"));

 bitsetAdd(bits1, bits2);

 cout << bits1.to_string, allocator >() << endl;

}

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

0100010100

Обсуждение

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

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

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

Смотри также

Рецепт 11.20.

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

Проблема

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

Решение

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

Пример 11.38. big_int.hpp

#ifndef BIG_INT_HPP

#define BIG_INT_HPP

#include

#include "bitset_arithmetic.hpp" // Рецепт 11.20

template

class BigInt {

 typedef BigInt self;

public:

 BigInt() : bits() {}

 BigInt(const self& x) : bits(x.bits) {}

 BigInt(unsigned long x) {

  int n = 0;

  while (x) {

   bits[n++] = x & 0x1;

   x >>= 1;

  }

 }

 explicit BigInt(const std::bitset& x) bits(x) {}

 // открытые функции

 bool operator[](int n) const { return bits[n]; }

 unsigned long toUlong() const { return bits.to_ulong(); }

 // операторы

 self& operator<<=(unsigned int n) {

  bits <<= n;

  return *this;

 }

 self& operator>>=(unsigned int n) {

  bits >>= n;

  return *this;

 }

 self operator++(int) {

  self i = *this;

  operator++();

  return i;

 }

 self operator--(int) {

  self i = *this;

  operator--();

  return i;

 }

 self& operator++() {

  bool carry = false;

  bits[0] = fullAdder(bits[0], 1, carry);