Bits & memory toolkit

ACompressed recap

🧾

Hex digit = 4 bits; sizes as powers of two (K = 2¹⁰, M = 2²⁰, G = 2³⁰); 2ⁿ locations need n address bits; N items need ⌈log₂ N⌉ bits. Two's complement: range −2ⁿ⁻¹ … 2ⁿ⁻¹−1, negate by invert + 1, sign-extend by copying the MSB; overflow when same-sign operands give the other sign. Parts: MUX (k selects for 2ᵏ inputs), decoder (one active output), full adder, register (load + clock edge), tri-state bus (one driver). Memory: capacity = 2^(address bits) × unit; big- vs little-endian; aligned addresses are multiples of the object size.

BMerged rule card

0.2.1 Binary and hex, powers of two, size units, log₂: n bits name 2ⁿ things

• One hex digit = 4 bits. 1 K = 2¹⁰, 1 M = 2²⁰, 1 G = 2³⁰.
• 2ⁿ locations ↔ n address bits. N items need ⌈log₂ N⌉ bits.
• 2ᵃ / 2ᵇ = 2ᵃ⁻ᵇ: convert sizes to exponents before dividing.
• B = byte (8 bits), b = bit.

0.2.2 Signed integers: 2's complement, ranges, sign extension, overflow; bit fields and shifts

• Unsigned: 0 … 2ⁿ−1. Two's complement: −2ⁿ⁻¹ … 2ⁿ⁻¹−1; MSB weight −2ⁿ⁻¹.
• Negate: invert and add 1. Sign-extend by copying the MSB.
• Signed overflow: same-sign operands, other-sign result. Carry out = unsigned overflow.
• Left shift ×2ᵏ; logical right shift for unsigned; arithmetic right shift keeps the sign.
• Field bits i..j: (word >> j) AND (2^(i−j+1) − 1).

0.2.3 Digital building blocks: gates, MUX, decoder, adder, flip-flops, registers, clock, tri-state bus

• 2ᵏ-to-1 MUX: k select lines. k-to-2ᵏ decoder: one active output.
• Full adder: sum = a⊕b⊕c, carry = ab + c(a⊕b). Ripple adder: carries pass stage to stage.
• Register = n flip-flops + load; changes only at the clock edge. Counter adds 1 per edge.
• Tri-state: 0, 1 or Z; exactly one driver per bus per cycle.
• Clock cycle ≥ slowest register-to-register path.

0.2.4 Memory as an array: address, word, byte vs word addressing, endianness, alignment

• Capacity = 2^(address bits) × addressable unit.
• Byte-addressable: word number = ⌊address / word size⌋.
• Big-endian: MSB at lowest address. Little-endian: LSB at lowest address.
• k-byte object aligned ⇔ address multiple of k; misaligned word = 2 accesses.
• Data bus width = bytes per transfer.

CInterleaved GATE-style questions

Q1NAT1 markAddress bits

A byte-addressable memory is 512 MB. Address bits?

Numerical answer: ________

Q2NAT2 marksTwo's complement

The 16-bit two's-complement value 0xFF9C equals what decimal number?

Numerical answer: ________

Q3MCQ1 markMUX

To select one of 16 registers for each of 32 bit positions using MUXes, you need:

• (A) 32 MUXes of 16-to-1, sharing 4 select lines
• (B) one 4-to-16 decoder only
• (C) one 16-to-1 MUX with 16 select lines
• (D) 16 MUXes of 32-to-1

Q4NAT2 marksWord-addressable

A memory has 22-bit addresses and 64-bit words, word-addressable. Capacity in MB?

Numerical answer: ________

Q5MCQ2 marksEndianness

A big-endian machine stores the 32-bit value 0x89ABCDEF at address 0. A little-endian machine then reads those same four bytes as one 32-bit little-endian value. It gets:

• (A) 0x98BADCFE
• (B) 0xEFCDAB89
• (C) 0x89ABCDEF
• (D) 0xFEDCBA98

Q6MSQ2 marksOverflow and carry

For the 8-bit addition 1100 0000 + 1100 0000 (both read as signed), which hold?

• (A) Signed overflow occurs.
• (B) The unsigned result is correct.
• (C) There is a carry out of the MSB.
• (D) The signed result is −128.

Q7NAT1 markDecoder

How many outputs does a decoder with 5 inputs have?

Numerical answer: ________

Q8NAT2 marksBits for counts

A cache has 2,048 lines grouped into sets of 4 lines each. How many bits are needed to number a set?

Numerical answer: ________

Q9MCQ1 markAlignment

Reading a 4-byte integer stored at byte address 4,098 on a machine whose memory delivers aligned 4-byte words needs:

• (A) 3 accesses
• (B) 1 access
• (C) 2 accesses
• (D) 4 accesses

DAnswer Vault