Behold! The Binary Adder...

Zacariaz · **Joined:** Tue May 22, 2007 2:36 pm **Posts:** 1069

Dont ask why, because there is no answer to that question.
Anyway, for some reason i though it would be a fun way to pratice my binary arimethic.

Well here it is.

Code:

#include <bitset>

class BinAdd {
  std::bitset<8> Dest;
  std::bitset<8> Src;
  bool Carry;
  bool Overflow; // Allso used as temporary Dest bit
    public:
  BinAdd() {}
  ~BinAdd() {}
  bool Get_Carry() {
    return Carry;
  }
  bool Get_Overflow() {
    return Overflow;
  }
  std::bitset<8> Add(std::bitset<8> Dest_in, std::bitset<8> Src_in, bool Carry_in) {
    Dest = Dest_in;
    Src = Src_in;
    Carry = Carry_in;
    for(int i = 0; i < 8; i++) {
      Overflow = (Dest[i] ^ Src[i]) ^ Carry;
      Carry = (Dest[i] & Src[i]) | ((Dest[i] ^ Src[i]) & Carry);
      Dest[i] = Overflow;
    }
    Overflow = (Carry == 1) ? 1 : 0;
    return Dest;
  }
};

For those who know a little C++ and binary arimethic, it should pretty much explain it self and i dare you to improve it.

Overflow and Carry are essentially the same, but i needed the extra bit so i though i might aswell call it overflow.

Asimpler representation of the important stuff could be:

Code:

std::bitset<8> Add(std::bitset<8> Dest, std::bitset<8> Src, bool Carry) {
  bool B;
  for(int i = 0; i < 8; i++) {
    B = (Dest[i] ^ Src[i]) ^ Carry;
    Carry = (Dest[i] & Src[i]) | ((Dest[i] ^ Src[i]) & Carry);
    Dest[i] = B;
  }
  return Dest;
}

Regards

Solar · **Posted:** Wed May 30, 2007 2:17 am

Zacariaz wrote:

...and i dare you to improve it.

You asked for it. There is always room for improvement. :twisted:

You might note I didn't touch your algorithm at all.

1) With your implementation, clients had to pass carry on each invocation - making it impossible to keep carry untouched across several operations.

2) Some code cleanup. ( Overflow = ( Carry == 1 ) ? 1 : 0; is the winner of the day.

)

3) Extended to handle arbitrary parameters. To avoid confusion, you have to call BinAdder.reset() before switching to different-width parameters.

4) Made things static so you don't need to instantiate BinAdder. Not thread safe, but in a single-thread envir more comfortable.

Code:

#include <cstddef>

class BinAdder
{
    public:
        static bool getCarry();
        static bool getOverflow();

        static void clearCarry();
        static void clearOverflow();

        static void reset();

        template < typename T > static unsigned long add( T const operand1, T const operand2 );

    private:
        static bool carry;
        static bool overflow;

        static std::size_t op_size;
};

bool BinAdder::carry = false;
bool BinAdder::overflow = false;
std::size_t BinAdder::op_size = 0;

bool BinAdder::getCarry()
{
    return carry;
}

bool BinAdder::getOverflow()
{
    return overflow;
}

void BinAdder::clearCarry()
{
    carry = false;
}

void BinAdder::clearOverflow()
{
    overflow = false;
}

void BinAdder::reset()
{
    clearCarry();
    clearOverflow();
    op_size = 0;
}

#include <bitset>
#include <exception>
#include <climits>

template < typename T > unsigned long BinAdder::add( T const operand1, T const operand2 )
{
    if ( op_size && op_size != sizeof( T ) )
    {
         throw std::exception();
    }
    op_size = sizeof( T );
    std::bitset< sizeof( T ) * CHAR_BIT > op1( operand1 ), op2( operand2 );
    for ( std::size_t i = 0; i < op1.size(); ++i )
    {
         // using overflow as temporary dest bit
        overflow = ( op1[i] ^ op2[i] ) ^ carry;
        carry = ( op1[i] & op2[i] ) | ( ( op1[i] ^ op2[i] ) & carry );
        op1[i] = overflow;
    }
    overflow = carry;
    return op1.to_ulong();
}

#include <iostream>

int main()
{
  try
   {
      std::cout << BinAdder::add( 8, 16 ) << std::endl;
      std::cout << BinAdder::add( 32, 4 ) << std::endl;
      std::cout << BinAdder::add( 24ll, 36ll ) << std::endl;
   }
   catch ( std::exception )
   {
      std::cout << "Exception caught." << std::endl;
   }
   BinAdder::reset();
   std::cout << BinAdder::add( 24ll, 36ll ) << std::endl;
   return 0;
}

Edit: I was thinking about removing the class altogether, making carry / overflow static variables within the function itself. But that would make retrieval of them a pain - either you'd need a return structure, or "OUT" parameters, both of which aren't nice.

Candy · **Posted:** Wed May 30, 2007 12:40 pm

Solar wrote:

Zacariaz wrote:

...and i dare you to improve it.

You asked for it. There is always room for improvement. :twisted:

*gives it a stab*

Code:

#include <cstddef>

template <typename T>
class BinAdder
{
    public:
        enum { opsize = sizeof(T) * CHAR_BIT; };
        T add( T const operand1, T const operand2 );
};

#include <bitset>
#include <exception>
#include <climits>

template < typename T > 
unsigned long BinAdder::add( T const operand1, T const operand2, bool &carry, bool &overflow)
{
    std::bitset< sizeof( T ) * CHAR_BIT > op1( operand1 ), op2( operand2 );
    for ( std::size_t i = 0; i < op1.size(); ++i )
    {
         // using overflow as temporary dest bit
        overflow = ( op1[i] ^ op2[i] ) ^ carry;
        carry = ( op1[i] & op2[i] ) | ( ( op1[i] ^ op2[i] ) & carry );
        op1[i] = overflow;
    }
    overflow = carry;
    return op1.to_ulong();
}

#include <iostream>

int main()
{
   BinAdder<unsigned int> addr;
   std::cout << addr.add( 8, 16 ) << std::endl;
   std::cout << addr.add( 32, 4 ) << std::endl;
   BinAdder<unsigned long long> ulladdr;
   std::cout << ulladdr.add( 24ll, 36ll ) << std::endl;
   return 0;
}

I added the opsize as a static component of the class, made the members full class members so they could be used as any such item. Also, I removed those weird spaces Solar added in the template definition. I understand they help with coding style & nested templates, but c++09 is going to make the > > cludge obsolete, so it's best not to adjust yourself to the language.

Zacariaz · **Joined:** Tue May 22, 2007 2:36 pm **Posts:** 1069

I keep telling my self not to ask these kinda questions, as the answers will rarely do anything but remind me how little i know. Anyway thats for the answers, it will take me some time to actually understand them fully, but ill definently learn something.

Anyway, if it is a fun challence, keep em comming. As you might have guessed, the original idea was simply to make a class/function that actually (more or less) works as a binary adder would in reallity, on the hardware level that is.

Anyway, thank again...

Candy · **Posted:** Wed May 30, 2007 2:18 pm

Zacariaz wrote:

I keep telling my self not to ask these kinda questions, as the answers will rarely do anything but remind me how little i know. Anyway thats for the answers, it will take me some time to actually understand them fully, but ill definently learn something.

The answers (or at least the one I added) was intended to show a few bits of coding that allows you some other properties with the same program. It was a bit of a show off to show you a method of coding you might not have used before. In my case, I wanted to show template adders (a slight bit) and how to define a constant in a template class. Solar intended to show you some genericity (which the templates also provide), the concept of accessors and protecting variables and the concept of static functions - if you can make it static, you should. We (I) don't intend to make you less motivated or stumped by these suggestions, we hope you'll google for their bases and learn the language more. You can also see the std:: dripping off Solar's example, which is his way of telling "you should know what the standard already brings and what it helps you to use it".

Zacariaz · **Joined:** Tue May 22, 2007 2:36 pm **Posts:** 1069

Yes, i did notice that yor code (candy) was somewhat easyer to comprihend that solars. However its not that im all: "oh no, how am i ever gonna understand" over solars code, just that i hadnt expected such an alteration.

Just for the kicks i did the binary add thingy on paper...

Kevin McGuire · **Posted:** Wed May 30, 2007 4:39 pm

Now all that is left to do is go to Radio Shack and buy a cheap pack of NPN and PNP transistors and you can have you self a real binary adder.

Two high signal on two NPN can pull a line low, and a third PNP would pull another line high to represent the output of 1 for a AND.

A OR is just connecting the wires together, and a NOT is born.

Two ANDs like above with the inputs into one AND inverted with a PNP and then a another PNP so that when both ANDs go low the PNP goes high giving a 1 since as you know a 10 or 01 must have been on both ANDs for them to go low and make the PNP go high.

So its:

battery
jumper pack
soilder gun
soilder
NPN and PNP silicon transistors
pack of LEDS
pack of 1/4 watt resistors

Now you get to make digital circuits from analog ones.

Zacariaz · **Joined:** Tue May 22, 2007 2:36 pm **Posts:** 1069

ill get back to you an that ;D ive never been very good with electronics

Colonel Kernel · **Posted:** Wed May 30, 2007 6:52 pm

And now for something completely different:

-SimulationTest.scala-

Code:

object SimulationTest {
    def main( args: Array[String] ) {
        val input1 = new Wire
        val input2 = new Wire
        val sum = new Wire
        val carry = new Wire

        val sim = new Simulation
        sim.afterDelay( 0, () => Console.println( "*** simulation started ***" ) )
        sim.probe( "sum", sum )
        sim.probe( "carry", carry )

        sim.halfAdder( input1, input2, sum, carry )
        Console.println( "setting input 1..." )
        input1 setSignal true; sim.run
        Console.println( "setting input 2..." )
        input2 setSignal true; sim.run
    }

    val InverterDelay = 1
    val AndGateDelay = 3
    val OrGateDelay = 5

    type Action = () => unit

    class Wire {
        def getSignal = sigVal

        def setSignal( s: boolean ) =
            if (s != sigVal) {
                sigVal = s
                actions.foreach( action => action() );
            }

        def addAction( a: Action ) = {
            actions = a :: actions; a()
        }

        private var sigVal = false
        private var actions: List[Action] = List()
    }

    class Simulation {
        def afterDelay( delay: int, action: => Action ) {
            val actionTime = curTime + delay
            def insert( ag: Agenda ): Agenda = ag match {
                case List() =>
                    Pair( actionTime, action ) :: ag
                case (first @ Pair( time, act )) :: ag1 =>
                    if (actionTime < time) Pair( actionTime, action ) :: ag
                    else first :: insert( ag1 )
            }
            agenda = insert( agenda )
        }
/*
        // This recursive version of run is from the textbook. I find it quite scary. -- BJ
        def run {
            agenda match {
                case List() =>
                case Pair( time, action ) :: agenda1 =>
                    agenda = agenda1; curTime = time; action(); run
            }
        }
*/
        def run {
            var keepGoing = false
            do {
                keepGoing =
                    agenda match {
                        case List() => false
                        case Pair( time, action ) :: agenda1 =>
                            agenda = agenda1; curTime = time; action(); true
                    }
            } while (keepGoing)
        }

        def probe( name: String, wire: Wire ) {
            wire addAction {() =>
                val bit = if (wire.getSignal) 1 else 0
                Console.println(
                    "@ time " + curTime + ": " + name + " = " + bit )
            }
        }

        def inverter( input: Wire, output: Wire ) = {
            def invertAction() = {
                val inputSig = input.getSignal
                afterDelay( InverterDelay, () => output.setSignal( !inputSig ) )
            }
            input addAction invertAction
        }

        def andGate( a1: Wire, a2: Wire, output: Wire ) = {
            def andAction() = {
                val a1Sig = a1.getSignal
                val a2Sig = a2.getSignal
                afterDelay( AndGateDelay, () => output.setSignal( a1Sig & a2Sig ) )
            }
            a1 addAction andAction
            a2 addAction andAction
        }

        def orGate( o1: Wire, o2: Wire, output: Wire ) = {
            def orAction() = {
                val o1Sig = o1.getSignal
                val o2Sig = o2.getSignal
                afterDelay( OrGateDelay, () => output.setSignal( o1Sig | o2Sig ) )
            }
            o1 addAction orAction
            o2 addAction orAction
        }
/*
        // As an interesting experiment, see what happens when you implement OR gates
        // in terms of AND gates and inverters.
        def orGate( o1: Wire, o2: Wire, output: Wire ) = {
            val notO1 = new Wire
            val notO2 = new Wire
            val andOut = new Wire

            inverter( o1, notO1 )
            inverter( o2, notO2 )
            andGate( notO1, notO2, andOut )
            inverter( andOut, output )
        }
*/
        def halfAdder( a: Wire, b: Wire, s: Wire, c: Wire ) {
            val d = new Wire
            val e = new Wire

            // Uncomment these lines to see what goes on inside half adders during the
            // simulation. If you use the complex OR gate, you can see some jitter in
            // the circuit.
//            probe( "d", d )
//            probe( "e", e )
            orGate( a, b, d )
            andGate( a, b, c )
            inverter( c, e )
            andGate( d, e, s )
        }

        def fullAdder( a: Wire, b: Wire, cin: Wire, sum: Wire, cout: Wire ) {
            val s = new Wire
            val c1 = new Wire
            val c2 = new Wire
            halfAdder( a, cin, s, c1 )
            halfAdder( b, s, sum, c2 )
            orGate( c1, c2, cout )
        }

        private type Agenda = List[Pair[int, Action]]
        private var agenda: Agenda = List()
        private var curTime = 0
    }
}

This is a completed and corrected version of the circuit simulator program from Scala By Example.

Solar · **Posted:** Wed May 30, 2007 9:44 pm

Nope, too long to be tackled "on the fly".

But, Candy, you might want to review your code. You don't use that enum you defined anywhere, and one cannot retrieve overflow / carry (as I understood was Zacarias' intent as he explicitly added getter functions for them).

Colonel Kernel · **Posted:** Wed May 30, 2007 11:41 pm

I'll expand on that code a little -- it actually simulates the circuit behaviour by assigning propagation delays to each of the gate types. Wires between gates are represented as objects. Gates themselves are represented as functions that create closures of other functions (Scala is an OO-functional language hybrid) to actually propagate the signals. Each function that propagates signals has references to the relevant Wire objects as variables in its environment (i.e. -- in the closure).

All in all, I think this is the most succinct language I know of to express this type of simulation.

I know this has nothing to do with good C++ coding practices, but the code does simulate a binary full-adder, so I would argue that it's more on-topic.

Candy · **Posted:** Thu May 31, 2007 9:57 am

Solar wrote:

Nope, too long to be tackled "on the fly".

But, Candy, you might want to review your code. You don't use that enum you defined anywhere, and one cannot retrieve overflow / carry (as I understood was Zacarias' intent as he explicitly added getter functions for them).

The carry and overflow are reference parameters to the operation, which can come from another object containing these parameters (a flag register) or from any other source, such as a constant 0 or 1. The enum is in fact pointless, but it does allow you to determine the amount of bits that adder processes. Even more so, it allows you to determine how many bits an adder of any type is going to process, when using template metaprogramming.

Oh, and I didn't compile it. I don't post code intended for people to use, I post code intended for people to understand and follow. If skipping obvious parts of the solution makes it clearer, I will.

Candy · **Posted:** Thu May 31, 2007 1:26 pm

I was thinking, you should be able to do this at compile-time with appropriate templates too. If you made it a variadic template (to be introduced with C++0x in 2 to 4 years) you could make it perform arbitrary calculations at compile time on bit vectors...

So I set out with my preliminary c++0x compiler for my own OS and tried to make it work. It works, except for me not having a crt0.o to link to, nor an environment to execute in. Since it's in compile time, however, you can see the results in the assembly output since the calculations won't be in there.

The source

Code:

namespace std {
void printf(const char *, ...);
}

template <int... Boolvector>
class bitvector;

template <int B0, int... rest>
struct bitvector<B0, rest...> {
        typedef bitvector<rest...> tail;
        enum {
                head = B0,
                value = (B0 << tail::bitcount) + (tail::value),
                bitcount = 1 + tail::bitcount
        };
        template <int Z>
        struct add_front {
                typedef bitvector<Z, B0, rest...> value;
        };
};

template <int c, typename V1, typename V2>
struct add {
private:
        typedef add<c, typename V1::tail, typename V2::tail> subchild;
public:
        typedef typename add<c, typename V1::tail, typename V2::tail>::value subchildvalue;
        typedef typename subchildvalue::template add_front<V1::head ^ V2::head ^ subchild::carry>::value value;
        enum {
                carry = (V1::head & V2::head) | (V1::head & subchild::carry) | (V2::head & subchild::carry)
        };
};

template <int c>
struct add<c, bitvector<>, bitvector<> > {
        typedef bitvector<> value;
        enum { carry = c };
};

template <>
struct bitvector<> {
        enum {
                value = 0,
                bitcount = 0
        };
        template <int Z>
        struct add_front {
                typedef bitvector<Z> value;
        };
};

typedef bitvector<0,1,1,0,1,0,0,1> value_105;
typedef bitvector<0,0,1,1,0,0,1,1> value_51;
typedef add<0, value_105, value_51>::value value_result;

int main() {
        std::printf("Value of %d + %d = %d\n", value_105::value, value_51::value, value_result::value);
}

The assembly output (per lack of better output, left out a few bits of slack, didn't modify any bit I copied, didn't copy more than one bit):

Code:

        .file   "bit.cc"
        .section        .rodata
.LC0:
        .string "Value of %d + %d = %d\n"
        .text
        .align 2
.globl main
        .type   main, @function
main:
.LFB2:
        leal    4(%esp), %ecx
.LCFI0:
        andl    $-16, %esp
        pushl   -4(%ecx)
.LCFI1:
        pushl   %ebp
.LCFI2:
        movl    %esp, %ebp
.LCFI3:
        pushl   %ecx
.LCFI4:
        subl    $20, %esp
.LCFI5:
        movl    $156, 12(%esp)
        movl    $51, 8(%esp)
        movl    $105, 4(%esp)
        movl    $.LC0, (%esp)
        call    _ZSt6printfPKcz
        movl    $0, %eax
        addl    $20, %esp
        popl    %ecx
        popl    %ebp
        leal    -4(%ecx), %esp
        ret
.LFE2:
        .size   main, .-main
<snip exception handling and GNU personality thingy>
        .align 4
.LEFDE1:
        .ident  "GCC: (GNU) 4.3.0 20070427 (experimental)"

As you can see, it'll output (105 + 51 == 156), which is mathematically correct.

If you want to mess with it, you can get the compiler from the GCC CVS/SVN server. Download a 4.3 snapshot (mine is from early this month) or current tip.

Enjoy!

Candy · **Posted:** Thu May 31, 2007 3:26 pm

For an encore, the proof that you can do this in C++98 already:

Code:

extern "C"
void printf(const char *, ...);

struct NullType {};

template <int B0, typename tailtypes>
struct bitvector {
        typedef tailtypes tail;
        enum {
                head = B0,
                value = (B0 << tail::bitcount) + (tail::value),
                bitcount = 1 + tail::bitcount
        };
        template <int Z>
        struct add_front {
                typedef bitvector<Z, bitvector<B0, tail> > value;
        };
};

template <int B0>
struct bitvector<B0, NullType> {
        enum {
                head = B0,
                value = B0,
                bitcount = 1
        };
        template <int Z>
        struct add_front {
                typedef bitvector<Z, bitvector<B0, NullType> > value;
        };
};

template <int c, typename V1, typename V2>
struct add {
private:
        typedef add<c, typename V1::tail, typename V2::tail> subchild;
public:
        typedef typename subchild::value::template add_front<V1::head ^ V2::head ^ subchild::carry>::value value;
        enum {
                carry = (V1::head & V2::head) | (V1::head & subchild::carry) | (V2::head & subchild::carry)
        };
};

template <int c, int N1, int N2>
struct add<c, bitvector<N1, NullType>, bitvector<N2, NullType> > {
        typedef bitvector<N1 ^ N2 ^ c, NullType> value;
        enum { carry = (c & N1) | (N1 & N2) | (N2 & c) };
};

#define BITVECTOR8(a,b,c,d,e,f,g,h) bitvector<a, bitvector<b, bitvector<c, bitvector<d, bitvector<e, bitvector<f, bitvector<g, bitvector<h, NullType> > > > > > > >

typedef BITVECTOR8(0,1,1,0,1,0,0,1) value_105;
typedef BITVECTOR8(0,0,1,1,0,0,1,1) value_51;
typedef add<0, value_105, value_51>::value value_result;

int main() {
        printf("Value of %d + %d = %d\n", value_105::value, value_51::value, value_result::value);
}

Downside is the use of the preprocessor due to the verbosity of the recursive template replacing the variadic template... You can probably reduce this by formatting it more like a tree at the expense of a bit more complex management structure...

niteice · **Joined:** Tue Oct 03, 2006 3:49 pm **Posts:** 59

There was a recent contest this would have been PERFECT for:

http://omg.worsethanfailure.com

OSDev.org

Behold! The Binary Adder...

Who is online