Construct UART Data Frame with Parity Bit

Original Code (with loop for bit counting)

Time Complexity (TC):

• The loop runs 7 times (once for each bit).
• TC: O(1) (constant time, since 7 is fixed, but involves 7 iterations per call).

Space Complexity (SC):

• Uses a few local variables.
• SC: O(1) (constant space).

Optimized Code (with __builtin_popcount)

Time Complexity (TC):

• __builtin_popcount is typically implemented as a single instruction or a few instructions in hardware or compiler intrinsics.
• TC: O(1) (constant time, but faster than the loop).

Space Complexity (SC):

• No additional space used.
• SC: O(1) (constant space).

Key Point:
Both are O(1), but the optimized version is faster in practice due to intrinsic/hardware support for bit counting. Space usage is the same in both.

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

typedef struct {
    uint8_t parity_enable : 1;
    uint8_t parity_type   : 1;
    uint8_t reserved      : 6;
} UART_Control;

uint8_t create_uart_frame(uint8_t data, UART_Control *ctrl) {
      data &= 0x7F; // Ensure 7 bits

    if (!ctrl->parity_enable) {
        return data;
    }

    // Use GCC intrinsic for bit count (efficient on most platforms)
    uint8_t ones = __builtin_popcount(data);

    // Parity bit calculation: even parity = ones%2, odd parity = !(ones%2)
    uint8_t parity_bit = (ctrl->parity_type) ? !(ones % 2) : (ones % 2);

    return (parity_bit << 7) | data;
}

int main() {
    uint8_t data;
    scanf("%hhu", &data);  // 7-bit input

    uint8_t parity_enable, parity_type;
    scanf("%hhu %hhu", &parity_enable, &parity_type);

    UART_Control ctrl;
    ctrl.parity_enable = parity_enable;
    ctrl.parity_type = parity_type;

    uint8_t frame = create_uart_frame(data, &ctrl);
    printf("frame = 0x%02X", frame);

    return 0;
}

Solving Approach