Two's complement representation in ARM Architecture - Time & Space Complexity

Time Complexity: Two's complement representation

O(1)

Understanding Time Complexity

We want to understand how the time to process two's complement numbers changes as the number size grows.

Specifically, how does the cost of converting or interpreting these numbers scale with their bit length?

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly code snippet that converts a two's complement number to its positive magnitude.

    CMP R0, #0          ; Compare input number with zero
    BGE positive        ; If number >= 0, branch to positive
    MVN R1, R0          ; Otherwise, invert bits
    ADD R1, R1, #1      ; Add 1 to complete two's complement negation
    B done
  positive:
    MOV R1, R0          ; Number is positive, move as is
  done:
    ; R1 now holds the positive magnitude
    

This code checks if a number is negative and if so, converts it to positive by two's complement negation.

Identify Repeating Operations

Look for loops or repeated steps that depend on input size.

• Primary operation: Simple conditional check and bitwise operations.
• How many times: Each instruction runs once per input number, no loops.

How Execution Grows With Input

The number of instructions executed stays the same regardless of the number's bit length.

Input Size (bits)	Approx. Operations
8	5 instructions
16	5 instructions
32	5 instructions

Pattern observation: The execution steps do not increase with input size; they remain constant.

Final Time Complexity

Time Complexity: O(1)

This means the time to convert or interpret a two's complement number does not grow with the number's size.

Common Mistake

[X] Wrong: "Converting a two's complement number takes longer for bigger numbers because you have to process each bit."

[OK] Correct: The processor uses fixed-size registers and instructions that handle all bits at once, so the time stays the same no matter the number size.

Interview Connect

Understanding that two's complement operations are constant time helps you reason about low-level data handling efficiently, a useful skill in many programming and hardware contexts.

Self-Check

"What if the number was stored in memory as a variable-length bit string instead of a fixed register size? How would the time complexity change?"

Practice

1. What is the main purpose of using two's complement in ARM architecture?

easy

A. To represent both positive and negative integers in binary

B. To store only positive numbers efficiently

C. To convert decimal numbers to hexadecimal

D. To encrypt data for security

Solution

1. Step 1: Understand number representation in computers

   Computers use binary to represent numbers, but need a way to show both positive and negative values.

2. Step 2: Role of two's complement

   Two's complement allows representing negative numbers by inverting bits and adding one, enabling simple arithmetic.

3. Final Answer:

   To represent both positive and negative integers in binary -> Option A

4. Quick Check:

   Two's complement = Signed integer representation [OK]

Hint: Two's complement = signed numbers in binary [OK]

Common Mistakes:

• Thinking it only stores positive numbers
• Confusing with encryption or encoding
• Assuming it converts decimal to hex

2. Which of the following is the correct 4-bit two's complement representation of -3?

easy

A. 1101

B. 0011

C. 1011

D. 1110

Solution

1. Step 1: Find binary of positive 3 in 4 bits

   3 in binary is 0011.

2. Step 2: Calculate two's complement for -3

   Invert bits: 1100, then add 1: 1101.

3. Final Answer:

   1101 -> Option A

4. Quick Check:

   -3 in 4-bit two's complement = 1101 [OK]

Hint: Invert bits and add 1 for negative numbers [OK]

Common Mistakes:

• Using positive binary without complement
• Adding instead of inverting bits first
• Confusing bit length or dropping bits

3. Given an 8-bit two's complement number 11111010, what decimal value does it represent?

medium

A. 22

B. -22

C. 250

D. -6

Solution

1. Step 1: Identify if number is negative

   Most significant bit is 1, so number is negative.

2. Step 2: Find magnitude by two's complement

   Invert bits: 00000101, add 1: 00000110 (6 decimal).

3. Final Answer:

   -22 -> Option B

4. Quick Check:

   11111010 two's complement = -22 [OK]

Hint: If MSB=1, invert bits +1 to find negative value [OK]

Common Mistakes:

• Reading as unsigned binary (250)
• Ignoring two's complement rules
• Mistaking bit inversion step

4. A programmer wrote this 4-bit two's complement number: 1001. They claim it equals +9. What is the error?

medium

A. 1001 equals +9 correctly

B. 1001 is invalid in two's complement

C. 1001 represents -7, not +9

D. Two's complement cannot represent 4-bit numbers

Solution

1. Step 1: Check sign from MSB

   MSB is 1, so number is negative in two's complement.

2. Step 2: Calculate decimal value

   Invert bits: 0110, add 1: 0111 (7 decimal), so value is -7.

3. Final Answer:

   1001 represents -7, not +9 -> Option C

4. Quick Check:

   1001 two's complement = -7, not +9 [OK]

Hint: MSB 1 means negative, check two's complement value [OK]

Common Mistakes:

• Assuming binary is always positive
• Ignoring sign bit meaning
• Confusing two's complement with unsigned

5. In ARM 8-bit two's complement, what is the result of adding 00010110 (+22) and 11101010 (-22)?

hard

A. 00011100 (28)

B. 11111111 (-1)

C. Overflow error

D. 00000000 (0)

Solution

1. Step 1: Understand the numbers

   00010110 is +22, 11101010 is -22 in two's complement.

2. Step 2: Add the binary numbers

   00010110 + 11101010 = 00000000 (ignoring carry out), which is 0.

3. Final Answer:

   00000000 (0) -> Option D

4. Quick Check:

   +22 + (-22) = 0 [OK]

Hint: Adding number and its negative gives zero [OK]

Common Mistakes:

• Expecting overflow when adding opposites
• Misreading negative number value
• Ignoring carry out in two's complement addition