#### VVS

Joined Jul 22, 2007
66
Hello, I have come across a problem and i tried really hard to solve it, i have no idea how to solve the problem, could u please help me.
I have attached the problem in the jpeg file

#### mik3

Joined Feb 4, 2008
4,843
Hello, I have come across a problem and i tried really hard to solve it, i have no idea how to solve the problem, could u please help me.
I have attached the problem in the jpeg file
The range for addition is -(2^N) up to +((2^N)-1) and you need N-bits to represent the answer. For multiplication is should be the same because but i am not sure.

#### Papabravo

Joined Feb 24, 2006
14,205
If you add 2 N-bit numbers each stage will produce a result bit and a carry bit. So the answer for addition is N + 1 bits are required.

For multiplication the answer is N + N = 2*N

#### Caveman

Joined Apr 15, 2008
471
They're right, but I'm going to explain a little more on this.
Range:
The range of an N bit signed number is $$-(2^{N})$$ as the most negative, and $$2^{N} - 1$$ for the most positive.

The smallest possible result is when you add the two most negative possible inputs. The largest possible result is when you add the two most positive possible inputs. This should be fairly intuitive.
So the two most negative is $$-(2^{N}) + -(2^{N}) = -2 * 2^{N} = -(2^{N+1})$$.
The most positive is $$2^{N}-1 + 2^{N}-1 = 2*2^{N}-2 = 2^{N+1}-2$$

That output can only be held in an N+1 bit sized number. This makes sense because one more bit means that it can handle double the size, which is as big as adding two numbers can realize.

Multiplication is similar to prove out. The smallest is $$-(2^{N}) * -(2^{N}) = 2^{N+N} = 2^{2N}$$
The largest is $$(2^{N}-1)(2^{N}-1) = 2^{2N} - 2^{N+1} + 1$$

The minimum of the range shows that you need 2*N bits, and the maximum can be held in this as well, so that is the answer.

#### VVS

Joined Jul 22, 2007
66
thanx to mik3, papabravo and speciall caveman, ur explanation is excellent.
one thing i never understood tho is why the maximum positive number in a 2's complement is 2^n - 1. isnt it: 2^0 + 2^1 + 2^2 + 2^3 +........+2^(N-1).
If somebody could explain this to me, I would be very thankful.
thanks a lot again.
VVS

#### Papabravo

Joined Feb 24, 2006
14,205
It is a matter of representation. If an n-bit number represents an unsigned quantity they you are correct and the sum from k=zero to n of 2^k is(( 2^n) - 1)

For 8-bits the unsigned range is [0..255]
For 16-bits the unsigned range is [0..65535]

If an n-bit number is to represent a signed quantity then we dived the available range roughly in half so that the non-negative numbers go from 0 to 2^(n-1) and the negative numbers go fro -1 to -(2(n-1) + 1)

For 8-bits the signed range is -128 to +127
For 16-bits the signed range is -32768 to +32767

#### VVS

Joined Jul 22, 2007
66
that has cleared all my doubts. thanx!!!! i have some more questions.
How does one convert from signed Decimal to Hexadecimal??? I know how to convert signed Decimal to 2's complement. But what about Hexadecimal??

here is an example which I should have been able to solve in a past paper:

#### Papabravo

Joined Feb 24, 2006
14,205
Convert 2317 to hexadecimal => 0x090D
Take the 2's complement => 0xF6F3

#### VVS

Joined Jul 22, 2007
66
how does one take 2's complement of HEX numbers??

#### Papabravo

Joined Feb 24, 2006
14,205
Hex and binary are two equivalent representations of the same thing.

You take the 2's complement of a hexadecimal representation of a binary number by exclusive ORing(taking the 1s complement) with 0xFFFF and adding 0x0001.

In our example
Rich (BB code):
0x090D ^ 0xFFFF = 0xF6F2
0xF6F2 + 0x0001 = 0xF6F3