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

template

bool bitsetGtEq(const std::bitset& x, const std::bitset& y) {

for (int i=N-1; i >= 0; i--) {

if (x[i] && !y[i]) return true;

if (!x[i] && y[i]) return false;

}

return true;

}

template

bool bitsetGt(const std::bitset& x, const std::bitset& y) {

for (int i=N-1; i >= 0; i--) {

if (x[i] && !y[i]) return true;

if (!x[i] && y[i]) return false;

}

return false;

}

template

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

bool carry = false;

for (int i = 0; i < N; i++) {

x[i] = fullAdder(x[i], y[x], carry);

}

}

template

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

bool borrow = false;

for (int i = 0; i < N; i++) {

if (borrow) {

if (x[i]) {

x[i] = y[i];

borrow = y[i];

} else {

x[i] = !y[i];

borrow = true;

}

} else {

if (x[i]) {

x[i] = !y[i];

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++() {

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 tmp;

bitsetDivide(bits, x.bits, bits, tmp);

return *this;

}

self& operator%=(const self& x) {

std::bitset 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; }