I got this exercise in Introduction to Algorithms :

Quote

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

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 :

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

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.

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

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

In

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

Thank you very much !\

PS : It's extremely easy

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

Posted 07 June 2013 - 07:12 PM

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

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.

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.

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:

Base 10:

Simple, no?

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

Posted 07 June 2013 - 11:21 PM

Yes, it's pretty easy . I thought it would be more complex.

And thank you Flukeshot /> 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:

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

And thank you Flukeshot /> 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

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

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.

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.

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.

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:

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:

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

Posted 07 June 2013 - 11:49 PM

jon.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.

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.

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 ?

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 ?

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?

Posted 08 June 2013 - 12:02 AM

Flukeshot, 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.

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.

Posted 08 June 2013 - 12:11 AM

Skydiver, 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

Posted 08 June 2013 - 12:30 AM

I think I got it , sort of , but it outputs it reversed.

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)

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

- Caffeine Lounge
- Corner Cubicle
- Student Campus
- Software Development
- Industry News
- Introduce Yourself
- Nightmare.In.Code

- C and C++
- VB.NET
- Java
- C#
- Python
- PHP
- Mobile Development
- ASP.NET
- .NET Framework
- Ruby
- Game Development
- Assembly
- Databases
- ColdFusion
- VB6
- Other Languages
- 52 Weeks Of Code

- Web Development
- HTML & CSS
- JavaScript
- Graphic Design
- Flash & ActionScript
- Blogging
- SEO & Advertising
- Web Servers & Hosting
- Site Check

- C++ Tutorials
- Java Tutorials
- VisualBasic Tutorials
- VB.NET Tutorials
- C# Tutorials
- PHP Tutorials
- ColdFusion Tutorials
- Database Tutorials

- C Snippets
- C++ Snippets
- Java Snippets
- Visual Basic Snippets
- C# Snippets
- VB.NET Snippets
- ASP.NET Snippets
- PHP Snippets
- Python Snippets
- Ruby Snippets
- ColdFusion Snippets
- SQL Snippets
- Assembly Snippets
- Functional Programming Snippets
- Perl Snippets
- HTML/CSS Snippets
- Javascript Snippets
- Flash/ActionScript Snippets
- ASP Snippets
- Linux, Unix, and Bash Snippets
- Other Languages Snippets
- Regex

Copyright 2001-2016 **MediaGroup1 LLC**, All Rights Reserved

A**MediaGroup1 LLC** Production - Version 6.0.2.1.36

Server: secure3

A

Server: secure3