# How to write a C program for multiplication without using the * and + operators?

Is it possible to write a C program that multiplies two numbers without using the multiplication and addition operators?

I found this on Stack Overflow. Please help this poor programmer with his problem. And please don't give answers like c = a/(1/((float)b)), which is exactly the same as c = a*b. (And is already given as an answer.)

• @PaulR use your fantasy – John Dvorak Jan 11 '14 at 17:03
• Code-golf.SE should not be a place for you to mock questions you've seen on StackOverflow. – Gareth Jan 11 '14 at 19:40
• @Gareth, are you sure? The first line of this suggests this may be quite appropriate. – Darren Stone Jan 11 '14 at 20:27
• I´m waiting for someone write an algorithm based on sleep – kb_sou Jan 12 '14 at 2:11
• This question isn't as ridiculous as it sounds. Actual computer hardware (transistors) don't have multiply and add operations -- they have basic logic operations like NOT, AND, OR, XOR. Figuring out how to answer this question can give you excellent insight into how a computer really works at the level of logic gates. – Gabe Jan 12 '14 at 6:12

## Always use recursion

Recusion is the right way!

int inc(int x) {
return x&1?inc(x>>1)<<1:x|1;
}

int dec(int x) {
return x&1?x^1:dec(x>>1)<<1|1;
}

int add(int x, int y) {
}

int mul(int x, int y) {
}

int main() {
int a, b;
scanf("%i\n%i", &a, &b);
printf("%i", mul(a,b));
}

• I would give +3 if I could: one for the ultimate recursion, one for ??:: without parentheses, one for solving the problem without trying to tweak the rules ;) – yo' Jan 11 '14 at 22:52
• If Picasso was a programmer... – R Hughes Jan 12 '14 at 6:29
• @SargeBorsch But where'd the fun be in that? – Oberon Jan 12 '14 at 16:06
• @HC_ The inc function tests its argument to see if the lowest bit is 1; if so, it calls itself on the remaining upper bits of the argument and returns the result with the same low bit that was checked being set to 0, while if not (i.e. the lowest bit is 0), it replaces that 0 with a 1 and returns the result. The process is very similar to what you'd do if you were adding the values by hand, binary digit by binary digit. – JAB Jan 13 '14 at 18:28
• Doesn't the increment function go into an infinite loop for -1? (0xFFFF) ideone shows (-1 >> 1) == -1. – Destrictor Jan 15 '14 at 9:33

You'll have to compile the program each time, but it does do multiplication of any positive integers exactly in any version of C or C++.

 #define A 45  // first number
#define B 315 // second number

typedef char buffer[A][B];

main() {
printf("%d\n",sizeof(buffer));
}

• Put it inside a structure and you don't need memory. – Ben Jackson Jan 12 '14 at 0:54
• Hahahah great!! – Almo Jan 12 '14 at 8:26
• use "%zu" format string. – Grijesh Chauhan Jan 13 '14 at 7:30
• just sizeof(char[A][B]) will work (unless A<=0 or B <=0 or A*B overflows, in which case you should get a 'bad type' sort of error) – greggo Jan 13 '14 at 14:59
• @DavidRicherby - I could simplify the code to main(){return sizeof(char[A][B]);} and you compile using cc -DA=6 -DB=7 a.c; ./a.out; echo $? – Mark Lakata Jan 13 '14 at 22:48 If you are OK with a little imprecision, you can use the Monte Carlo method: #include <stdlib.h> #include <stdio.h> unsigned int mul(unsigned short a, unsigned short b) { const int totalBits = 24; const int total = (1 << totalBits); const int maxNumBits = 10; const int mask = (1 << maxNumBits) - 1; int count = 0, i; unsigned short x, y; for(i = 0; i < total; i++) { x = random() & mask; y = random() & mask; if ((x < a) && (y < b)) count++; } return ((long)count) >> (totalBits - (maxNumBits << 1)); } void main(int argc, char *argv[]) { unsigned short a = atoi(argv[1]); unsigned short b = atoi(argv[2]); printf("%hd * %hd = %d\n", a, b, mul(a, b)); }  Example: $ ./mul 300 250
300 * 250 = 74954


I guess this could be good enough ;)

• You have my up vote. I heard Monte Carlo is what NASA uses for its arithmetic. But I'd like to see this without the two instances of the ++ operator. – Darren Stone Jan 11 '14 at 18:28
• @DarrenStone -= -1 – Timtech Jan 11 '14 at 20:06
• @Timtech |= 1 (will work on 50% of numbers, 100% of the time) – Darren Stone Jan 11 '14 at 20:20
• +1, but noting that it could be too slow, and you could add multi-thread support, carefully locking the 'count++' :-) – greggo Jan 13 '14 at 15:01
• There's always printf increment : printf("%*cc%n\n", count, &count, 'c'); (Prints 'c' count times, then another 'c', and stores the number of characters written back in count. – MSalters Jan 15 '14 at 12:44

Since you didn't specify what size of number, I assume that you mean two one-bit numbers.

#include <stdbool.h>
bool mul(bool a, bool b) {
if (a && b) {
return true;
} else {
return false;
}
}


If you want a maximally-efficient implementation, use the following tiny implementation:

m(a,b){return a&b;}


Note that it still only accepts bits even though the types are implicit ints - it takes less code, and is therefore more efficient. (And yes, it does compile.)

• Nice. A deliberate misinterpretation of the question :-) – John Dvorak Jan 12 '14 at 5:59
• You can optimize this to return a && b;. It’s shorter, so it’s faster. – Ry- Jan 12 '14 at 18:10
• @minitech: I decided against that in order to make the code slightly worse. If I wanted to go further with that, I'd make it return a&b;. – Cel Skeggs Jan 12 '14 at 20:11
• C has #include<stdbool.h> to define true and false. – leewz Jan 15 '14 at 2:10
• Yeah, #include<stdbool.h> seems to just be three #defines that you can do yourself (true, false, bool, and a flag to mark that it's been activated). You can also take a trick from one of the other answers and use implicit int for the "short" version. – leewz Jan 15 '14 at 15:19

Here's a simple shell script to do it:

curl "http://www.bing.com/search?q=$1%2A$2&go=&qs=n&form=QBLH&pq=$1%2A$2" -s \
| sed -e "s/[<>]/\n/g" \
| grep "^[0-9 *]*=[0-9 ]*"  UPDATE: Of course, to do it in C, just wrap it in exec("bash", "-c", ...). (Thanks, AmeliaBR) • I can't decide which is more awful. That you're outsourcing your calculation to a search engine, or that your chosen search engine is Bing. Unfortunately, I don't think this will work for our happless OP, who needed something in C. – AmeliaBR Jan 12 '14 at 1:40 • Thanks for catching that oversight. FYI, I'm using Bing because Google makes it more complicated to issue requests like this -- you have to add headers to convince Google your request is really coming from a browser. – Vroo Jan 12 '14 at 5:34 • @abarnert hmm... does Bing understand "times"? Wolfram Alpha might, though. – John Dvorak Jan 13 '14 at 10:57 • @JanDvorak: Yeah, Wolfram works. (Note the %20 to avoid using any + signs.) But you still need to parse the output (in C) to get the value out of it. Which will be especially tricky, since the output appears to be an image, not text. HTML parsing plus OCR might make that the best possible answer to this problem. – abarnert Jan 13 '14 at 12:48 • @JanDvorak: That's no fun. I was looking forward to someone writing a simple OCR library with no addition or multiplication… – abarnert Jan 13 '14 at 12:54 Why, let's do a recursive halving search between INT64_MIN and INT64_MAX! #include <stdio.h> #include <stdint.h> int64_t mul_finder(int32_t a, int32_t b, int64_t low, int64_t high) { int64_t result = (low - (0 - high)) / 2; if (result / a == b && result % a == 0) return result; else return result / a < b ? mul_finder(a, b, result, high) : mul_finder(a, b, low, result); } int64_t mul(int32_t a, int32_t b) { return a == 0 ? 0 : mul_finder(a, b, INT64_MIN, INT64_MAX); } void main(int argc, char* argv[]) { int32_t a, b; sscanf(argv[1], "%d", &a); sscanf(argv[2], "%d", &b); printf("%d * %d = %ld\n", a, b, mul(a, b)); }  P.S. It will happily sigsegv with some values. ;) Unfortunately, this only works for integers. Since addition is disallowed, let's build an increment operator first: int plusOne(int arg){ int onMask = 1; int offMask = -1; while (arg & onMask){ onMask <<= 1; offMask <<= 1; } return(arg & offMask | onMask); }  Next, we have to handle the sign. First, find the sign bit: int signBit = -1; while(signBit << 1) signBit <<=1;  Then take the sign and magnitude of each argument. To negate a number in a two's complement, invert all bits, and add one. int signA = a & signBit; if(signA) a = plusOne(-1 ^ a); int signB = b & signBit; if(signB) b = plusOne(-1 ^ b); int signRes = signA ^ signB;  To multiply two positive integers, we can use the geometrical meaning of multiplication: // 3x4 // // ooo // ooo // ooo // ooo int res = 0; for(int i = 0; i < a; i = plusOne(i)) for(int j = 1; j < b; j = plusOne(j)) res = plusOne(res); if(signRes) res = plusOne(-1 ^ res);  trolls: • Addition is disallowed, but does a++ really count as addition? I bet the teacher intended to allow it. • Relies on two's complement, but that's an implementation-defined behavior and the target platform wasn't specified. • Similarly, assumes subtraction and division are disallowed just as well. • << is actually multiplication by a power of two, so it should technically be disallowed. • unneccesary diagram is unneccesary. Also, it could have been transposed to save one line. • repeated shifting of -1 is not the nicest way of finding the sign bit. Even if there was no built-in constant, you could do a logical shift right of -1, then invert all bits. • XOR -1 is a not the best way to invert all bits. • The whole charade with sign-magnitude representation is unneccesary. Just cast to unsigned and modular arithmetic will do the rest. • since the absolute value of MIN_INT (AKA signBit) is negative, this breaks for that value. Luckily, it still works in half the cases, because MIN_INT * [even number] should be zero. Also, plusOne breaks for -1, causing infinite loops anytime the result overflows. plusOne works just fine for any value. Sorry for the confusion. • +1 for an actual code troll: It looks like it should work, but it very likely will blow up on the OP and s/he'll have no idea why. – Kevin Jan 11 '14 at 22:26 • It's possible to do addition without ANY addition operators by just using shift, XOR and AND. All these ++'s are making my head hurt -- single bit ADD with carry is (x ^ y) | ((x & y) << 1) (modulo any errors caused by typing in this crappy little text box.) – Julie in Austin Jan 12 '14 at 1:25 • @JulieinAustin yep. The algorithm is even more inefficient than it needs to be. Should I amend the troll list? :-) – John Dvorak Jan 12 '14 at 5:31 • @JulieinAustin (x ^ y) | ((x & y) << 1) doesn't quite work, it won't propagate carry when x or y and carry are both true in the same position :) – hobbs Jan 12 '14 at 6:10 • @hobbs solution: instead of ORing, add them recursively if carry is non-zero. – John Dvorak Jan 12 '14 at 7:29 Works for floating point numbers as well: float mul(float a, float b){ return std::exp(std::log(a) - std::log(1.0 / b)); }  Everyone knows that Python is easier to use than C. And Python has functions corresponding to every operator, for cases where you can't use the operator. Which is exactly our problem definition, right? So: #include <Python.h> void multiply(int a, int b) { PyObject *operator_name, *operator, *mul, *pa, *pb, *args, *result; int result; operator_name = PyString_FromString("operator"); operator = PyImport_Import(operator_name); Py_DECREF(operator_name); mul = PyObject_GetAttrString(operator, "__mul__"); pa = PyLong_FromLong((long)a); pb = PyLong_FromLong((long)b); args = PyTuple_New(2); PyTuple_SetItem(args, 0, pa); PyTuple_SetItem(args, 1, pb); presult = PyObject_CallObject(mul, args); Py_DECREF(args); Py_DECREF(mul); Py_DECREF(operator); result = (int)PyLong_AsLong(presult); Py_DECREF(presult); return result; } int main(int argc, char *argv[]) { int c; Py_Initialize(); c = multiply(2, 3); printf("2 * 3 = %d\n", c); Py_Finalize(); }  None of the other answers are theoretically sound. As the very first comment on the question says: Please be more specific about "numbers" We need to define multiplication, and numbers, before an answer is even possible. Once we do, the problem becomes trivial. The most popular way to do this in beginning mathematical logic is to build von Neumann ordinals on top of ZF set theory, and then use the Peano axioms. This translates naturally to C, assuming you have a set type that can contain other sets. It doesn't have to contain anything but sets, which makes it trivial (none of that casting void* nonsense in most set libraries), so I'll leave the implementation as an exercise for the reader. So, first: /* The empty set is 0. */ set_t zero() { return set_new(); } /* The successor of n is n U {n}. */ set_t successor(set_t n) { set_t result = set_copy(n); set_t set_of_n = set_new(); set_add(set_of_n, n); set_union(result, set_of_n); set_free(set_of_n); return result; } /* It is an error to call this on 0, which will be reported by running out of memory. */ set_t predecessor(set_t n) { set_t pred = zero(); while (1) { set_t next = successor(pred); if (set_equal(next, n)) { set_free(next); return pred; } set_free(pred); } } set_t add(set_t a, set_t b) { if (set_empty(b)) { /* a + 0 = a */ return a; } else { /* a + successor(b) = successor(a+b) */ set_t pred_b = predecessor(b) set_t pred_ab = add(a, pred_b); set_t result = successor(pred_ab); set_free(pred_b); set_free(pred_ab); return result; } } set_t multiply(set_t a, set_t b) { if (set_empty(b)) { /* a * 0 = 0 */ return b; } else { /* a * successor(b) = a + (a * b) */ set_t pred_b = predecessor(b) set_t pred_ab = mul(a, pred_b); set_t result = successor(pred_ab); set_free(pred_b); set_free(pred_ab); return result; } }  If you want to expand this to integers, rationals, reals, surreals, etc., you can—with infinite precision (assuming you have infinite memory and CPU), to boot. But as Kroenecker famously said, God made the natural numbers; all else is the work of man, so really, why bother? • Wow. You're even slower than me. – John Dvorak Jan 13 '14 at 10:50 unsigned add( unsigned a, unsigned b ) { return (unsigned)&((char*)a)[b]; // ignore compiler warnings // (if pointers are bigger than unsigned). it still works. } unsigned umul( unsigned a, unsigned b ) { unsigned res = 0; while( a != 0 ){ if( a & 1) res = add( res, b ); b <<= 1; a >>= 1; } return res; } int mul( int a, int b ){ return (int)umul( (unsigned)a, (unsigned)b ); }  If you consider the a[b] hack to be cheating (since it's really an add) then this works instead. But table lookups involve pointer adds too. See http://en.wikipedia.org/wiki/IBM_1620 - a conputer that actually did addition using lookup tables... Something satisfying about using a table mechanism to 'speed up' an operation that could actually be done in one instruction. static unsigned sumtab[17][16]= { { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15}, { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16}, { 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17}, { 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18}, { 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19}, { 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20}, { 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21}, { 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22}, { 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23}, { 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24}, {10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}, {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26}, {12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27}, {13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28}, {14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29}, {15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}, {16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31} }; unsigned add( unsigned a, unsigned b ) { static const int add4hack[8] = {4,8,12,16,20,24,28,32}; unsigned carry = 0; unsigned (*sumtab0)[16] = &sumtab[0]; unsigned (*sumtab1)[16] = &sumtab[1]; unsigned result = 0; int nshift = 0; while( (a|b) != 0 ){ unsigned psum = (carry?sumtab1:sumtab0)[ a & 0xF ][ b & 0xF ]; result = result | ((psum & 0xF)<<nshift); carry = psum >> 4; a = a >> 4 b = b >> 4; nshift= add4hack[nshift>>2]; // add 4 to nshift. } return result; }  • Oops, there is * char (although it's not multiplication) – Display Name Jan 12 '14 at 8:37 • Uh, table lookup uses addition -- (a[i]) is the same as (*(a + i)). – Julie in Austin Jan 29 '14 at 17:18 • @JulieinAustin I mentioned that. Table lookup can be done without adds, by merging fields (as illustrated in the IBM 1620, see link) but it's messy to set that up in C - for one thing you need to align the table to a proper address so the indices can be just or'd in. – greggo Mar 2 '14 at 2:23 I'm not sure what constitutes "cheating" in these "code troll" posts, but this multiplies 2 arbitrary integers, at run time, with no * or + operator using standard libraries (C99). #include <math.h> main() { int a = 6; int b = 7; return fma(a,b,0); }  My troll solution for unsigned int: #include<stdio.h> unsigned int add(unsigned int x, unsigned int y) { /* An addition of one bit corresponds to the both following logical operations for bit result and carry: r = x xor y xor c_in c_out = (x and y) or (x and c_in) or (y and c_in) However, since we dealing not with bits but words, we have to loop till the carry word is stable */ unsigned int t,c=0; do { t = c; c = (x & y) | (x & c) | (y & c); c <<= 1; } while (c!=t); return x^y^c; } unsigned int mult(unsigned int x,unsigned int y) { /* Paper and pencil method for binary positional notation: multiply a factor by one (=copy) or zero depending on others factor actual digit at position, and shift through each position; adding up */ unsigned int r=0; while (y != 0) { if (y & 1) r = add(r,x); y>>=1; x<<=1; } return r; } int main(int c, char** param) { unsigned int x,y; if (c!=3) { printf("Fuck!\n"); return 1; } sscanf(param[1],"%ud",&x); sscanf(param[2],"%ud",&y); printf("%d\n", mult(x,y)); return 0; }  • +1 Nice implementation of carry evaluation. I like your code :) – yo' Jan 12 '14 at 12:49 • @BЈовић: My fault, I thought trolling is not about understandig. Changed names and added comments. – Matthias Jan 13 '14 at 10:57 • sorry. I misunderstood what that tag is, and what the Q really is about. You should revert it – BЈовић Jan 13 '14 at 12:07 • @Matthias in this case it's useful to understand how it works so that we can appreciate how twisted that converging-carry operation is. In an actual code-troll situation the comments could be redacted :-) – greggo Jan 13 '14 at 14:48 • I'd like to point out that if you want to add bit-reversed numbers (with high to lo carry prop) and you don't have a 'bitrev' instruction, this is probably a perfectly reasonable approach (after changing to c>>=1 of course) – greggo Jan 13 '14 at 15:18 There are a lot of good answers here, but it doesn't look like many of them take advantage of the fact that modern computers are really powerful. There are multiple processing units in most CPUs, so why use just one? We can exploit this to get great performance results. #include <stdio.h> #include <limits.h> #include "omp.h" int mult(int a, int b); void main(){ int first; int second; scanf("%i %i", &first, &second); printf("%i x %i = %i\n", first, second, mult(first,second)); } int mult(int second, int first){ int answer = INT_MAX; omp_set_num_threads(second); #pragma omp parallel for(second = first; second > 0; second--) answer--; return INT_MAX - answer; }  Here's an example of its usage:  ./multiply
5 6
5 x 6 = 30


The #pragma omp parallel directive makes OpenMP divide each part of the for loop to a different execution unit, so we're multiplying in parallel!

Note that you have to use the -fopenmp flag to tell the compiler to use OpenMP.

Troll parts:

2. Doesn't work on negative (or large) numbers.
3. Doesn't actually divide the parts of the for loop - each thread runs the loop.
4. Annoying variable names and variable reuse.
5. There's a subtle race condition on answer--; most of the time, it won't show up, but occasionally it will cause inaccurate results.
• Why not combine this with Paul R's SIMD answer, so you can run 32x as fast instead of 8x? Although really, you want to get the GPU involved as well as the cores; then it would really blaze. :) – abarnert Jan 13 '14 at 11:06
• Might as well use OpenMPI to run it on a few machines in parallel. – millinon Jan 13 '14 at 11:22

Unfortunately, multiplication is a very difficult problem in computer science. The best solution is to use division instead:

#include <stdio.h>
#include <limits.h>
int multiply(int x, int y) {
int a;
for (a=INT_MAX; a>1; a--) {
if (a/x == y) {
return a;
}
}
for (a=-1; a>INT_MIN; a--) {
if (a/x == y) {
return a;
}
}
return 0;
}
main (int argc, char **argv) {
int a, b;
if (argc > 1) a = atoi(argv[1]);
else a = 42;
if (argc > 2) b = atoi(argv[2]);
else b = 13;
printf("%d * %d is %d\n", a, b, multiply(a,b));
}


In real life I usually respond to trolling with knowledge, so here's an answer that doesn't troll at all. It works for all int values as far as I can see.

int multiply (int a, int b) {
int r = 0;
if (a < 0) { a = -a; b = -b }

while (a) {
if (a&1) {
int x = b;
do { int y = x&r; r ^= x; x = y<<1 } while (x);
}
a>>=1; b<<=1;
}
return r;
}


This is, to the best of my understanding, very much like how a CPU might actually do integer multiplication. First, we make sure that at least one of the arguments (a) is positive by flipping the sign on both if a is negative (and no, I refuse to count negation as a kind of either addition or multiplication). Then the while (a) loop adds a shifted copy of b to the result for every set bit in a. The do loop implements r += x using and, xor, and shifting in what's clearly a set of half-adders, with the carry bits fed back into x until there are no more (a real CPU would use full adders, which is more efficient, but C doesn't have the operators we need for this, unless you count the + operator).

• The asker didn't troll. You are supposed to troll. – John Dvorak Jan 12 '14 at 5:56
• It's a stealth troll! The secret failure is on a==INT_MIN. – Jander Jan 13 '14 at 6:17
• @Jander hmm. Yeah, that's a good one. I'm guessing (on ordinary two's complement systems) the result of negating a is still negative, and the while(a) loop never terminates. – hobbs Jan 13 '14 at 6:22
• @hobbs Yeah, that sounds right to me. Otherwise a very pretty answer. – Jander Jan 13 '14 at 6:30
 int bogomul(int A, int B)
{
int C = 0;
while(C/A != B)
{

C = rand();

}
return C;
}

• This will fail horribly if the result overflows. Nice! I guess you shouldn't print, though. – John Dvorak Jan 13 '14 at 6:35
• fails for a=2, b=2, c=5 – BЈовић Jan 13 '14 at 7:12
• @BЈовић: while(C/A != B || C%A)? – abarnert Jan 13 '14 at 11:08
• Note that this is really an attempt to do the same thing as Deep Thought's successor, but for all possibly universes, instead of just the one where the answer is 42. Which would be very impressive if it weren't for the bug. And the lack of error handling in case of Vogons. – abarnert Jan 13 '14 at 13:10
• Needs multiple threads. You know, to make it efficient. – greggo Jan 13 '14 at 14:54

Throwing this into the mix:

#include <stdio.h>
#include <stdlib.h>

int mul(int a, int b)
{
asm ("mul %2"
: "=a" (a)
: "%0" (a), "r" (b) : "cc"
);
return a;
}

int main(int argc, char *argv[])
{
int a, b;

a = (argc > 1) ? atoi(argv[1]) : 0;
b = (argc > 2) ? atoi(argv[2]) : 0;

return printf("%d x %d = %d\n", a, b, mul(a, b)) < 1;
}


– Introducing something extremely unacceptable or unreasonable in the code that cannot be removed without throwing everything away, rendering the answer utterly useless for the OP.

– […] The intention is to do the homework in a language that the lazy OP might think acceptable, but still frustrate him.

• "without using the multiplication and addition operators". Nice bending of the rules - this will be absolutely useless to the asker :-) – John Dvorak Jan 12 '14 at 9:36
• This isn't really a C solution. Plus, it fails to compile on my ARM9. – abarnert Jan 13 '14 at 10:51
• @abarnert: Fail to recognize your statement as a relevant argument. – Runium Jan 13 '14 at 11:35
• @Sukminder: The question is "Is it possible to write a C program…?" Inline assembly is not C. The fact that some C compilers can also do inline assembly doesn't change that, any more than the fact that some C compilers can also do C++ or ObjC makes C++ or ObjC count as C code. – abarnert Jan 13 '14 at 12:43
• @abarnert: It is embedded code widely used in C programs. Even though it is a cross-breed one can argue it is a C program. It is even plausible OP would recognize it as C code. It is clearly not python, or? – Runium Jan 13 '14 at 13:43
#include <stdio.h>
#include <stdlib.h>

int mult (int n1, int n2);
int add (int n1, int n2 );
int main (int argc, char** argv)
{
int a,b;
a = atoi(argv[1]);
b = atoi(argv[2]);

printf ("\n%i times %i is %i\n",a,b,mult(a,b));
return 0;
}

int add (int n1, int n2 )
{
return n1 - -n2;
}

int mult (int n1, int n2)
{
int sum = 0;
char s1='p', s2='p';
if ( n1 == 0 || n2 == 0 ) return 0;
if( n1 < 0 )
{
s1 = 'n';
n1 = -n1;
}
if( n2 < 0 )
{
s2 = 'n';
n2 = -n2;
}
for (int i = 1; i <= n2; i = add( i, 1 ))
{
}
if ( s1 != s2 ) sum = -sum;
return sum;
}


Is it possible to write a C program that multiplies two numbers without using the multiplication and addition operators?

Sure:

void multiply() {
printf("6 times 7 is 42\n");
}


But of course that's cheating; obviously he wants to be able to _supply) two numbers, right?

void multiply(int a, int b) {
printf("The answer is 42, so that's the wrong question.\n");
} else {
printf("The answer is 42, but that's probably not the right question anyway.\n");
}
}

• Why, it was not obvious to me at all! – leewz Jan 15 '14 at 22:07

There's no arithmetic like pointer arithmetic:

int f(int a, int b) {
char x[1][b];
return x[a] - x[0];
}

int
main(int ac, char **av) {
printf("%d\n", f(atoi(av[1]),atoi(av[2])));
return 0;
}


The function f implements multiplication. main simply calls it with two arguments.
Works for negative numbers as well.

• Negative a, yes, negative b I don't think so. But that's fixable in many creative ways. Simplest would be sign_a ^= sign_b, sign_b = 0. – MSalters Jan 15 '14 at 12:51
• @MSalters, tested and works for all sign combinations (with Linux/gcc). – ugoren Jan 15 '14 at 15:03

# C#

I think subtraction and negation are not allowed... Anyway:

int mul(int a, int b)
{
int t = 0;
for (int i = b; i >= 1; i--) t -= -a;
return t;
}

• This is exactly the solution I thought of... but coming to the party late I knew it was a matter of scrolling down until I found that someone had already written it. Still, you get a -(-1) from me. – Floris Jan 15 '14 at 6:49

C with SSE intrinsics (because everything's better with SIMD):

#include <stdio.h>
#include <stdlib.h>
#include <xmmintrin.h>

static float mul(float a, float b)
{
float c;

__m128 va = _mm_set1_ps(a);
__m128 vb = _mm_set1_ps(b);
__m128 vc = _mm_mul_ps(va, vb);
_mm_store_ss(&c, vc);
return c;
}

int main(int argc, char *argv[])
{
if (argc > 2)
{
float a = atof(argv[1]);
float b = atof(argv[2]);
float c = mul(a, b);
printf("%g * %g = %g\n", a, b, c);
}
return 0;
}


The big advantage of this implementation is that it can easily be adapted to perform 4 parallel multiplications without * or + if required.

• I don't think this is trolling... – John Dvorak Jan 13 '14 at 10:54
• Really ? I thought the pointless, gratuitous and architecture-specific use of SIMD would qualify it for code-trolling ? – Paul R Jan 13 '14 at 11:55
• hmm... true. Didn't realise this was architecture-specific. – John Dvorak Jan 13 '14 at 12:13
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define INF 1000000

char cg[INF];

int main()
{
int a, b;

char bg[INF];
memset(bg, '*', INF);

scanf("%d%d", &a, &b);

bg[b] = 0;

while(a--)
strcat(cg, bg);

int result;
printf("%s%n",cg,&result);
printf("%d\n", result);

return 0;
}

• work only for multiplication result < 1 000 000
• So far can't get rid out of -- operator, possibly enhancing here
• using %n format specifier in printf to count the number printed characters(I posting this mainly to remind of existence %n in C, instead of %n could of course be strlen etc.)
• Prints a*b characters of '*'
• Now waiting for the 'turing machine emulation' solution. – greggo Jan 13 '14 at 14:56
• while strlen(cg) != a is a very trolling method to eliminate the -- (makes it O(N*N)). – MSalters Jan 15 '14 at 12:57

Probably too fast :-(

   unsigned int add(unsigned int a, unsigned int b)
{
unsigned int carry;

for (; b != 0; b = carry << 1) {
carry = a & b;
a ^= b;
}
return a;
}

unsigned int mul(unsigned int a, unsigned int b)
{
unsigned int prod = 0;

for (; b != 0;  a <<= 1, b >>= 1) {
if (b & 1)
}
return prod;
}

• Ungh. This is not trolling. This is an entirely reasonable way to do this. – John Dvorak Jan 13 '14 at 15:49
• It's trolly because it's too fast :-) – Timtech Jan 13 '14 at 16:09

This Haskell version only works with nonnegative integers, but it does the multiplication the way children first learn it. I.e., 3x4 is 3 groups of 4 things. In this case, the "things" being counted are notches ('|') on a stick.

mult n m = length . concat . replicate n . replicate m $'|'  int multiply(int a, int b) { return sizeof(char[a][b]); }  This may work in C99, if the weather is right, and your compiler supports undefined nonsense. Since the OP didn't ask for C, here's one in (Oracle) SQL! WITH aa AS ( SELECT LEVEL AS lvl FROM dual CONNECT BY LEVEL <= &a ), bb AS ( SELECT LEVEL AS lvl FROM dual CONNECT BY LEVEL <= &b ) SELECT COUNT(*) AS addition FROM (SELECT * FROM aa UNION ALL SELECT * FROM bb); WITH aa AS ( SELECT LEVEL AS lvl FROM dual CONNECT BY LEVEL <= &a ), bb AS ( SELECT LEVEL AS lvl FROM dual CONNECT BY LEVEL <= &b ) SELECT COUNT(*) AS multiplication FROM aa CROSS JOIN bb;  • My God, it's full of *s ! – Paul R Jan 14 '14 at 15:42 • @PaulR :) but they're not operators. – SQB Jan 15 '14 at 7:09 int add(int a, int b) { return 0 - ((0 - a) - b); } int mul(int a, int b) { int m = 0; for (int count = b; count > 0; m = add(m, a), count = add(count, 0 - 1)) { } return m; }  May contain traces of UD. #include <stdio.h> #include <stdlib.h> int main(int argc, char **argv) { int x = atoi(argv[1]); int y = atoi(argv[2]); FILE *f = fopen("m","wb"); char *b = calloc(x, y); if (!f || !b || fwrite(b, x, y, f) != y) { puts("503 multiplication service is down for maintenance"); return EXIT_FAILURE; } printf("%ld\n", ftell(f)); fclose(f); remove("m"); return 0; }  Test run: $ ./a.out 1 0
0
$./a.out 1 1 1$ ./a.out 2 2
4
$./a.out 3 2 6$ ./a.out 12 12
144
\$ ./a.out 1234 1234
1522756