473,897 Members | 3,084 Online

# Diggins PDP #1.2 : Binary Arithmetic Algorithms

// binary_aritmeti c.hpp
// Diggins PDP (Public Domain Post) #1.2
// by Christopher Diggins, May 24, 2005
//
// Comment:
// Provides several algorithms for unsigned binary arithmetic
//
// Changes:
// Now includes a full_subtractor

#ifndef BINARY_ARITHMET IC_HPP
#define BINARY_ARITHMET IC_HPP

#include <stdexcept>
#include <cassert>
#include <limits>

namespace cdiggins
{
template<class T>
T logical_xor(con st T& x, const T& y) {
return (x || y) && !(x && y);
}

bool full_adder(bool b1, bool b2, bool& carry)
{
bool sum = (b1 ^ b2) ^ carry;
carry = (b1 && b2) || (b1 && carry) || (b2 && carry);
return sum;
}

bool full_subtractor (bool b1, bool b2, bool& borrow)
{
bool diff;
if (borrow)
{
diff = !logical_xor(b1 , b2);
borrow = !b1 || (b1 && b2);
}
else
{
diff = logical_xor(b1, b2);
borrow = !b1 && b2;
}
return diff;
}

template<typena me T>
unsigned int count_significa nt_digits(T x) {
unsigned int n = 0;
while (x > 0) {
++n;
x >>= 1;
}
return n;
}

template<typena me T>
T multiply(T x, T y)
{
// this multiply accepts only non-negative integer values
assert(x >= 0);
assert(y >= 0);
T ret = 0;
while (y > 0)
{
if ((y & 1) == 1) {
ret += x;
}
y >>= 1;
x <<= 1;
}
return ret;
}

template<typena me T>
void divide(T x, T y, T& q, T& r)
{
// this divide accepts only non-negative integer values
assert(x >= 0);
assert(y >= 0);
if (y == 0) {
throw std::domain_err or("division by zero undefined");
}
if (x == 0) {
q = 0;
r = 0;
return;
}
if (y == x) {
q = 1;
r = 0;
return;
}

q = 0;
r = x;

if (y > x) {
return;
}

// count significant digits in divisor and dividend
unsigned int sig_x = count_significa nt_digits(x);
unsigned int sig_y = count_significa nt_digits(y);

// check against my own stupidity
assert(sig_x >= sig_y);

// align the divisor with the dividend
unsigned int n = (sig_x - sig_y);
y <<= n;

n += 1; // make sure the loop executes the right number of times

// long division algorithm, shift and subtract
while (n--)
{
q <<= 1; // shift the quotient to the left
if (y <= r)
{
q |= 1; // add a new digit to quotient
r = r - y; // subtract from the remained
}
y >>= 1; // shift the divisor to the right
}
}

template<typena me T>
T divide_quotient (const T& x, const T& y) {
T q;
T r;
divide(x, y, q, r);
return q;
}

template<typena me T>
T divide_remainde r(const T& x, const T& y) {
T q;
T r;
divide(x, y, q, r);
return r;
}
}

namespace binary_arithmet ic_test
{
using namespace cdiggins;

void test(bool b) {
if (!b) {
throw std::runtime_er ror("test failed");
}
}

void test_divide() {
for (unsigned char i=0; i < 0xFF; i++) {
for (unsigned char j=1; j < 0xFF; j++) {
test(divide_quo tient(i, j) == i / j);
test(divide_rem ainder(i, j) == i % j);
}
}
}

void test_multiply() {
for (int i=0; i < 0xFF; i++) {
for (int j=0; j < 0xFF; j++) {
test(multiply(i , j) == i * j);
}
}
}

bool carry = true;
test(full_adder (true, true, carry) == true);
test(carry == true);
test(full_adder (true, false, carry) == false);
test(carry == true);
test(full_adder (false, true, carry) == false);
test(carry == true);
test(full_adder (false, false, carry) == true);
test(carry == false);
test(full_adder (true, false, carry) == true);
test(carry == false);
test(full_adder (false, true, carry) == true);
test(carry == false);
test(full_adder (true, true, carry) == false);
test(carry == true);
}

void test_full_subtr actor() {
bool borrow = false;
test(full_subtr actor(true, true, borrow) == false);
test(borrow == false);
test(full_subtr actor(true, false, borrow) == true);
test(borrow == false);
test(full_subtr actor(false, false, borrow) == false);
test(borrow == false);
test(full_subtr actor(false, true, borrow) == true);
test(borrow == true);
test(full_subtr actor(true, true, borrow) == true);
test(borrow == true);
test(full_subtr actor(false, true, borrow) == false);
test(borrow == true);
test(full_subtr actor(false, false, borrow) == true);
test(borrow == true);
test(full_subtr actor(true, false, borrow) == false);
test(borrow == false);
}

void test_main()
{
test_divide();
test_multiply() ;
test_full_subtr actor();
}
}

#endif

Jul 23 '05 #1
0 2516

This thread has been closed and replies have been disabled. Please start a new discussion.