Factorial in C without conditionals, loops and arithmetic operators

Question

How can I find the factorial of a number (from 1 to 10) in C, without using:

• loop statements like for, while, and do while;
• conditional operators like if and case; and
• arithmetic operators like + , − , * , % , /, ++, −−?

FYI: I found this question in C aptitude.

Answer 1

Since it is only 1 to 10, simply precompute it and store it in a simple int array of size 11. For the first element in the array put 1. It is not a valid input range for your problem but might as well be correct.

We need to store 11 elements instead of the 10 we need because otherwise we'd need to use operation "-" to get the right index. Subtraction is not allowed in your problem though.

int factorial(int x)
{
  return precomputedArray[x];
}

Answer 2

Here is a solution without loops, arithmetics, or conditionals and which does not resort to precomputation. It also does not use short-circuiting conditionals like && or || which are in practice equivalent to if. So this seems to be the first proper solution without any conditionals at all. Now in proper C without C++ features :)

#include <stdio.h>
#define uint unsigned int

void A(uint *a, uint *b)
{
    uint tmp = *a & *b;
    *a = (*a | *b) & ~tmp;
    *b = tmp << 1;
}

#define REPEAT32(s) \
s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s

uint add(uint a, uint b)
{
    REPEAT32(A(&a, &b);) return a;
}

uint bitexpand(uint b)
{
    b = (b << 1)  | b; b = (b << 2)  | b; b = (b << 4)  | b;
    b = (b << 8)  | b; b = (b << 16) | b;
    return b;
}

void M(uint *acc, uint *a, uint *b)
{
    *acc = add(*acc, *a & bitexpand(*b & 1));
    *a <<= 1;
    *b >>= 1;
}

uint mult(uint a, uint b)
{
    uint acc = 0;
    REPEAT32(M(&acc, &a, &b);) return acc;
}

uint factorial(int n)
{
    uint k = 1;
    uint result = 0;
    result |= (bitexpand(n == 1) & k);
    k = mult(k, 2); result |= (bitexpand(n == 2) & k);
    k = mult(k, 3); result |= (bitexpand(n == 3) & k);
    k = mult(k, 4); result |= (bitexpand(n == 4) & k);
    k = mult(k, 5); result |= (bitexpand(n == 5) & k);
    k = mult(k, 6); result |= (bitexpand(n == 6) & k);
    k = mult(k, 7); result |= (bitexpand(n == 7) & k);
    k = mult(k, 8); result |= (bitexpand(n == 8) & k);
    k = mult(k, 9); result |= (bitexpand(n == 9) & k);
    k = mult(k, 10); result |= (bitexpand(n == 10) & k);
    return result;
}

int main(int argc, char **argv)
{
    uint i;
    /* Demonstration loop, not part of solution */
    for (i = 1; i <= 10; i++)
    {
        printf("%d %d\n", i, factorial(i));
    }
}

Updated: the discussion contained the claim that short-circuiting conditional like && would be acceptable in a solution that does not use if. Here is a simple macro that mimics two-way 'if' using && and obviously makes the whole problem much less interesting:

#define IF(i, t, e) \
(void)((i) && (goto then##__LINE__, 1)); goto else##__LINE__;
then##__LINE__: t; goto cont##__LINE__; \
else##__LINE__: e; cont##__LINE__: ((void)0);

You can then define

#define WHILE(c, s) \
loop##__LINE__: IF(c, s; goto loop##__LINE__, ((void)0)))

and then the rest of the problem becomes trivial.