ISRO2017-24

Question

When two $n$-bit binary numbers are added the sum will contain at the most

• A. $n$ bits
• B. $n + 2$ bits
• C. $n + 3$ bits
• D. $n + 1$ bits

Comments

Maximum number representable from $n$ bits=$2^{n}-1$

thus adding two $n$ bit number,

$2^{n}-1$+$2^{n}-1=2 \times (2^{n}-1)$ i.e one more bit

hence D

Answer 1

Answer: (d)

This I think can be proved using induction, but that would be much more complicated than required to understand the intricacies. So, I will go with the intuitive approach.

At some point in addition of two n-bit numbers when two bit are added we inurn add three bits. First bit is the bit from the first operand, the second bit is the bit from the second operand and then third bit is the carry bit resulted due to addition of bits at previous place value.

Let the $n^{th}$ bit of operands including the carry bit (obtained from addition of bits at previous place value) be $1$ so as to get the maximum sum. In such a case the $n^{th}$ bit addition will give $11$, where the most significant bit is carry bit but ultimately become the most significant bit of final result. Thereby increasing the number of bit of result by just one. 

---

There is another way of convincing yourself that the result of addition will not have more than $(n+1)$ bits. For some value of $n$ perform addition with $2^n-1$ (largest n-bit binary number) as its both the operands and see if the result you get is of $(n+1)$ bits or not.

Comments

but , the question is given for at most right?

eg. 10 + 01 = 11 (2 bits)

so the at most it has n bits.

correct me if I am wrong.

---

Let $n=2$ and try this one

$(11)_2 + (11)_2$

What do you get? How many bits are there in the result?

Answer 2

See, in worst case what will happen? 

like for 2 bits:           1  1

                                    1  1

---

                                1  1   0

---

for 3 bits:              1  1  1   0

---

for n bits :                 n+1

Answer 3

n+1 bits..1 if carry is there

Answer 4

• Bit Capacity: $n$-bit numbers can represent $2^n$ distinct values.
• Maximum Sum: The largest possible sum occurs when both $n$-bit numbers are their maximum value (all bits 1).
• Carry-Out: Adding two $n$-bit numbers can generate a carry-out bit, extending the result beyond $n$ bits.
• Example: Adding $1111$ (binary 4-bit) and $1111$ results in $11110$ (binary 5-bit, with a carry-out).

Therefore, the sum of two n-bit binary numbers can contain at most $n + 1$ bits to accommodate a potential carry-out.