Bit manipulation in ARM in ARM Architecture - Time & Space Complexity

Time Complexity: Bit manipulation in ARM

O(1)

Understanding Time Complexity

Bit manipulation in ARM involves changing or checking bits in registers using instructions.

We want to know how the time to do these operations changes as we work with more bits.

Scenario Under Consideration

Analyze the time complexity of the following ARM bit manipulation code.

    MOV R0, #0xFF       ; Load immediate value
    AND R1, R0, #0x0F   ; Mask lower 4 bits
    ORR R2, R1, #0x10   ; Set bit 4
    EOR R3, R2, #0x01   ; Toggle bit 0
    BIC R4, R3, #0x08   ; Clear bit 3
    

This code performs several bit operations on registers: masking, setting, toggling, and clearing bits.

Identify Repeating Operations

Each instruction performs a single bit operation on fixed-size registers.

• Primary operation: Single bitwise instruction per line
• How many times: Each instruction runs once, no loops or recursion

How Execution Grows With Input

Since each instruction works on a fixed 32-bit register, the time does not grow with input size.

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

Pattern observation: The number of instructions stays the same regardless of bit size.

Final Time Complexity

Time Complexity: O(1)

This means the time to perform bit manipulation does not increase as the number of bits grows.

Common Mistake

[X] Wrong: "Bit manipulation takes longer if we have more bits to handle."

[OK] Correct: ARM instructions operate on fixed-size registers in one step, so time stays constant.

Interview Connect

Understanding that bit operations run in constant time helps you reason about low-level code efficiency and system performance.

Self-Check

"What if we had to manipulate bits in a large array of registers instead of one? How would the time complexity change?"

Practice

1. Which ARM instruction is used to set specific bits to 1 without changing other bits?

easy

A. BIC

B. ORR

C. EOR

D. LSR

Solution

1. Step 1: Understand ORR instruction

   ORR performs a bitwise OR, setting bits to 1 where either operand has 1.

2. Step 2: Compare with other instructions

   BIC clears bits, EOR toggles bits, LSR shifts bits right. Only ORR sets bits without clearing others.

3. Final Answer:

   ORR -> Option B

4. Quick Check:

   Set bits = ORR [OK]

Hint: ORR sets bits; BIC clears bits; remember ORR for setting [OK]

Common Mistakes:

• Confusing BIC with ORR
• Thinking EOR sets bits
• Mixing shift instructions with bit setting

2. Which of the following is the correct syntax to clear bits using BIC in ARM assembly?

easy

A. BIC R0, R1, R2

B. BIC R0, R1, #R2

C. BIC R0, #R1, R2

D. BIC R0, R1, LSR #1

Solution

1. Step 1: Review BIC syntax

   BIC syntax is BIC destination, source, operand2 (register or immediate). BIC R0, R1, R2 matches this format.

2. Step 2: Analyze other options

   Options using # before register names are invalid; the option attempting a shift lacks the required register operand, making it invalid syntax.

3. Final Answer:

   BIC R0, R1, R2 -> Option A

4. Quick Check:

   BIC syntax = BIC Rd, Rn, Operand2 [OK]

Hint: BIC clears bits: BIC Rd, Rn, Operand2 [OK]

Common Mistakes:

• Using # before register names
• Confusing immediate and register operands
• Adding unnecessary shifts in basic syntax

3. Given the ARM instruction EOR R0, R1, #0xFF and R1 contains 0x0F0F, what will be the value in R0 after execution?

medium

A. 0xF0F0

B. 0x0F00

C. 0xF0F0FF

D. 0x0FF0

Solution

1. Step 1: Understand EOR operation

   EOR performs bitwise exclusive OR between R1 and immediate 0xFF (which is 255 decimal).

2. Step 2: Calculate bitwise EOR

   R1 = 0x0F0F (binary 0000111100001111), immediate 0xFF affects only lower 8 bits (0000000011111111). XOR lower 8 bits: 00001111 XOR 11111111 = 11110000 (0xF0). Upper bits remain 0x0F. So result is 0x0F (upper) and 0xF0 (lower) combined = 0xF0F0.

3. Final Answer:

   0xF0F0 -> Option A

4. Quick Check:

   EOR 0x0F0F ^ 0x00FF = 0xF0F0 [OK]

Hint: EOR toggles bits; XOR lower byte 0x0F with 0xFF = 0xF0 [OK]

Common Mistakes:

• Applying immediate to full 16 bits
• Confusing OR with XOR
• Ignoring bitwise operation effects

4. Identify the error in this ARM assembly snippet intended to clear bit 3 of R2:
BIC R2, R2, #3

medium

A. BIC cannot use immediate values

B. Syntax error: missing comma after R2

C. Immediate value #3 clears bits 0 and 1, not bit 3

D. Should use ORR instead of BIC

Solution

1. Step 1: Understand BIC with immediate

   BIC clears bits set in the immediate value. #3 in binary is 00000011, which clears bits 0 and 1.

2. Step 2: Check which bit to clear

   Bit 3 corresponds to binary 00001000 (decimal 8). Using #3 clears wrong bits.

3. Final Answer:

   Immediate value #3 clears bits 0 and 1, not bit 3 -> Option C

4. Quick Check:

   Clear bit 3 needs #8, not #3 [OK]

Hint: Immediate #3 clears bits 0 and 1, use #8 for bit 3 [OK]

Common Mistakes:

• Using wrong immediate value for bit position
• Thinking BIC can't use immediate
• Confusing ORR and BIC roles

5. You want to toggle bits 0 and 2 of register R3 without affecting other bits. Which ARM instruction and operand should you use?

hard

A. AND R3, R3, #0x05

B. ORR R3, R3, #0x05

C. BIC R3, R3, #0x05

D. EOR R3, R3, #0x05

Solution

1. Step 1: Identify bits to toggle

   Bits 0 and 2 correspond to binary 00000101 (hex 0x05).

2. Step 2: Choose instruction for toggling bits

   EOR toggles bits where mask bits are 1. ORR sets bits, BIC clears bits, AND masks bits.

3. Step 3: Apply EOR with mask 0x05

   EOR R3, R3, #0x05 flips bits 0 and 2, leaving others unchanged.

4. Final Answer:

   EOR R3, R3, #0x05 -> Option D

5. Quick Check:

   Toggle bits = EOR with mask [OK]

Hint: Toggle bits with EOR and mask of bits to flip [OK]

Common Mistakes:

• Using ORR or AND instead of EOR for toggling
• Wrong mask value for bits 0 and 2
• Confusing clearing with toggling