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

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