ITPEC FE Morning October 2021 Question 2

For a non-negative integer x, which of the following gives the remainder after division of x by 8 as a result?

a)Performing a bitwise AND operation on x and 7b)Performing a bitwise AND operation on x and 248c)Performing a bitwise OR operation on x and 8d)Performing a bitwise OR operation on x and 15

Explanation

Bitwise AND with 7 — dividing by 8 = 2³ shifts out the lowest three bits, so those three bits are the remainder.

Write x = 8q + r: the bits from position 3 upward hold 8q and the lowest three bits hold r, a value from 0 to 7. The mask 7 = 00000111 keeps exactly those three bits and clears the rest.

Example: 19 = 10011, and 10011 AND 00111 = 00011 = 3, while 19 ÷ 8 = 2 remainder 3.

Answer (a)

Why not others:

•(b) AND 248 — 248 = 11111000 keeps the upper bits and clears the lowest three, giving the multiple of 8 at or below x (19 becomes 16), the opposite of the remainder
•(c) OR 8 — OR can only set bits; bit 3 is always 1 in the result, so it is at least 8, while a remainder is at most 7
•(d) OR 15 — sets the lowest four bits, so the result is at least 15

Key rule: For a divisor 2ⁿ, the remainder is x AND (2ⁿ − 1): a mask of n ones keeps the remainder bits, and shifting right by n gives the quotient.

Basic Theory · AI-written, may contain errors

Previous Next

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.