Condition flags (N, Z, C, V) in ARM Architecture - Time & Space Complexity

Time Complexity: Condition flags (N, Z, C, V)

O(n)

Understanding Time Complexity

We want to understand how checking and using condition flags affects the time it takes for ARM instructions to run.

Specifically, how does the use of these flags change the number of steps the processor takes?

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet.

    CMP R0, R1      // Compare values in R0 and R1
    BEQ label      // Branch if equal (Z flag set)
    ADD R2, R2, #1 // Increment R2
label:
    SUBS R3, R3, #1 // Subtract 1 from R3 and update flags
    BNE label      // Branch if not equal (Z flag clear)
    

This code compares registers, uses condition flags to decide branching, and loops until R3 reaches zero.

Identify Repeating Operations

Look for repeated instructions or loops that depend on condition flags.

• Primary operation: The loop controlled by the SUBS and BNE instructions repeats.
• How many times: The loop runs as many times as the initial value in R3.

How Execution Grows With Input

The number of loop iterations depends directly on the value in R3.

Input Size (R3 initial)	Approx. Operations
10	About 10 loop cycles
100	About 100 loop cycles
1000	About 1000 loop cycles

Pattern observation: The execution time grows linearly with the initial value of R3.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the code increases in direct proportion to the input size n (the value in R3).

Common Mistake

[X] Wrong: "Using condition flags makes the code run in constant time regardless of input."

[OK] Correct: Condition flags only control branching; the number of loop iterations still depends on input size, so time grows with n.

Interview Connect

Understanding how condition flags affect loops helps you explain how low-level code controls flow and performance, a useful skill in many programming and debugging situations.

Self-Check

"What if the loop used a different condition flag, like the carry flag (C), instead of zero (Z)? How would that affect the time complexity?"

Practice

1. Which condition flag in ARM architecture indicates that the result of an operation is zero?

easy

A. Z flag

B. N flag

C. C flag

D. V flag

Solution

1. Step 1: Understand the meaning of each flag

   The Z flag is set when the result of an operation is zero. The N flag indicates a negative result, C is for carry or borrow, and V is for signed overflow.

2. Step 2: Identify the zero result flag

   Since the question asks for the flag indicating zero result, the correct flag is Z.

3. Final Answer:

   Z flag -> Option A

4. Quick Check:

   Zero result = Z flag [OK]

Hint: Zero result always sets the Z flag [OK]

Common Mistakes:

• Confusing N (negative) with Z (zero)
• Thinking C means zero result
• Mixing V (overflow) with zero flag

2. Which of the following is the correct way to check the Negative flag (N) in ARM assembly condition codes?

easy

A. BMI (Branch if Minus)

B. BEQ (Branch if Equal)

C. BHS (Branch if Higher or Same)

D. BVS (Branch if Overflow Set)

Solution

1. Step 1: Recall ARM condition codes

   BEQ checks Z flag (zero), BMI checks N flag (negative), BHS checks C flag (carry set), and BVS checks V flag (overflow).

2. Step 2: Match the condition code to N flag

   The correct code for checking the Negative flag is BMI (Branch if Minus).

3. Final Answer:

   BMI (Branch if Minus) -> Option A

4. Quick Check:

   Negative flag = BMI [OK]

Hint: BMI always checks the Negative (N) flag [OK]

Common Mistakes:

• Using BEQ for negative instead of zero
• Confusing BHS with N flag
• Mixing BVS (overflow) with negative flag

3. Consider an ARM instruction that adds two 8-bit numbers: 0x7F + 0x01. Which condition flags will be set after this operation?

medium

A. N=0, Z=1, C=0, V=0

B. N=0, Z=0, C=1, V=0

C. N=1, Z=0, C=1, V=1

D. N=1, Z=0, C=0, V=1

Solution

1. Step 1: Calculate the sum and check overflow

   0x7F (127 decimal) + 0x01 (1 decimal) = 128 decimal (0x80). This fits in 8 bits but crosses the positive max for signed 8-bit (127), causing signed overflow.

2. Step 2: Determine flags

   N flag is 1 (MSB of 0x80 is 1, negative result), Z=0 since result is not zero, C=0 because no carry out beyond 8 bits, V=1 because signed overflow occurred.

3. Final Answer:

   N=1, Z=0, C=0, V=1 -> Option D

4. Quick Check:

   Signed overflow sets V=1, no zero or carry [OK]

Hint: Overflow sets V, zero result sets Z, carry sets C [OK]

Common Mistakes:

• Confusing carry with overflow
• Assuming zero flag set for non-zero result
• Misinterpreting negative flag for unsigned sum

4. An ARM instruction adds 0xFF and 0x02 and sets the condition flags. The flags are incorrectly showing C=0. What is the likely error?

medium

A. The addition result was zero, so C should be 0

B. The instruction did not update the condition flags

C. The V flag was set instead of C flag

D. The processor does not support carry flag

Solution

1. Step 1: Analyze the addition and expected flags

   0xFF (255) + 0x02 (2) = 0x101 (257), which exceeds 8 bits, so carry (C) should be set to 1.

2. Step 2: Identify why C flag is 0

   If C=0 incorrectly, likely the instruction did not update the condition flags because the 'S' suffix (e.g., ADDS) was missing, so flags were not changed.

3. Final Answer:

   The instruction did not update the condition flags -> Option B

4. Quick Check:

   Missing 'S' means flags unchanged [OK]

Hint: Use 'S' suffix to update flags after arithmetic [OK]

Common Mistakes:

• Assuming carry flag updates automatically
• Confusing overflow (V) with carry (C)
• Believing processor lacks carry flag

5. You want to write an ARM assembly routine that subtracts two numbers and branches if the result is negative or zero. Which condition flags and branch instructions should you use together?

hard

A. Check V flag with BVC and C flag with BCC, branch if both clear

B. Check C flag with BCS and V flag with BVS, branch if either set

C. Check N flag with BMI and Z flag with BEQ, branch if either set

D. Check Z flag with BNE and N flag with BPL, branch if both clear

Solution

1. Step 1: Identify flags for negative and zero results

   Negative result sets N flag, zero result sets Z flag.

2. Step 2: Choose branch instructions for these flags

   BMI branches if N=1 (negative), BEQ branches if Z=1 (zero). To branch if either negative or zero, use BMI and BEQ together.

3. Final Answer:

   Check N flag with BMI and Z flag with BEQ, branch if either set -> Option C

4. Quick Check:

   Negative = BMI, Zero = BEQ [OK]

Hint: Use BMI for negative and BEQ for zero branches [OK]

Common Mistakes:

• Using BNE instead of BEQ for zero
• Confusing carry or overflow flags for sign checks
• Trying to branch on both flags cleared instead of set