Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 3 / Solution Created 2026-09-24 Updated 2026-10-14
View more
Extract one four-bit digit at a time, beginning at the most significant end of the Java int. A lookup string supplies characters, but no library performs the conversion:
java
static String toHex(int value) {
    String digits = "0123456789abcdef";
    String answer = "";
    boolean started = false;
    for (int shift = 28; shift >= 0; shift -= 4) {
        int digit = (value >>> shift) & 15;
        if (started || digit != 0 || shift == 0) {
            answer = answer + digits.charAt(digit);
            started = true;
        }
    }
    return answer;
}
The logical right bit shift >>> inserts zeros, and the bit mask 15 retains exactly the low four bits of the shifted word. Each emitted character is therefore the corresponding hexadecimal digit. The started flag suppresses leading zero digits; the shift == 0 exception makes zero produce "0", rather than an empty string.
A negative Java integer uses two's complement. Its top bit is set, so the first extracted digit is between eight and fifteen and all eight digits are emitted. We interpret its original 32-bit pattern, without taking an absolute value or negating a potentially unnegatable minimum integer. In particular, toHex(19) returns "13", toHex(-1) returns "ffffffff", and toHex(Integer.MIN_VALUE) returns "80000000". There are exactly eight iterations, so for this fixed word size the time complexity is constant.
Read the full article
Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 8 / b / ii / Solution Created 2026-09-24 Updated 2026-10-14
View more
Use strength reduction on the disassembled hot instructions. In a fixed-width wrapping integer model,
(1)
The first replacement is a single left bit shift. For the second, preserve the original operand in a register, shift a copy left by four and subtract the original:
text
rOriginal = x
rResult = rOriginal << 4
rResult = rResult - rOriginal
This avoids a general multiplication if shifts and subtraction are cheaper on the target processor. The two identities hold for positive and negative two's complement operands when only the low result bits are required.
Because only a binary is available, patch the machine instructions and adjust displaced branches or use a jump to a replacement code block if the new sequence does not fit. Preserve live registers and the calling convention. If later instructions consume overflow or other condition flags, or the original multiplication produces a double-width result or traps on overflow, matching only the low-word arithmetic is insufficient: those effects must be reproduced or the transformation rejected. Finally, measure the modified program; a fast hardware multiply need not be slower than several replacement instructions.
Read the full article