# Binary addition

Brian Pianczk

Ranch Hand

Posts: 45

posted 7 years ago

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

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

posted 7 years ago

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

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: 50687

83

posted 7 years ago

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

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

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

posted 7 years ago

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

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

posted 7 years ago

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

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

You down with OOP? Yeah you know me!

Brian Pianczk

Ranch Hand

Posts: 45

posted 7 years ago

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?

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: 230

posted 7 years ago

if an array is length long the last

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

posted 7 years ago

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

Thanks

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 lastindexwill 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: 230

Justin Fox

Ranch Hand

Posts: 802

posted 7 years ago

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

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

You down with OOP? Yeah you know me!