Signed and unsigned integers in ARM Architecture - Time & Space Complexity

Time Complexity: Signed and unsigned integers

O(n)

Understanding Time Complexity

When working with signed and unsigned integers in ARM architecture, it is important to understand how operations on these types behave as input size changes.

We want to know how the time to perform arithmetic or comparisons grows when the numbers get larger or when many numbers are processed.

Scenario Under Consideration

Analyze the time complexity of the following ARM instructions handling signed and unsigned integers.

    LDR R0, [R1]       // Load integer from memory
    CMP R0, #0         // Compare integer with zero
    BGE label_signed   // Branch if signed greater or equal
    CMP R0, #0         // Compare integer with zero (unsigned)
    BHS label_unsigned // Branch if unsigned higher or same
    

This code loads an integer and performs signed and unsigned comparisons to decide program flow.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single load and two comparisons per integer.
• How many times: Once per integer processed; if processing multiple integers, these operations repeat for each.

How Execution Grows With Input

Each integer requires a fixed number of instructions: load and two comparisons.

Input Size (n)	Approx. Operations
10	30 instructions
100	300 instructions
1000	3000 instructions

Pattern observation: The total instructions grow directly in proportion to the number of integers processed.

Final Time Complexity

Time Complexity: O(n)

This means the time to process signed and unsigned integers grows linearly with the number of integers.

Common Mistake

[X] Wrong: "Signed and unsigned comparisons take different amounts of time depending on the number size."

[OK] Correct: ARM instructions for signed and unsigned comparisons run in constant time regardless of the integer value size.

Interview Connect

Understanding how signed and unsigned integer operations scale helps you reason about performance in low-level programming and embedded systems.

Self-Check

"What if we added a loop that processes each integer twice, once signed and once unsigned? How would the time complexity change?"

Practice

1.

What is the main difference between signed and unsigned integers in ARM architecture?

easy

A. Signed integers use more memory than unsigned integers.

B. Signed integers can represent negative and positive numbers, unsigned only non-negative.

C. Unsigned integers can represent negative numbers, signed cannot.

D. Signed integers are faster to process than unsigned integers.

Solution

1. Step 1: Understand signed integers

   Signed integers use two's complement to represent both negative and positive numbers.

2. Step 2: Understand unsigned integers

   Unsigned integers represent only zero and positive numbers, allowing a larger positive range.

3. Final Answer:

   Signed integers can represent negative and positive numbers, unsigned only non-negative. -> Option B

4. Quick Check:

   Signed = negative and positive, Unsigned = only positive [OK]

Hint: Signed = negatives allowed, unsigned = only zero or positive [OK]

Common Mistakes:

• Thinking unsigned can represent negative numbers
• Assuming signed uses more memory
• Believing signed is always faster

2.

Which of the following is the correct way to declare an unsigned 8-bit integer in ARM assembly?

easy

A. mov r0, #255 (assuming r0 is unsigned 8-bit)

B. movs r0, #255

C. mov r0, #-1

D. mov r0, #256

Solution

1. Step 1: Understand unsigned 8-bit range

   Unsigned 8-bit integers range from 0 to 255, so 255 is valid.

2. Step 2: Check instructions

   mov r0, #255 moves the immediate value 255 into register r0 correctly.

3. Final Answer:

   mov r0, #255 (assuming r0 is unsigned 8-bit) -> Option A

4. Quick Check:

   Unsigned 8-bit max = 255, mov loads immediate [OK]

Hint: Unsigned 8-bit max is 255, use mov with that value [OK]

Common Mistakes:

• Using movs which sets flags unnecessarily
• Trying to move negative values to unsigned
• Using values above 255 for 8-bit

3.

Consider a 4-bit signed integer using two's complement. What decimal value does the binary 1101 represent?

medium

A. -3

B. 13

C. -5

D. 5

Solution

1. Step 1: Identify two's complement sign

   In 4-bit two's complement, if the leftmost bit is 1, the number is negative.

2. Step 2: Calculate decimal value

   Binary 1101: invert bits -> 0010, add 1 -> 0011 (3 decimal), so value is -3. But careful: 1101 is -3 or -5? Let's check carefully:
   1101 binary = (1x-8) + (1x4) + (0x2) + (1x1) = -8 + 4 + 0 + 1 = -3

3. Final Answer:

   -3 -> Option A

4. Quick Check:

   Two's complement 1101 = -3 decimal [OK]

Hint: If MSB is 1, subtract 2^bits from value [OK]

Common Mistakes:

• Treating binary as unsigned
• Forgetting two's complement negative calculation
• Mixing bit positions

4.

In ARM assembly, a programmer tries to store the value -1 in an unsigned 8-bit register. What is the likely result?

medium

A. The program crashes at runtime.

B. Syntax error occurs during assembly.

C. The register stores 0.

D. The register stores 255 due to wrap-around.

Solution

1. Step 1: Understand unsigned storage

   Unsigned 8-bit registers store values 0 to 255. Negative values wrap around using modulo 256.

2. Step 2: Calculate wrap-around for -1

   -1 modulo 256 equals 255, so the register stores 255.

3. Final Answer:

   The register stores 255 due to wrap-around. -> Option D

4. Quick Check:

   Unsigned wrap-around: -1 = 255 [OK]

Hint: Negative to unsigned wraps modulo max+1 [OK]

Common Mistakes:

• Expecting syntax error for negative immediate
• Assuming register stores zero
• Thinking program crashes

5.

You have a 16-bit unsigned integer register holding the value 65535. You subtract 1 from it. What is the result stored in the register?

hard

A. 65536

B. -1

C. 65534

D. 0

Solution

1. Step 1: Understand 16-bit unsigned range

   16-bit unsigned integers range from 0 to 65535.

2. Step 2: Perform subtraction

   65535 - 1 = 65534, which fits in 16 bits without wrap-around.

3. Final Answer:

   65534 -> Option C

4. Quick Check:

   65535 - 1 = 65534 within unsigned 16-bit [OK]

Hint: Subtract within range stays positive, no wrap [OK]

Common Mistakes:

• Thinking result becomes negative
• Assuming overflow to zero
• Confusing unsigned with signed behavior