Binary add

  • (2 Pages)
  • +
  • 1
  • 2

27 Replies - 1426 Views - Last Post: 08 June 2013 - 10:53 PM

#1 TwoOfDiamonds  Icon User is offline

  • D.I.C Regular

Reputation: 54
  • View blog
  • Posts: 272
  • Joined: 27-July 12

Binary add

Posted 07 June 2013 - 02:50 PM

How are 2 binary numbers (are they also called numbers in base 2?) added?

I got this exercise in Introduction to Algorithms :

Quote

Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n + 1)-element array C. State the problem formally and write pseudocode for adding the two integers.


And I'm not really sure how to add those 2 numbers.

Is This A Good Question/Topic? 0
  • +

Replies To: Binary add

#2 andrewsw  Icon User is offline

  • Fire giant boob nipple gun!
  • member icon

Reputation: 2886
  • View blog
  • Posts: 9,587
  • Joined: 12-December 12

Re: Binary add

Posted 07 June 2013 - 03:00 PM

Seriously?

http://www.wikihow.c...-Binary-Numbers

In any basic tutorial on binary you will find that two binary numbers are added on page 2,3 or 4 :whistling:
Was This Post Helpful? 1
  • +
  • -

#3 TwoOfDiamonds  Icon User is offline

  • D.I.C Regular

Reputation: 54
  • View blog
  • Posts: 272
  • Joined: 27-July 12

Re: Binary add

Posted 07 June 2013 - 03:10 PM

>.< Never dealt with them before ... And sorry for asking when it was so simple to search ... It's 1 AM here and I'm pretty tired, just want to solve that exercise .

Thank you very much !\

PS : It's extremely easy :D

This post has been edited by TwoOfDiamonds: 07 June 2013 - 03:15 PM

Was This Post Helpful? 0
  • +
  • -

#4 Flukeshot  Icon User is offline

  • A little too OCD
  • member icon

Reputation: 402
  • View blog
  • Posts: 1,004
  • Joined: 14-November 12

Re: Binary add

Posted 07 June 2013 - 07:12 PM

It's also extremely easy to convert binary into decimal.

128 64 32 16  8  4  2  1
  0  1  0  1  1  1  0  1



This is one byte of data. Notice how every column, from right to left, increases by x2. That's that bits decimal representation. To convert this byte into a number, we just add all the ones together.

1 + 4 + 8 + 16 + 64 = 93, so 01011101 = 93. Simple.
Was This Post Helpful? 1
  • +
  • -

#5 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7294
  • View blog
  • Posts: 12,138
  • Joined: 19-March 11

Re: Binary add

Posted 07 June 2013 - 08:01 PM

Addition in base 2 works the same way as in any base. You start from the least significant side, and you sum the digits in that place. You take the modulo of that total by 2, and that's the value of that place in the result. You take the div of that total by 2, and that's the carry, it's added to the next column to the left.

Same as base 10, except change the 2 to a 10.

Consider this example. I've stated the carry digit explicitly, even when there is nothing carried.

Base 2:
  1001 + 
  1101 = 
 ------
     0 + 
    10 (carry) + 
    00 +  
   000 (carry) +
   100 +
  0000 (carry) + 
  0000 +
 10000 (carry) = 
 -----
 10110


Base 10:
  9009 + 
  1101 =
 ------- 
     0 + 
    10 (carry) + 
    00 +  
   000 (carry) +
   100 +
  0000 (carry) + 
  0000 +
 10000 (carry) = 
 -----
 10110


Simple, no?

This post has been edited by jon.kiparsky: 07 June 2013 - 08:03 PM

Was This Post Helpful? 1
  • +
  • -

#6 TwoOfDiamonds  Icon User is offline

  • D.I.C Regular

Reputation: 54
  • View blog
  • Posts: 272
  • Joined: 27-July 12

Re: Binary add

Posted 07 June 2013 - 11:21 PM

Yes, it's pretty easy . I thought it would be more complex.
And thank you Flukeshot :D/> I finnaly understood how numbers are represented in binary.
And if I want to change from base 10 to base 2 i just take the highest power of 2 smaller than my number and substract it from my number in base 10, and so on until it becomes 0 ? and put a 1 if I subtracted with that power of 2 or 0 if i didn't, right?

for example:

Quote

583
512 is the greatest power of 2 smaller than 583 so I make this:
583 - 512 = 71
so my binary number becomes 1
256 is bigger than my number so i can't substract it so it becomes a 0 => 10
128 is bigger => 0 => 100
64 is smaller so i'll have 71-64 = 7 so i put a 1 => 1001
32 is bigger => 0 => 10010
16 is bigger => 0 => 100100
8 is bigger => 0 => 1001000
4 is smaller => 7 - 4 = 3 => 1 => 10010001
2 is smaller => 3 - 2 = 1 => 1 => 100100011
1 is exactly the number => 1 - 1 = 0 (so i am done) => 1001000111


is that logic correct or is there a better way to do it?

This post has been edited by TwoOfDiamonds: 07 June 2013 - 11:23 PM

Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7294
  • View blog
  • Posts: 12,138
  • Joined: 19-March 11

Re: Binary add

Posted 07 June 2013 - 11:32 PM

Yes, there's a better way, but it might not be obvious if you're trying to work it out on your own.

It might be obvious if I ask you this question: How do you know a number has a 1 in the 2^0 place of its binary represenation? Similarly, how do you know if it has a 7 in the 10^0 place of its decimal representation? Or, to make it more general, how do you know what digit is in the ones place of a number, when it's represented in base b? From there, how do you get to the b's place?

Okay, probably still not obvious. But I'll let you chew on that a little.
Was This Post Helpful? 0
  • +
  • -

#8 Flukeshot  Icon User is offline

  • A little too OCD
  • member icon

Reputation: 402
  • View blog
  • Posts: 1,004
  • Joined: 14-November 12

Re: Binary add

Posted 07 June 2013 - 11:35 PM

Once you've understood Jon's post you can move on to octal and hex.
The process is the same, but instead of 0 and 1, you're using 0 through 7 (for octal) and 0 through 9 and ABCDEF (for hex).

Example of octal:

8 4 2 1
7 3 6 1 = 7x8 + 3x4 + 6x2 + 1 = 56 + 12 + 12 + 1 = 81

512 64 8 1
7 3 6 1 = 7x512 + 3x64 + 6x8 + 1 = 3584 + 192 + 48 + 1 = 3825

Example of hex:

8 4 2 1
F 0 E 9 = 15x8 + 14x2 + 9 = 120 + 28 + 9 = 157


4096 256 16 1
F 0 E 9 = 15x4096 + 14x16 + 9 = 61440 + 224 + 9 = 61673

Since hex can hold higher values per bit, it has the highest capacity.

This post has been edited by Flukeshot: 08 June 2013 - 12:20 AM

Was This Post Helpful? 0
  • +
  • -

#9 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7294
  • View blog
  • Posts: 12,138
  • Joined: 19-March 11

Re: Binary add

Posted 07 June 2013 - 11:49 PM

View Postjon.kiparsky, on 08 June 2013 - 01:32 AM, said:

Yes, there's a better way, but it might not be obvious if you're trying to work it out on your own.

It might be obvious if I ask you this question: How do you know a number has a 1 in the 2^0 place of its binary represenation? Similarly, how do you know if it has a 7 in the 10^0 place of its decimal representation? Or, to make it more general, how do you know what digit is in the ones place of a number, when it's represented in base b? From there, how do you get to the b's place?

Okay, probably still not obvious. But I'll let you chew on that a little.



Bascially, this is the inverse of your method, but it's probably a lot easier to write it nicely.
Was This Post Helpful? 0
  • +
  • -

#10 TwoOfDiamonds  Icon User is offline

  • D.I.C Regular

Reputation: 54
  • View blog
  • Posts: 272
  • Joined: 27-July 12

Re: Binary add

Posted 07 June 2013 - 11:52 PM

Jon, I think it with (number) modulo (base).
So at 10^0 there is n % 10, and in base 2 there is n % 2 so if n is odd at 2^0 we have 1 and if it's even we have 0. Am I right ?
Was This Post Helpful? 2
  • +
  • -

#11 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7294
  • View blog
  • Posts: 12,138
  • Joined: 19-March 11

Re: Binary add

Posted 07 June 2013 - 11:55 PM

Exactly. So you can peel off digits from the least-significant end, and reduce with division, and stop when n gets to zero. Makes sense?
Was This Post Helpful? 0
  • +
  • -

#12 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3172
  • View blog
  • Posts: 9,610
  • Joined: 05-May 12

Re: Binary add

Posted 08 June 2013 - 12:02 AM

View PostFlukeshot, on 08 June 2013 - 02:35 AM, said:

Once you've understood Jon's post you can move on to octal and hex.
The process is the same, but instead of 0 and 1, you're using 0 through 7 (for octal) and 0 through 9 and ABCDEF (for hex).

Example of octal:

8 4 2 1
7 3 6 1 = 7x8 + 3x4 + 6x2 + 1 = 56 + 12 + 12 + 1 = 81

Example of hex:

8 4 2 1
F 0 E 9 = 15x8 + 14x2 + 9 = 120 + 28 + 9 = 157

Since hex can hold higher values per bit, it has the highest capacity.


It's way past my bed time, but before I go to bed, there is no way that 0xF0E9 is only 157 in decimal considering that 0xFFFF is 65535 in decimal from many years of poking around on my Commodore 64.
Was This Post Helpful? 3
  • +
  • -

#13 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7294
  • View blog
  • Posts: 12,138
  • Joined: 19-March 11

Re: Binary add

Posted 08 June 2013 - 12:11 AM

View PostSkydiver, on 08 June 2013 - 02:02 AM, said:

It's way past my bed time, but before I go to bed, there is no way that 0xF0E9 is only 157 in decimal considering that 0xFFFF is 65535 in decimal from many years of poking around on my Commodore 64.



I hadn't even noticed that.

F 0 E 9 = 15x16^3 + 0*16^2 + 14x16^1 + 9 *16^0 = 61673
Was This Post Helpful? 0
  • +
  • -

#14 Flukeshot  Icon User is offline

  • A little too OCD
  • member icon

Reputation: 402
  • View blog
  • Posts: 1,004
  • Joined: 14-November 12

Re: Binary add

Posted 08 June 2013 - 12:21 AM

Forgot to change my base, my bad. Fixed. :)
Was This Post Helpful? 0
  • +
  • -

#15 TwoOfDiamonds  Icon User is offline

  • D.I.C Regular

Reputation: 54
  • View blog
  • Posts: 272
  • Joined: 27-July 12

Re: Binary add

Posted 08 June 2013 - 12:30 AM

I think I got it , sort of , but it outputs it reversed.
while (myNum != 0)
{
	binary = binary * 10 + a % 2;
	a = a / 2;
}



I know that it outputs it reversed, and I can make a function that will reverse my number but is the algorithm the good one or should I try again?

EDIT: or i could simply add (a%2)*10^(index)
where index is the position where a%2 should be in the binary number i.e. 101 .. 0 is at position 0 because it will be indexed starting with 0 (since we need 10^0)

This post has been edited by TwoOfDiamonds: 08 June 2013 - 12:42 AM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2