</>EmbeddedInterview

How do you add two binary strings or add one to a number stored as digits?

EasyArrays & Strings (Coding Round)

Short answer: Work from the least significant end (the right) with a carry, exactly like addition on paper: sum the two digits plus the carry, write sum % base, carry sum / base. If a carry is left at the end, the result is one digit longer.

#include <string.h>

/* out must have room for max(len a, len b) + 2 bytes */
void add_binary(const char *a, const char *b, char *out)
{
    size_t i = strlen(a), j = strlen(b);
    size_t k = (i > j ? i : j) + 1;           /* room for a final carry */
    out[k] = '\0';
    int carry = 0;
    while (k > 0) {
        int sum = carry;
        if (i > 0) sum += a[--i] - '0';
        if (j > 0) sum += b[--j] - '0';
        out[--k] = (char)('0' + (sum & 1));
        carry = sum >> 1;
    }
    if (out[0] == '0' && out[1] != '\0')      /* drop the unused leading digit */
        memmove(out, out + 1, strlen(out));
}
/* "1011" + "11" -> "1110" */

/* digits[0] is the most significant decimal digit; returns new length */
size_t plus_one(unsigned char *digits, size_t n)   /* capacity n + 1 */
{
    for (size_t i = n; i-- > 0; ) {
        if (digits[i] < 9) { digits[i]++; return n; }
        digits[i] = 0;                         /* 9 + 1 = 10: write 0, carry on */
    }
    memmove(digits + 1, digits, n);            /* all nines: 999 -> 1000 */
    digits[0] = 1;
    return n + 1;
}

Why this matters in embedded work: arbitrary-precision arithmetic, BCD counters (RTC chips store time in BCD; adding to a BCD value needs a decimal carry at 10, not 16), and multi-word counters (a 64-bit counter built from two 32-bit hardware registers, where the carry must be handled when the low word wraps).

Check your carry logic on: "1" + "1" = "10", "0" + "0" = "0", {9, 9} + 1 = {1, 0, 0}.