Detect Circular Pattern Match

Code

#include <stdio.h>
#include <stdint.h>

uint8_t is_circular_match(uint16_t reg, uint16_t target) {
    for (int i = 0; i < 16; i++) {
        uint16_t rotated = (reg << i) | (reg >> (16 - i));
        if (rotated == target)
            return 1;
    }
    return 0;
}

int main() {
    uint16_t reg, target;
    scanf("%hu %hu", &reg, &target);
    printf("%hhu", is_circular_match(reg, target));
    return 0;
}

Solving Approach

Great — let’s break down the solving approach for detecting a circular pattern match between two 16-bit values: reg and target.

🧠 Problem Understanding

You’re given:

• A 16-bit register value (reg)
• A 16-bit target value (target)

You need to check whether any circular left rotation of reg results in a value equal to target.

🔁 What Is Circular Rotation?

A circular left rotation by i bits means:

• Bits shifted out from the left end are wrapped around to the right end.
• For example, rotating 0b1011000000000000 left by 13 bits gives 0b0000000000001011.

✅ Step-by-Step Approach

1. Loop through all 16 possible rotations:
   • Since it's a 16-bit value, rotating by 0 to 15 bits covers all unique circular shifts.
2. Perform circular left rotation:

   • Use bitwise operations:

     rotated = (reg << i) | (reg >> (16 - i));
     

   • This wraps the bits around correctly.
3. Mask to 16 bits:

   • Ensure the result stays within 16 bits:

     rotated &= 0xFFFF;
     

4. Compare with target:
   • If rotated == target, return 1 (match found).
5. After loop ends:
   • If no match is found, return 0.

🧪 Time Complexity

• O(1): Only 16 iterations, constant time.
• Efficient even for embedded systems or microcontroller firmware.