472,358 Members | 1,950 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,358 software developers and data experts.

Diggins PDP #1.2 : Binary Arithmetic Algorithms

// binary_aritmetic.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_ARITHMETIC_HPP
#define BINARY_ARITHMETIC_HPP

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

namespace cdiggins
{
template<class T>
T logical_xor(const 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<typename T>
unsigned int count_significant_digits(T x) {
unsigned int n = 0;
while (x > 0) {
++n;
x >>= 1;
}
return n;
}

template<typename 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<typename 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_error("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_significant_digits(x);
unsigned int sig_y = count_significant_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<typename T>
T divide_quotient(const T& x, const T& y) {
T q;
T r;
divide(x, y, q, r);
return q;
}

template<typename T>
T divide_remainder(const T& x, const T& y) {
T q;
T r;
divide(x, y, q, r);
return r;
}
}

namespace binary_arithmetic_test
{
using namespace cdiggins;

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

void test_divide() {
for (unsigned char i=0; i < 0xFF; i++) {
for (unsigned char j=1; j < 0xFF; j++) {
test(divide_quotient(i, j) == i / j);
test(divide_remainder(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);
}
}
}

void test_full_adder() {
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_subtractor() {
bool borrow = false;
test(full_subtractor(true, true, borrow) == false);
test(borrow == false);
test(full_subtractor(true, false, borrow) == true);
test(borrow == false);
test(full_subtractor(false, false, borrow) == false);
test(borrow == false);
test(full_subtractor(false, true, borrow) == true);
test(borrow == true);
test(full_subtractor(true, true, borrow) == true);
test(borrow == true);
test(full_subtractor(false, true, borrow) == false);
test(borrow == true);
test(full_subtractor(false, false, borrow) == true);
test(borrow == true);
test(full_subtractor(true, false, borrow) == false);
test(borrow == false);
}

void test_main()
{
test_divide();
test_multiply();
test_full_adder();
test_full_subtractor();
}
}

#endif

Jul 23 '05 #1
0 2433

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

Similar topics

4
by: christopher diggins | last post by:
Welcome to the first installment of the Diggins Public Domain Posts (PDP). There is a significant dearth of good public domain C++ code. All of it seems to come with one kind of a license or...
103
by: Steven T. Hatton | last post by:
27.4.2.1.4 Type ios_base::openmode Says this about the std::ios::binary openmode flag: *binary*: perform input and output in binary mode (as opposed to text mode) And that is basically _all_ it...
8
by: bearophileHUGS | last post by:
Hello, I have four things to ask or to suggest, sorry if they seem basic or already discussed. ------------------- I am still ignorant about Tkinter. This little program, after pressing the...
3
by: ruben.de.visscher | last post by:
I am trying to write a program that encrypts 8-bit plaintext using a 10-bit key. To generate subkeys, and for other things, i will need to be able to perform permutations on binary strings for...
10
by: jt | last post by:
I'm needing to take a binary string start at a certain position and return a pointer from that postion to the end of the binary stirng. something like this: char bstr; char *pos; ...
8
by: sudharsan | last post by:
please gimme the logic to merge two binary search trees?I mean which node has to be the root node of the new binary tree?? Thanks in advance
68
by: vim | last post by:
hello everybody Plz tell the differance between binary file and ascii file............... Thanks in advance vim
7
by: Hallvard B Furuseth | last post by:
I'm trying to clean up a program which does arithmetic on text file positions, and also reads text files in binary mode. I can't easily get rid of it all, so I'm wondering which of the following...
8
by: Skybuck Flying | last post by:
Hello, Visual Studio .Net 2005 (Win32) Compile error: Error 1 error C2804: binary 'operator +' has too many parameters <snipped> line 16 class TSkybuckInt32 { private:
2
by: Kemmylinns12 | last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and efficiency. While initially associated with cryptocurrencies...
0
by: Naresh1 | last post by:
What is WebLogic Admin Training? WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge required to effectively administer and manage Oracle...
0
by: antdb | last post by:
Ⅰ. Advantage of AntDB: hyper-convergence + streaming processing engine In the overall architecture, a new "hyper-convergence" concept was proposed, which integrated multiple engines and...
2
by: Matthew3360 | last post by:
Hi, I have a python app that i want to be able to get variables from a php page on my webserver. My python app is on my computer. How would I make it so the python app could use a http request to get...
0
by: Arjunsri | last post by:
I have a Redshift database that I need to use as an import data source. I have configured the DSN connection using the server, port, database, and credentials and received a successful connection...
0
hi
by: WisdomUfot | last post by:
It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific technical details, Gmail likely implements measures...
1
by: Matthew3360 | last post by:
Hi, I have been trying to connect to a local host using php curl. But I am finding it hard to do this. I am doing the curl get request from my web server and have made sure to enable curl. I get a...
0
by: Carina712 | last post by:
Setting background colors for Excel documents can help to improve the visual appeal of the document and make it easier to read and understand. Background colors can be used to highlight important...
0
by: Ricardo de Mila | last post by:
Dear people, good afternoon... I have a form in msAccess with lots of controls and a specific routine must be triggered if the mouse_down event happens in any control. Than I need to discover what...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.