Interview Traps: K-Map Adjacency Rules and Number Representation
Explain the mathematical reasons behind Gray-code K-map ordering, edge wrap-around, and the power-of-2 grouping rule, and give the precise reasoning (not folklore) behind two's-complement asymmetry and BCD's wasted codes.
K-map and number-representation questions are popular interview traps because the 'rules' (Gray-code order, only power-of-2 groups, two's complement has one extra negative value) are usually taught as things to memorize rather than things to derive. An interviewer who asks 'why' instead of 'what' is checking whether you can reconstruct the rule from the underlying binary/Boolean structure, which is exactly what the five answers below do.
Why are K-map cells arranged in Gray-code order?
A Karnaugh map's row and column headers are ordered in Gray code (00, 01, 11, 10 for two variables) rather than plain binary order (00, 01, 10, 11) specifically so that any two physically adjacent cells — horizontally or vertically neighboring — differ in exactly one variable's value. That single-bit-difference property (Hamming distance 1) is what makes 'adjacent on the grid' the same thing as 'algebraically combinable': two adjacent minterms like A'BC and A'BC' can be combined into A'B by the identity X.Y + X.Y' = X, and that combination is only clean when the two cells differ in exactly one variable.
If the map instead used plain binary order, adjacent columns like 01 and 10 would differ in two bits, so cells next to each other on the page would no longer correspond to terms that combine into a smaller expression. The entire visual grouping method — circle adjacent 1s, read off a simplified term — depends on physical adjacency always meaning single-variable difference, and Gray-code ordering is what guarantees that everywhere on the map, not just in some rows.
A common shallow answer is 'it's just the convention K-maps use.' The stronger answer names the actual invariant being preserved: adjacency on the grid must equal Hamming distance 1, and Gray code is the unique simple bit ordering (for each row/column axis) that achieves that everywhere, including at the wrap-around edges (see next question).
Why can K-map edges be grouped (wrap-around adjacency)?
The leftmost and rightmost columns (and the top and bottom rows) of a K-map are logically adjacent even though they are not visually next to each other in the flattened 2D drawing, because the Gray-code sequence used for the headers is itself cyclic: for two variables, the sequence 00, 01, 11, 10 wraps back to 00, and the last entry (10) differs from the first (00) in exactly one bit, just like every other consecutive pair in the sequence. The K-map is really a torus (a grid that wraps around in both directions), and the flat rectangle drawn on paper is only one way of unrolling it.
This means a group spanning the two outer columns, or the two outer rows, or all four corners of the map simultaneously, is exactly as valid as a group of visually touching cells — the underlying requirement (Hamming distance 1 between all cells in a pairwise-adjacent chain) is satisfied identically. Students who treat the wrap-around as 'a special trick' rather than a consequence of the cyclic Gray-code ordering often miss valid four-corner or edge groupings when simplifying larger maps.
The trap answer is 'the edges aren't really connected, it's just a visual convention interviewers expect you to know.' The stronger answer explains *why* it's mathematically legitimate: the Gray-code sequence is cyclic, so the adjacency invariant (1-bit difference) holds across the wrap exactly as it holds between any other pair of neighboring cells.
Why can a K-map group contain 8 cells but not 6?
A valid K-map grouping must contain exactly 2^n cells (1, 2, 4, 8, 16, ...) because grouping 2^n adjacent cells is what algebraically eliminates exactly n variables from the resulting product term. Combining two adjacent cells (2^1) removes 1 variable via X.Y + X.Y' = X; combining two such pairs into a group of four (2^2) removes 2 variables by applying that identity twice; a group of eight removes 3 variables, and so on. Each doubling of group size corresponds to one more application of the same adjacency-elimination identity, which only works cleanly when the group size is itself a power of 2 and forms a valid rectangular (including wrap-around) shape.
Six cells cannot be covered by one legal group because 6 = 2 × 3 is not a power of 2 — there is no way to arrange six 1s into a single rectangle (flat or wrapped) where every cell is reachable from every other by the repeated 1-bit-difference pairing the elimination identity requires. In practice, six adjacent 1s must be simplified as two separate groups (e.g., a group of 4 plus a group of 2), each independently valid, rather than one group of 6.
The trap answer is 'because 6 isn't even' — evenness isn't the rule (2, 4, 8, 16 are all even, but so is 6). The real constraint is specifically 'power of 2 and rectangular/torus-shaped,' which is what guarantees a consistent, well-defined set of variables gets eliminated for the whole group at once.
Why does two's complement have one extra negative value?
For an n-bit two's-complement system, the representable range is -2^(n-1) to +2^(n-1) - 1 — for example, an 8-bit system covers -128 to +127. There are 2^n total distinct bit patterns available, and exactly one of them (all zeros) is used to represent 0. Because two's complement has no separate representation for negative zero (unlike sign-magnitude or one's complement, both of which waste a code on '-0'), that saved code is instead reassigned to extend the negative range by one extra value: the pattern 1000...0, which represents -2^(n-1) (e.g., -128 in 8 bits), has no positive counterpart at all, since +2^(n-1) (+128) would require a 9th bit to represent.
This is why the range is deliberately asymmetric rather than a coding accident: 0 consumes one slot that would otherwise be 'positive,' so the negative side ends up with exactly one more representable value (2^(n-1) negative numbers, from -1 down to -2^(n-1)) than the positive side (2^(n-1) - 1 positive numbers, from +1 up to +2^(n-1) - 1).
The trap answer is 'it's just a rounding artifact of binary arithmetic.' The precise answer is structural: single-representation zero is what frees up the extra code, and that freed code is what becomes the unpaired most-negative value — which is also exactly why negating the most-negative number (like -128 in 8-bit two's complement) overflows, since +128 simply doesn't exist in the representable range.
Why does BCD waste some 4-bit combinations?
Binary-Coded Decimal (BCD) encodes each individual decimal digit (0-9) using a fixed 4-bit nibble, but 4 bits can represent 16 distinct patterns (0000 through 1111). Only the first ten of those patterns (0000-1001) are ever used, one per decimal digit; the remaining six (1010 through 1111, representing decimal 10-15) are invalid/unused in every BCD digit position. That means 6 of every 16 possible 4-bit codes — 37.5% of the encoding space — are deliberately wasted, per digit, everywhere BCD is used.
This waste is a conscious trade-off, not an oversight: BCD sacrifices storage and arithmetic density in exchange for a direct, trivial mapping between each stored nibble and a single human-readable decimal digit, which massively simplifies decimal display (seven-segment decoders), decimal input, and decimal rounding in financial or instrumentation systems where introducing binary-to-decimal conversion error is unacceptable. Pure binary encoding of the same value would use every bit pattern (no waste) but would require nontrivial binary-to-decimal conversion logic before it could be displayed or printed correctly.
The trap answer is simply 'because binary is more efficient than BCD' — true, but it doesn't explain *why* BCD is inefficient in that specific way. The precise answer names the exact mechanism: restricting a 4-bit field to only 10 of its 16 possible codes, purely to keep a 1:1 nibble-to-decimal-digit correspondence.
Two's complement range and BCD code space
K-map group sizes must be a power of 2 (1,2,4,8,16,...) and form a valid rectangle or wrap-around rectangle; a group of size 2^n eliminates exactly n variables from the resulting term. Gray-code adjacency (Hamming distance 1 between consecutive codes, including the wrap from the last code back to the first) is what makes K-map grouping and rotary-encoder position reading both work.
Two's complement, n bits:
Total patterns = 2^n
Range = -2^(n-1) ... +2^(n-1) - 1
Example (n=8): -128 ... +127
Note: |min| = 128 has NO positive counterpart in 8 bits (+128 needs 9 bits)
BCD, per decimal digit (4 bits):
Total 4-bit codes = 16 (0000..1111)
Valid BCD codes = 10 (0000..1001, i.e. decimal 0-9)
Wasted codes = 6 (1010..1111) -- 37.5% of the 4-bit space per digitCode Examples
The 6 ones cannot be circled as a single group because 6 is not a power of 2 and no single rectangular (or wrap-around) region of exactly those 6 cells exists. The correct simplification finds the largest valid power-of-2 groups that cover all six 1s, here a group of 4 and a group of 2, each independently satisfying the 'power of 2 and rectangular' rule.
F = A'B' + A'BD' -- two legal groups (sizes 4 and 2), never one illegal group of 6
Common mistake: Trying to circle all 6 ones as one region is the classic beginner mistake — always decompose into the largest valid power-of-2 sub-groups that together cover every 1, even if that means overlapping groups.
4-variable K-map (rows AB in Gray order 00,01,11,10; cols CD in Gray order 00,01,11,10)
Suppose 1s occupy these 6 cells: AB=00,CD=00 | AB=00,CD=01 | AB=00,CD=11 | AB=00,CD=10 | AB=01,CD=00 | AB=01,CD=01
That is: all 4 cells of row AB=00 (a valid group of 4, eliminates C and D -> term A'B')
plus 2 cells of row AB=01 at CD=00 and CD=01 (a valid group of 2 -> term A'BD')
Result: F = A'B' + A'BD' (two separate groups; NOT one 6-cell group)Gray-code adjacency and K-map wrap-around
Because Gray-code order is cyclic, the physically outer edges of a K-map are logically adjacent to each other, enabling valid wrap-around groupings.
2-variable Gray-code sequence (cyclic):
00 -> 01 -> 11 -> 10 -> (back to 00)
each arrow changes exactly ONE bit, including the wrap arrow 10->00
4x4 K-map column headers (CD), Gray order:
00 01 11 10
[c0] [c1] [c2] [c3]
^______________|
wrap: c3(10) and c0(00) differ in exactly 1 bit -> logically adjacent
even though they are drawn at opposite ends of the rowWhy this matters beyond the interview
K-map adjacency rules are the manual version of what logic synthesis tools do automatically (via Quine-McCluskey or espresso-style algorithms) when minimizing combinational logic to reduce gate count and propagation delay in real chips. Two's-complement asymmetry is a live source of bugs in production code: abs(INT_MIN) in many languages silently overflows back to INT_MIN because +2^(n-1) cannot be represented, which has caused real security and correctness bugs. BCD's deliberate code waste is still the standard in financial systems, digital multimeters, and calculators specifically because it guarantees exact decimal rounding, which binary floating-point famously cannot.
Two's complement's range asymmetry (one extra negative value) is just a quirk/rounding error of binary math.
The asymmetry is structural: two's complement has only one representation for zero (no '-0'), so that otherwise-redundant code is reassigned to extend the negative range by exactly one value (-2^(n-1)), which has no positive counterpart representable in the same bit width.
This distinction matters concretely: it's exactly why negating the minimum representable value (e.g., -128 in an 8-bit signed type) overflows instead of producing a valid result — a classic source of real integer-overflow bugs, not just a trivia fact.
Why are K-map row and column headers ordered in Gray code instead of plain binary order? A. Gray code is simply the historical convention with no functional reason B. So that any two physically adjacent cells always differ in exactly one variable, which is required for the adjacent-cell grouping/simplification method to work correctly C. Because Gray code numbers are smaller than binary numbers D. Because Gray code is required by IEEE floating-point standards
B. So that any two physically adjacent cells always differ in exactly one variable, which is required for the adjacent-cell grouping/simplification method to work correctly — Grouping adjacent K-map cells relies on the identity X.Y + X.Y' = X, which only applies cleanly when the two combined minterms differ in exactly one variable (Hamming distance 1). Gray-code ordering (00,01,11,10) guarantees that every pair of physically neighboring cells satisfies this, while plain binary order (00,01,10,11) does not (01 and 10 differ in two bits).
Why is a 6-cell region on a K-map never a single valid group? A. 6 is an even number, and only odd-sized groups are allowed B. Valid groups must contain 2^n cells (1,2,4,8,...) forming a rectangle, and 6 = 2x3 is not a power of 2 C. K-maps only support groups up to size 4 D. Six cells always contain a 0, which is not allowed in a group
B. Valid groups must contain 2^n cells (1,2,4,8,...) forming a rectangle, and 6 = 2x3 is not a power of 2 — Each doubling of a group's size corresponds to eliminating one more variable via repeated application of X.Y+X.Y'=X. That only produces a single clean product term when the group size is a power of 2 and forms a legal rectangular (or wrap-around) shape; 6 cells must instead be split into separate valid groups, such as a 4-group plus a 2-group.
In an 8-bit two's-complement system, why is the representable range -128 to +127 instead of a symmetric -127 to +127 or -128 to +128? A. It's an arbitrary design choice with no underlying reason B. Because two's complement has exactly one representation for zero, freeing up the bit pattern 1000 0000 to represent an extra negative value (-128) that has no representable positive counterpart in 8 bits C. Because the sign bit is only sometimes counted D. Because +128 requires floating-point representation
B. Because two's complement has exactly one representation for zero, freeing up the bit pattern 1000 0000 to represent an extra negative value (-128) that has no representable positive counterpart in 8 bits — Unlike sign-magnitude or one's complement, two's complement has no separate '-0,' so that otherwise-wasted code is reassigned to extend the negative range by one. This gives 2^(n-1) negative values but only 2^(n-1)-1 positive values, and is exactly why negating the minimum value (-128) overflows back to itself in 8-bit arithmetic.
Why does BCD (Binary-Coded Decimal) waste 6 out of every 16 possible 4-bit codes? A. Because those 6 codes are reserved for error signaling in all BCD systems B. Because BCD restricts each 4-bit nibble to only the 10 codes 0000-1001 to keep a direct 1:1 correspondence with a single decimal digit (0-9), leaving 1010-1111 unused C. Because 4 bits cannot actually represent more than 10 values D. Because BCD reserves 6 bits for parity checking
B. Because BCD restricts each 4-bit nibble to only the 10 codes 0000-1001 to keep a direct 1:1 correspondence with a single decimal digit (0-9), leaving 1010-1111 unused — A 4-bit nibble can encode 16 distinct patterns, but BCD only ever uses 10 of them (one per decimal digit), leaving 1010-1111 invalid. This is a deliberate trade-off of storage/arithmetic density in exchange for trivial decimal display and exact decimal rounding, which is why BCD remains standard in calculators and financial hardware despite binary being denser.
An 8-bit register holds the two's-complement value 1000 0000. What decimal value does it represent, and what happens if you try to negate it (compute its two's complement)? Explain the result in terms of the range asymmetry.
1000 0000 represents -128 (the unpaired extra negative value, since +128 is outside the representable 8-bit range). Negating it: invert all bits -> 0111 1111, add 1 -> 1000 0000 — you get -128 back again, an overflow, because the true mathematical result (+128) needs 9 bits and cannot be represented in an 8-bit two's-complement register. This is the direct real-world consequence of two's complement having exactly one more negative value than positive values.
Recall the range for n=8 is -128 to +127, and negation in two's complement is 'invert all bits, then add 1.'