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) {}
BigInt(unsigned long x) {
int n = 0;
while (x) {
bits[n++] = x & 0x1;
x >>= 1;
}
}
explicit BigInt(const std::bitset<N>& 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);
for (int i = 1; i < N; i++) {
bits[i] = fullAdder(bits[i], 0, carry);
}
return *this;
}
self& operator--() {
bool borrow = false;
bits[0] = fullSubtractor(bits[0], 1, borrow);
for (int i = 1; i < N; i++) {
bits[i] = fullSubtractor(bits[i], 0, borrow);
}
return *this;
}
self& operator+=(const self& x) {
bitsetAdd(bits, x.bits);
return *this;
}
self& operator-=(const self& x) {
bitsetSubtract(bits, x.bits);
return *this;
}
self& operator*=(const self& x) {
bitsetMultiply(bits, x.bits);
return *this;
}
self& operator/=(const self& x) {
std::bitset<N> tmp;
bitsetDivide(bits, x.bits, bits, tmp);
return *this;
}
self& operator%=(const self& x) {
std::bitset<N> tmp;
bitsetDivide(bits, x.bits, tmp, bits);
return *this;
}
self operator~() const { return ~bits; }
self& operator&=(self x) { bits x.bits; return *this; }
self& operator|=(self x) { bits x.bits; return *this; }
self& operator~=(self x) { bits ~= x.bits; return *this; }
// дружественные функции
friend self operator<<(self x, unsigned int n) { return x <<= n; }
friend self operator>>(self x, unsigned int n) { return x >>= n; }
friend self operator+(self x, const self& y) { return x += y; }
friend self operator-(self x, const self& y) { return x -= y; }
friend self operator*(self x, const self& y) { return x *= y; }
friend self operator/(self x, const self& y) { return x /= y; }
friend self operator%(self x, const self& y) { return x %= y; }
friend self operator^(self x, const self& y) { return x ^= y; }
friend self operator&(self x, const self& y) { return x &= y; }