On 8/29/07, Dennis Heuer <[EMAIL PROTECTED]> wrote:
>
> int main ()
> {
> unsigned int x = 23; // the first value
> unsigned int y = 15; // the second value
> unsigned int c = 1; // the carry bitfield (ignore the value)
>
> while (c != 0)
> {
> c = x & y; // first extracting the (rippling) carry bits
> x = x ^ y; // before x gets overwritten with the result of
> // the basic addition and, from then on, the
> // result of merging x with the carry
> y = c << 1; // shifting the carry to merge it with x
> } // already beginning from above again
>
> if (x == 38)
> printf("test passed!\n");
>
> return 0;
> }
>
>
> what do you think?
Well, it IS an interesting characterization of an adder. But it's a
very software-ish approach. If you had a CPU without an ADD
instruction, it might yield an interesting optimization. In fact, if
your goal were to develop a CPU with absolute minimal logic, this
might be a good solution to the problem of doing sums without an ADD
instruction. I presume there'd be a similiar solution for SUB.
If you were to convert this to combinatorial logic, however, you'd
pretty much just end up with a regular ripple-carry adder.
Note that in hardware, we only care about the worst-case timing. If
something's worst case is O(n), then we have to allot it O(n) time for
signals to propagate. Also, note that carry look-ahead adders require
O(log n) time or even better. (Although they do require O(n*n) logic
gates or O(n*n*n) transistors.)
--
Timothy Normand Miller
http://www.cse.ohio-state.edu/~millerti
Open Graphics Project
_______________________________________________
Open-graphics mailing list
[email protected]
http://lists.duskglow.com/mailman/listinfo/open-graphics
List service provided by Duskglow Consulting, LLC (www.duskglow.com)
