Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

Brian Pianczk
Ranch Hand
Posts: 45
I have searched all over for answers on how to take two 1 byte strings and add them together. ( I am to only use the algorithm given)

My professor has given the algorithm, and has asked us to code it.

This is what was given:

Using the following algorithm, and only Boolean functions.

Set C to zero;
for i from right to left do

Ri = (Ai xor Bi) xor C;
Cnew = (Ai and Bi) or (Ai and c) or (Bi and C old)

Where Ai and Bi are the ith bits of the variables to be added, C old is the carry from the previous iteration, Cnew is the new carry and Ri is the ith bit of the result.

This is what I have, it is a shot in the dark but I am not sure if I fully understand the algorithm

Atm I am getting an outofbounds error, and I am trying to fix that.
I am not looking for code, what I am really looking for is some kind of explanation on how to go about it, especially the last bit of Cnew.

Thanks

Henry Wong
author
Marshal
Posts: 20894
75
Atm I am getting an outofbounds error, and I am trying to fix that.

And out of bounds exception provides the exact class, method, and line number, along with the index being accessed... So, it will tell you exactly where the out of bounds is occuring, and the whether it's an overflow or underflow. You should use that to isolate your problem.

Henry

Campbell Ritchie
Sheriff
Posts: 48415
56
f you are given such detailed pseudo-code, then it is usually very easy to convert it to code. What you have got to do, however, is convert a String like "01010101" into 8 numbers, working from right to left. You are using char[] arrays: if you look in the String class you might find a way of turning a String to a char array.
Find the Character class and see whether there are any methods which will allow you to convert '1' to 1 or '0' to 0, etc. You are trying to get a numeric value from the char.
You can now deal with a 1 or a 0 as a simple number. Much easier. You also need to find whether there are any operators in Java which implement the XOR function (Hint: you can find it here.) (Hint 2: XOR is short for exclusive OR) Similarly whether there are any operators which implement the AND and OR operations (Hint: if there is an XOR operator, you would expect to find the AND and OR operators on the same page).

Don't use explicit numbers in a for loop to iterate through an array. Always use myArray.length.

********************************************************************************************************************************

What you have been given is an exercise to model the full adder, which is a circuit in a chip which (would you believe) adds two 1-bit numbers. You can put 8, 16, 32, 64 full adders together to add (would you believe) 8-bit, 16-bit, 32-bit or 64-bit numbers. An adder takes three inputs, input1, input2, and carry_in; It can have 000 001 010 100 011 101 110 and 111 as its inputs. If it is presented with an even number of inputs, it outputs a 0 bit, or a 1 bit for an odd number of inputs. If it has lots of inputs (two 1s or three 1s) it outputs a 1 as its carry_out, or if it has few inputs (one 1 or all 0s) then it produces a 0 for its carry_out. You are calling the carry_in bit "C old" and the carry_out bit "C new."
The carry_out bit is passed on to the next adder in the array, and it can reliably add integers up to the size of the array.
You can even put XOR gates on the input and if you put an input to those XOR gates (and copy that signal to the carry_in of the 1st adder) you convert one of the inputs to its two's complement, so rather than adding the two numbers you can subtract them.

********************************************************************************************************************************

I think you have enough hints

Brian Pianczk
Ranch Hand
Posts: 45
Thanks much for the info.

I am using a char array, but in my output I convert it to a string.

I may have confused the Professor's initial direction which was to use that algorithm, I took it as to not use operators, which would be silly now that I think about it.

I will take a look at the functions and see if I can work it out that way.

thanks

Justin Fox
Ranch Hand
Posts: 802
I had an assignment exactly like this in CS2 I believe...
It's always easier if you make them both the same length,

say you have two inputs:
1. '10001'
2. '101'

then you would want to make them:
1.'10001'
2.'00101' // add two zeros to the front of the smaller one (which is 2 bits smaller in this case)

then you would start from the right at the same index and add them together..
just remember that

0 + 0 = 0 with a carry of 0
0 + 1 = 1 with a carry of 0
1 + 0 = 1 with a carry of 0
1 + 1 = 0 with a carry of 1

so if you're updating the carry everytime you add the two bits at row index i or j or whatever you want to use.

then you simply have to do:

Hope this was kind of helpfull, did the pseudo-code thing.

Justin

Brian Pianczk
Ranch Hand
Posts: 45
I guess now my issue is how to start at the right most bit, and then add through them from right to left?

for (int i =a.length; i<=0; i--)
doesn't seem to work. The way it looks to me is that this for should start at the last index of the array and work backward. Is that not what it is doing?

Paul Yule
Ranch Hand
Posts: 229
Brian Pianczk wrote:I guess now my issue is how to start at the right most bit, and then add through them from right to left?

for (int i =a.length; i<=0; i--)
doesn't seem to work. The way it looks to me is that this for should start at the last index of the array and work backward. Is that not what it is doing?

if an array is length long the last index will be length-1. Array indexes are zero based. so a[i] where i = a.length will throw an AIOOBE.

Brian Pianczk
Ranch Hand
Posts: 45
Paul Yule wrote:
Brian Pianczk wrote:I guess now my issue is how to start at the right most bit, and then add through them from right to left?

for (int i =a.length; i<=0; i--)
doesn't seem to work. The way it looks to me is that this for should start at the last index of the array and work backward. Is that not what it is doing?

if an array is length long the last index will be length-1. Array indexes are zero based. so a[i] where i = a.length will throw an AIOOBE.

Always something simple I overlook, practice, practice and more practice!

Thanks

Paul Yule
Ranch Hand
Posts: 229
Brian Pianczk wrote:

Always something simple I overlook, practice, practice and more practice!

Thanks

every single person on this site has had that error at some point. Everyone.

Justin Fox
Ranch Hand
Posts: 802
yep, it is definately easy to overlook things in a loop and get the
out of bounds exception.

The important thing is that your idea was right. Without being able
to solve the problem first (without code) you will have a hard
time programming.

Let us know if you get it working,

Justin