0210MediumMathBit Manipulation

Microcode Divide Step

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

You are writing microcode for a small motor controller. Its arithmetic unit can add, subtract, compare, and shift a register left or right, and that is the whole instruction set: there is no multiply instruction, no divide instruction and nothing that hands back a remainder. The firmware still needs a divide step, so you have to build one.

Given two signed integers value and step, report how many whole steps of size step go into value, carrying the sign the pair of operands implies. Anything left over is thrown away, so the count is cut towards zero and never rounded away from it: 19 over 5 gives 3, and -19 over 5 gives -3.

The result is latched into a signed 32-bit register, which holds values from -2^31 up to 2^31 - 1. Should the cut count sit above that ceiling, latch the ceiling 2^31 - 1 instead; should it sit below the floor, latch the floor -2^31 instead. The caller never passes a step of zero.

Build the count from addition, subtraction, comparison and bit shifts only, the way the unit would. Do not reach for a multiply, divide or remainder operator anywhere in your answer.

Examples

Example 1

Input: value = 23, step = -4
Output: -5

Five steps of size 4 fit inside 23 and 3 is left over. The operands carry opposite signs, so the count is negative and the leftover is discarded: -5.

Example 2

Input: value = -30, step = 7
Output: -4

Four steps of size 7 fit inside 30 with 2 left over, and the opposite signs make the count -4.

Example 3

Input: value = -2147483648, step = -1
Output: 2147483647

Two negative operands give an exact count of 2147483648, which is one above what the register holds, so the ceiling 2147483647 is latched.

Constraints

-2^31 <= value, step <= 2^31 - 1
step != 0

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def microcode_divide_step(value: int, step: int) -> int:

Java

public int microcodeDivideStep(int value, int step)

The intended approach

Time O(log V), V the magnitude of value: at most 32 bit positionsSpace O(1)

Settle the sign first from whether the two operands disagree, then work with magnitudes only. Sweep the bit positions from 31 down to 0: at each position, shift the step left that many places, and when the shifted step still fits inside what remains of the magnitude, subtract it and set that bit of the count. That builds the count one binary digit at a time using nothing but shifts, comparisons and subtraction. Reapply the sign at the end, then latch against the register ends, which is what makes the -2^31 over -1 case come back as the ceiling.

Pythonentry point: microcode_divide_step

def microcode_divide_step(value, step):
    # Time: O(log V) -- one pass down 32 bit positions, V the magnitude of value.
    # Space: O(1).
    flip = (value < 0) != (step < 0)
    top = -value if value < 0 else value
    unit = -step if step < 0 else step
    count = 0
    place = 31
    while place >= 0:
        chunk = unit << place
        if chunk <= top:
            top -= chunk
            count += 1 << place
        place -= 1
    if flip:
        count = -count
    if count > 2147483647:
        return 2147483647
    if count < -2147483648:
        return -2147483648
    return count

The obvious version

Peel one copy of the step magnitude off the value magnitude at a time and tally how many come away, then apply the sign and latch. O(V / S) subtractions.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_microcode_divide_step(value, step):
    flip = (value < 0) != (step < 0)
    top = -value if value < 0 else value
    unit = -step if step < 0 else step
    count = 0
    while top >= unit:
        top -= unit
        count += 1
    if flip:
        count = -count
    if count > 2147483647:
        return 2147483647
    if count < -2147483648:
        return -2147483648
    return count

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in