Binary addition
Brian Pianczk
Ranch Hand
Posts: 45
posted 8 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 8 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
Marshal
Posts: 52636
119
posted 8 years ago
f you are given such detailed pseudocode, 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 1bit numbers. You can put 8, 16, 32, 64 full adders together to add (would you believe) 8bit, 16bit, 32bit or 64bit 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 1bit numbers. You can put 8, 16, 32, 64 full adders together to add (would you believe) 8bit, 16bit, 32bit or 64bit 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 8 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 8 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 pseudocode 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 pseudocode thing.
Justin
You down with OOP? Yeah you know me!
Brian Pianczk
Ranch Hand
Posts: 45
posted 8 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 8 years ago
if an array is length long the last index will be length1. Array indexes are zero based. so a[i] where i = a.length will throw an AIOOBE.
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 length1. Array indexes are zero based. so a[i] where i = a.length will throw an AIOOBE.
Brian Pianczk
Ranch Hand
Posts: 45
posted 8 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 last index will be length1. 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 8 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!
I would challenge you to a battle of wits, but I see you are unarmed  shakespear. Unarmed tiny ad:
the new thread boost feature brings a LOT of attention to your favorite threads
https://coderanch.com/t/674455/ThreadBoostfeature
