Д. Стефенс - C++. Сборник рецептов

borrow = false;

} else {

x[i] = y[i];

borrow = y[i];

}

}

}

}

template

void bitsetMultiply(std::bitset& x, const std::bitset& y) {

std::bitset tmp = x;

x.reset();

// мы хотим минимизировать количество операций сдвига и сложения

if (tmp.count() < y.count()) {

for (int i=0; i < N; i++) if (tmp[i]) bitsetAdd(x, у << i);

} else {

for (int i=0; i < N; i++) if (y[i]) bitsetAdd(x, tmp << i);

}

}

template

void bitsetDivide(std::bitset x, std::bitset y,

std::bitset& q, std::bitset& r) {

if (y.none()) {

throw std::domain_error("division by zero undefined");

}

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

#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.

Требуется выполнить операции с числами, размер которых превышает размер типа 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++() {