Packing Section and Roll Number into One Byte
A small school in a hill town has an attendance kiosk built by last year's computer club. Each student's record is stored in one 8-bit byte: the lower 6 bits hold the roll number (1-48) and the upper 2 bits hold the section code (00 = A, 01 = B, 10 = C). The kiosk writes a byte when a student taps an RFID card and displays the section and roll number. This year the principal adds a fourth section, D, and admits 12 more students, so section A now has 56 students (roll numbers 1-56). The club president suggests simply changing the section code for D to 11 and keeping the roll number in 6 bits, because '6 bits can hold up to 63'. On the first day, section D roll number 12 displays correctly, but a teacher's master list built with a signed 6-bit field shows section A roll 40 as a negative number. A second problem appears: the kiosk uses the byte 11111111 as a special 'no card' marker, and the club worries that a valid student record could collide with it. The club has one week before the state inspection.
1. Verify the president's claim that 6 bits are enough for roll numbers 1-56. State the exact range of unsigned 6-bit values, the number of distinct values, and whether any section/roll combination this year collides with the no-card marker 11111111. Show your bit reasoning.
Read the worked answer
6 bits give 2^6 = 64 distinct patterns, numbered 0 to 63 in unsigned form. Roll numbers 1-56 need only 56 of those patterns, so the claim is true for the current roll range: the largest value 56 is 111000 in binary, well below 111111 (63). There are 8 unused codes, including 0.
The no-card marker is the whole byte 11111111, decimal 255. For a valid record to equal 255, the section bits must be 11 (section D) and the roll bits must be 111111 (63), producing D-63. This year section D has only 12 students, so D-63 does not exist and there is no current collision. The risk is real if D grows to 63 students or if a future section also uses 11 with roll 63. A safer design would avoid using all-ones as an in-band marker, or would reserve roll 0 or a separate validity bit.
2. The diagnostic mode reads the lower 6 bits as a signed two's-complement number. Explain what section A roll 40 displays in diagnostic mode, and whether the normal display is affected. Show the conversion.
Read the worked answer
40 decimal equals 32 + 8, so in 6 bits it is 101000. In 6-bit two's complement the leftmost bit has place value -32, not +32. Therefore 101000 represents -32 + 8 = -24. Diagnostic mode would display -24 for section A roll 40.
The stored bits are still 101000, and the normal display reads them as unsigned, so the normal display continues to show 40. The fault is in the diagnostic mode's interpretation and in any comparison that treats the sign bit as a value. For example, a check such as 'roll > 0' would wrongly classify roll 40 as invalid. The fix is to mask the lower 6 bits and treat them as unsigned during normal and diagnostic display, reserving a separate signed field only if negative values are genuinely needed.
3. The school expects up to 5 sections and 70 students per section within three years. Propose a bit allocation for a new record format, and explain why the current 8-bit byte cannot work. Include one simple way to keep the old kiosk working during the transition.
Read the worked answer
Five sections need ceil(log2 5) = 3 bits, because 2 bits give only four codes. Seventy roll numbers need ceil(log2 70) = 7 bits, because 6 bits give only 64 codes and 70 > 63. The minimum is 3 + 7 = 10 bits, and 5 x 70 = 350 distinct section-roll combinations, which exceeds the 256 patterns available in an 8-bit byte. Thus the current format cannot represent all future students even if every bit is used.
A workable 16-bit record is: 3 bits for section (or 4 bits for future growth), 7 bits for roll number, and the remaining 6 bits for flags such as card-valid, parity, or a format version. For the transition, the old kiosk can keep a lookup table that maps each new 16-bit student ID to a legacy byte only for sections A-C and rolls 1-48; new sections use a second reader or a software update. The all-ones marker should be moved out of the student ID space, for example by using a separate validity bit.