Chapters 1.1–1.2 Lock-in — Signed numbers & Binary codes

ACompressed recap

🧾

SM flips the sign bit, 1's inverts, 2's inverts and adds 1; 2's MSB weight −2ⁿ⁻¹, range −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1. 2's add: drop carry; A − B = A + B' + 1; overflow when same signs give the opposite sign (carry in ⊕ carry out of MSB). Sign-extend by copying the MSB. Arithmetic right shift copies the MSB. Booth: 10 → −M, 01 → +M. BCD (+6 correction), excess-3, Gray (g = b ⊕ b >> 1), parity.

BMerged rule card

1.1.1 Sign-magnitude, 1's complement and 2's complement

• Positive numbers: same in SM, 1's and 2's complement (MSB 0).
• SM: flip the sign bit. 1's: invert all bits. 2's: invert all and add 1 (or copy up to the first 1 from the right, invert the rest).
• 2's complement value: MSB worth −2ⁿ⁻¹; range −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1; one zero.
• SM and 1's complement: range ±(2ⁿ⁻¹ − 1), two zeros.

1.1.2 2's-complement arithmetic: addition, subtraction, overflow, sign extension

• 2's-complement add: add the patterns, discard the carry out.
• A − B = A + B' + 1.
• Overflow: same-sign operands give an opposite-sign result; equivalently carry into MSB ⊕ carry out of MSB = 1. Mixed signs never overflow.
• Sign extension: copy the MSB. 1's complement addition needs an end-around carry.

1.1.3 Shifts, multiplication and Booth's algorithm

• Logical shifts insert 0; arithmetic right shift copies the MSB (÷2, rounding towards −∞).
• Signed n × n product needs 2n bits.
• Booth pairs (qᵢ, qᵢ₋₁), q₋₁ = 0: 10 → −M, 01 → +M, 00/11 → nothing; then arithmetic shift right of A, Q, Q₋₁.
• Booth operations = number of 01 and 10 pairs; worst case alternating bits.

1.2.1 Binary codes: BCD, excess-3, Gray code and parity

• BCD: 4 bits per decimal digit; 1010–1111 invalid; digit sum > 9 or carry → add 0110.
• Excess-3: digit + 3; self-complementing.
• Gray: g = b ⊕ (b >> 1); back: bᵢ = bᵢ₊₁ ⊕ gᵢ (running XOR from the MSB). Neighbours differ in one bit.
• Even parity makes the count of 1s even; detects odd numbers of flipped bits.

CInterleaved GATE-style questions

Q1NAT1 markSign-magnitude

What decimal value does the 8-bit sign-magnitude pattern 1011 0110 represent?

Numerical answer: ________

Q2MCQ1 markRange

The range of n-bit sign-magnitude numbers is:

• (A) 0 … 2ⁿ − 1
• (B) −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1
• (C) −(2ⁿ⁻¹ − 1) … 2ⁿ⁻¹ − 1
• (D) −2ⁿ … 2ⁿ

Q3NAT2 marks2's complement value

What decimal value does the 8-bit 2's-complement pattern 1000 0000 represent?

Numerical answer: ________

Q4MCQ1 markOverflow

In 8-bit 2's complement, which of these sums overflows?

• (A) −100 + 50
• (B) 100 + 27
• (C) −64 + −64
• (D) −100 + −29

Q5NAT1 markSubtraction

In 8-bit 2's complement, 0001 0000 − 0010 0001 gives a pattern. What value does it represent?

Numerical answer: ________

Q6NAT2 marksBooth

How many additions plus subtractions does Booth's algorithm perform for the 8-bit multiplier 1010 1010?

Numerical answer: ________

Q7NAT1 markExcess-3

The excess-3 code of the digit 7, read as a 4-bit unsigned number, is:

Numerical answer: ________

Q8NAT2 marksGray

What is the decimal value whose 4-bit Gray code is 1000?

Numerical answer: ________

DAnswer Vault