bitset_arithmetic.hpp
----------------------------------
#include <stdexcept>
#include <bitset>
bool fullAdder(bool b1, bool b2, bool& carry) {
bool sum = (b1 ^ b2) ^ carry;
carry = (b1 && b2) || (b1 && carry) || (b2 && carry);
return sum;
}
bool fullSubstractor(bool b1, bool b2, bool& borrow) {
bool diff;
if (borrow) {
diff = !(b1 ^ b2);
borrow = !b1 || (b1 && b2);
}
else {
diff = b1 ^ b2;
borrow = !b1 && b2;
}
return diff;
}
template<unsigned int N>
bool bitsetLtEq(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 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[i], 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();
// we want to minimize the number of time we shift and add
if (tmp.count() < y.count()) {
for (int i=0; i < N; i++)
if (tmp[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;
}
r = x;
if (bitsetLt(x, y)) {
return;
}
// count significant digits in divisor and dividend
unsigned int sig_x;
for (int i=N-1; i>=0; i--) {
sig_x = 1;
if (x[i]) break;
}
unsigned int sig_y;
for (int i=N-1; i>=0; i--) {
sig_y = 1;
if (y[i]) break;
}
// align the divisor with the dividend
unsigned int n = (sig_x - sig_y);
y <<= n;
// make sure the loop executes the right number of times
n += 1;
// long division algorithm, shift, and subtract
while (n--)
{
// shift the quotient to the left
if (bitsetLtEq(y, r))
{
// add a new digit to quotient
q[n] = true;
bitsetSubtract(r, y);
}
// shift the divisor to the right
y >>= 1;
}
}
----------------------------------------
all these example code, you can download directly from
http://examples.oreilly.com/9780596007614/
-----
11-38
11-39
11-36
----------------------------------------------------------------
since my g++ compiler work at cplusplus.com 's example code, so It prove that maybe somewhere wrong on that book's example
code.
Hope all these are sufficient enough for experts to debug
sincerely, Eric