Mockup in C of hardware implementation for multiplication of signed integers I challenged myself to implement multiplication of signed integers using only +, -, &gt;&gt;, &lt;&lt;, &amp;, |, ^, and conditionals, though I would like to improve my method to not use conditionals if possible in the future. Any input would be very helpful.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;stdbool.h&gt;
#include &lt;limits.h&gt;
#include &lt;time.h&gt;

int multiply(int, int);

int main() {
    int a, b, c, i;
    bool equal;

    srand(time(NULL));

    for (i = 0; i &lt; 100; i++) {
        // 0x8000 to ensure no integer overflow is possible
        a = (rand() % 0x8000) * (rand() % 2 ? -1 : 1);
        b = (rand() % 0x8000) * (rand() % 2 ? -1 : 1);
        c = multiply(a, b);
        equal = (c == a * b);

        printf("%-11d * %-11d = %-11d (%s)\n", a, b, c, (equal ? "Success" : "Failure"));

        if (!equal) {
            return EXIT_FAILURE;
        }
    }

    return EXIT_SUCCESS;
}

int multiply(int a, int b) {
    struct {
        unsigned char index : 5;
    } bit;

    int c = INT_MAX &amp; a, // remove sign bit
        d = INT_MAX &amp; b,
        sign = (INT_MIN &amp; a) ^ (INT_MIN &amp; b), // sign of product
        mask = 0x40000000,
        prod = 0;

    bit.index = 30; // keeping track of mask bit index

    do {
        prod += (mask &amp; c ? d &lt;&lt; bit.index : 0);
    } while ((bit.index--) &amp;&amp; (mask &gt;&gt;= 1));

    return sign | (prod &amp; INT_MAX);
}
Sign bit manipulation unnecessary

I looked at your code and was puzzled by all the sign bit manipulation.  As far as I can tell, it's not necessary.  I rewrote your function to be like the following and it still passed all your tests:

int multiply(int a, int b)
{
    // Bit keeps track of mask bit index.
    struct {
        unsigned int index: 5;
    } bit = {31};
    int prod = 0;

    do {
        prod += ((a &amp; (1 &lt;&lt; bit.index)) ? b &lt;&lt; bit.index : 0);
    } while (bit.index--);

    return prod;
}


Bonus answer: no conditionals inside loop

int multiply(int a, int b)
{
    // Bit keeps track of mask bit index.
    struct {
        unsigned int index: 5;
    } bit = {31};
    int prod = 0;

    do {
        prod += (-((a &gt;&gt; bit.index) &amp; 1)) &amp; (b &lt;&lt; bit.index);
    } while (bit.index--);

    return prod;
}


Explanation:


((a &gt;&gt; bit.index) &amp; 1) is 1 or 0 depending on the masked bit.  Call this B.
-B is -1 or 0.  This sets up a mask to use for the next step (-1 is a mask of all one bits).
-B &amp; (b &lt;&lt; bit.index) is either (b &lt;&lt; bit.index) or 0.