Hexadecimal for register and memory values in ARM Architecture - Time & Space Complexity

Time Complexity: Hexadecimal for register and memory values

O(n)

Understanding Time Complexity

We want to understand how the time to read or write hexadecimal values in registers or memory changes as the amount of data grows.

How does the number of operations grow when handling more hexadecimal values?

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly snippet that loads multiple hexadecimal values into registers.

    LDR R0, =0x1000      ; Load base address
    MOV R1, #0           ; Initialize counter
    LOOP:
      LDR R2, [R0, R1, LSL #2]  ; Load word from memory
      ADD R1, R1, #1             ; Increment counter
      CMP R1, #N                 ; Compare with N
      BLT LOOP                   ; Repeat if less
    

This code loads N hexadecimal 32-bit values from memory into a register one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loading a 32-bit hexadecimal value from memory into a register.
• How many times: This load operation repeats N times, once for each value.

How Execution Grows With Input

Each additional hexadecimal value requires one more load operation, so the total work grows directly with N.

Input Size (n)	Approx. Operations
10	10 loads
100	100 loads
1000	1000 loads

Pattern observation: The number of operations increases steadily and proportionally as the input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to load hexadecimal values grows linearly with the number of values.

Common Mistake

[X] Wrong: "Loading multiple hexadecimal values happens instantly or in constant time regardless of how many values there are."

[OK] Correct: Each value requires a separate load operation, so more values mean more work and more time.

Interview Connect

Understanding how loading data scales helps you reason about program speed and efficiency, a useful skill in many programming and hardware-related roles.

Self-Check

What if we changed the code to load two hexadecimal values at once using a wider register or vector instruction? How would the time complexity change?

Practice

1. What does the prefix 0x in a value like 0x1A3F indicate in ARM architecture?

easy

A. The value is a binary number

B. The value is in decimal format

C. The value is a memory address

D. The value is in hexadecimal format

Solution

1. Step 1: Understand the prefix meaning

   The prefix 0x is a standard notation used in computing to indicate that the following number is in hexadecimal (base 16) format.

2. Step 2: Differentiate from other formats

   Decimal numbers do not have this prefix, binary numbers use 0b, and memory addresses may or may not use this prefix but the prefix itself means hexadecimal.

3. Final Answer:

   The value is in hexadecimal format -> Option D

4. Quick Check:

   Prefix 0x means hexadecimal [OK]

Hint: Remember 0x means hex, not decimal or binary [OK]

Common Mistakes:

• Confusing 0x with decimal numbers
• Thinking 0x means binary
• Assuming 0x always means memory address

2. Which of the following is the correct way to write the hexadecimal value for decimal 255 in ARM assembly?

easy

A. 0xFF

B. FFx0

C. 255x0

D. 0b11111111

Solution

1. Step 1: Convert decimal 255 to hexadecimal

   Decimal 255 equals hexadecimal FF because 15*16 + 15 = 255.

2. Step 2: Write the correct hexadecimal notation

   Hexadecimal values start with 0x followed by digits and letters A-F, so 0xFF is correct.

3. Final Answer:

   0xFF -> Option A

4. Quick Check:

   Decimal 255 = 0xFF [OK]

Hint: Hex starts with 0x, then hex digits (0-9, A-F) [OK]

Common Mistakes:

• Writing the prefix after the digits
• Using decimal digits without 0x
• Confusing binary prefix 0b with hex

3. Given the ARM register value R0 = 0x1C, what is the decimal equivalent of this value?

medium

A. 12

B. 28

C. 44

D. 31

Solution

1. Step 1: Understand hexadecimal digits

   The value 0x1C has two hex digits: 1 and C. Hex digit C equals decimal 12.

2. Step 2: Calculate decimal value

   Calculate as (1 * 16) + 12 = 16 + 12 = 28.

3. Final Answer:

   28 -> Option B

4. Quick Check:

   0x1C = 28 decimal [OK]

Hint: Multiply first digit by 16, add second digit decimal [OK]

Common Mistakes:

• Treating hex digits as decimal directly
• Ignoring that C = 12 in decimal
• Adding digits without multiplying first by 16

4. An ARM instruction tries to load the value 0xG5 into a register. What is the problem with this hexadecimal value?

medium

A. The value is too large for a register

B. The prefix 0x is missing

C. Hexadecimal digits must be 0-9 or A-F; 'G' is invalid

D. Hexadecimal values cannot be loaded into registers

Solution

1. Step 1: Check valid hexadecimal digits

   Hexadecimal digits include 0-9 and letters A-F only. The letter 'G' is not a valid hex digit.

2. Step 2: Identify the error in the value

   Since 'G' is invalid, the value 0xG5 is not a valid hexadecimal number and will cause an error.

3. Final Answer:

   Hexadecimal digits must be 0-9 or A-F; 'G' is invalid -> Option C

4. Quick Check:

   Hex digits only 0-9, A-F [OK]

Hint: Hex digits only 0-9 and A-F, no other letters [OK]

Common Mistakes:

• Assuming any letter can be hex
• Thinking 0x prefix is missing
• Believing hex values can't be loaded into registers

5. You have a memory address 0x100 storing the value 0x2A. You want to add decimal 10 to this value and store it back. What is the new hexadecimal value stored at 0x100?

hard

A. 0x34

B. 0x3A

C. 0x20

D. 0x2F

Solution

1. Step 1: Convert the original hex value to decimal

   Value at 0x100 is 0x2A. Hex 2A = (2 * 16) + 10 = 32 + 10 = 42 decimal.

2. Step 2: Add decimal 10 to the value

   42 + 10 = 52 decimal.

3. Step 3: Convert the result back to hexadecimal

   52 decimal = 3 * 16 + 4 = 0x34 in hexadecimal.

4. Final Answer:

   0x34 -> Option A

5. Quick Check:

   42 + 10 = 52 decimal = 0x34 hex [OK]

Hint: Convert hex to decimal, add, then convert back to hex [OK]

Common Mistakes:

• Adding hex digits directly without conversion
• Confusing decimal and hex values
• Forgetting to convert result back to hex