Binary multiplication without arithmetic operators and loops

Question

I have to do the following task:

Implement written multiplication of two two-digit binary numbers without using the +, -, *, / and bit operations. The logical operators &&, || and ! may only be applied to logical expressions and not to the numbers themselves. The use of arrays and loops is not permitted here. Likewise, the solution by distinguishing between all 16 cases is not permitted here.

The code should be structured in such a way that an extension to numbers with a larger number of digits is easily possible.

The two numbers are entered digit by digit from the console or via redirection from a file (exactly four digits). For single-digit numbers, the leading zero must also be entered.

To do this, use two functions add(), which adds two binary digits without carry (i.e. returns 0 or 1) and carry(), which determines the carry when adding two binary digits. Additional functions may be used.

The output should be such that the two factors are next to each other without leading zeros, then an equal sign follows and the product without leading zeros.

My approach is Booth's algorithm for multiplication with binary numbers. However, I don't know how to implement this without loops.

Do I have the right algorithm?

Code example of the mentioned algorithm:

#include <stdio.h>

// Function to display a binary number
void displayBinary(int n) {
    if (n == 0) {
        printf("0");
        return;
    }

    int binary[32];
    int i = 0;

    while (n > 0) {
        binary[i] = n % 2;
        n /= 2;
        i++;
    }

    for (i--; i >= 0; i--) {
        printf("%d", binary[i]);
    }
}

// Function to perform Booth multiplication
int boothMultiplication(int multiplicand, int multiplier) {
    int m = multiplicand;
    int q = multiplier;
    int ac = 0; // Accumulator
    int q0 = 0; // Least significant bit of q
    int q1 = 0; // Next least significant bit of q

    int n = sizeof(int) * 8; // Number of bits in an integer 

    printf("Step\t\tA\t\tQ\t\tQ(-1)\tQ(0)\tOperation\n");

    for (int step = 1; step <= n; step++) {
        int q0_q1 = (q0 << 1) | q1;
        int operation = 0;

        if ((q0_q1 & 0b11) == 0b01) {
            ac += m;
            operation = 1;
        } else if ((q0_q1 & 0b11) == 0b10) {
            ac -= m;
            operation = -1;
        }

        if (q & 1) {
            q1 = q0;
        }
        q0 = q & 1;
        q >>= 1;

        printf("%d\t\t\t", step);
        displayBinary(ac);
        printf("\t");
        displayBinary(q);
        printf("\t");
        displayBinary(q1);
        printf("\t");
        displayBinary(q0);
        printf("\t");

        if (operation == 1) {
            printf("Addition (+%d)\n", m);
        } else if (operation == -1) {
            printf("Subtraction (-%d)\n", m);
        } else {
            printf("No Operation\n");
        }
    }

    return ac;
}

int main() {
    int multiplicand, multiplier;
    
    printf("Enter the multiplicand: ");
    scanf("%d", &multiplicand);
    
    printf("Enter the multiplier: ");
    scanf("%d", &multiplier);

    int product = boothMultiplication(multiplicand, multiplier);

    printf("\nResult: %d * %d = %d\n", multiplicand, multiplier, product);

    return 0;
}

The original task in German

Answer 1

This should satisfy the requirements.

#include <stdio.h>

int add(int b1, int b0) { return b1 != b0; }

int carry(int b1, int b0) { return b1==1 && b0==1; }

void print(int b3, int b2, int b1, int b0, char *s)
{
    int c = 0;
    if (b3==1 || c) printf("%i", b3), c = 1;
    if (b2==1 || c) printf("%i", b2), c = 1;
    if (b1==1 || c) printf("%i", b1), c = 1;
    printf("%i%s", b0, s), c = 1;
}

int main()
{
    int x1, x0, y1, y0, z3, z2, z1, z0, a1, a0;
    scanf("%i", &x1),   scanf("%i", &x0); 
    scanf("%i", &y1),   scanf("%i", &y0); 
    z1 = y0 ? x1 : 0,   z0 = y0 ? x0 : 0;
    a1 = y1 ? x1 : 0,   a0 = y1 ? x0 : 0;
    z2 = carry(z1, a0), z1 = add(z1, a0);
    z3 = carry(z2, a1), z2 = add(z2, a1);
    print( 0,  0, x1, x0, " * "),
    print( 0,  0, y1, y0, " = "),
    print(z3, z2, z1, z0, "\n");
}