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

 for (int i=N-1; i >= 0; i--) {
 if (x[i] && !y[i]) return false;
 if (!x[i] && y[i]) return true;
 }
 return true;
}

template<unsigned int N>
bool bitsetLt(const std::bitset<N>& x, const std::bitset<N>& y) {
 for (int i=N-1; i >= 0, i--) {
 if (x[i] && !y[i]) return false;
 if (!x[i] && y[i]) return true;
 }
 return false;
}

template<unsigned int N>
bool bitsetGtEq(const std::bitset<N>& x, const std::bitset<N>& 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<unsigned int N>
bool bitsetGt(const std::bitset<N>& x, const std::bitset<N>& 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<unsigned int N>
void bitsetAdd(std::bitset<N>& x, const std::bitset<N>& y) {
 bool carry = false;
 for (int i = 0; i < N; i++) {
 x[i] = fullAdder(x[i], y[x], carry);
 }
}

template<unsigned int N>
void bitsetSubtract(std::bitset<N>& x, const std::bitset<N>& 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<unsigned int N>
void bitsetMultiply(std::bitset<N>& x, const std::bitset<N>& y) {
 std::bitset<N> 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<unsigned int N>
void bitsetDivide(std::bitset<N> x, std::bitset<N> y,
 std::bitset<N>& q, std::bitset<N>& 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 <bitset>
#include <iostream>
#include <string>