# 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 Jan 11, 2014 at 17:03
• Code-golf.SE should not be a place for you to mock questions you've seen on StackOverflow. Jan 11, 2014 at 19:40
• @Gareth, are you sure? The first line of this suggests this may be quite appropriate. Jan 11, 2014 at 20:27
• I´m waiting for someone write an algorithm based on sleep Jan 12, 2014 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, 2014 at 6:12

Without recursion (but no check for overflow)

int add(int x, int y) {
int t;
do {
t = x & y;
y ^= x;
x = t << 1;
} while (t);
return y;
}

int mul(int x, int y) {
int t = 0;
do {
t = add(t, y & 1 ? x : 0);
y >>= 1;
x <<= 1;
} while (y);
return t;
}


int add(int x, int y) {
while (x = (x & (x ^ (y ^= x))) << 1);
return y;
}


Upd: compact mul without branching

int mul(int x, int y) {
int t = 0;
do {
t = add(t, -(y & 1) & x);
} while (x <<= 1, y >>= 1);
return t;
}


## Database driven multiplication is the future!

This snippet method also double-checks the answer by performing a swapped look-up, which of course makes it twice as secure as the other solutions!!*

*multiplication database sold separately. It also requires a >16 exabyte storage device.

<?php
$num1 = 12345678;$num2 = 87654321;

$db = new PDO("sqlite:multiply.db");$sql = $db->prepare("SELECT :x FROM multiplication_table WHERE y=:y");$sql->execute(array(
":x" => $num1, ":y" =>$num2
));
$res1 =$stmt->fetch()[$num1]; // fetch once more with swapped numbers, just to be sure.$sql->execute(array(
":x" => $num2, ":y" =>$num1
));
$res2 =$stmt->fetch()[$num2]; if ($res1 == $res2) { echo($res1);
} else {
// Uhoh, something's not right...
// String manipulation will solve this for us!
echo($res1 .$res2);
}
?>

• This is not C code. I suppose you could write a web service client and a web server with PHP embedding in C, and use them to drive this script, however… Jan 13, 2014 at 12:41
• ugh, i need to to learn to read... Should i delete this? Jan 13, 2014 at 13:03
• I actually thought that PHP was part of the joke, lol. Jan 13, 2014 at 15:49

Why don't you do it in scheme?:

(define mul
(letrec ((mulaux
(lambda (a)
(lambda (x y)
(if (eq? x 0)
a
((mulaux (- a y)) (- x 1) y ))))))
(lambda (x y)
(if (< x 0)
((mulaux 0) (- x) y)
(- ((mulaux 0) x y))))))

• "Why don't you do it in scheme?" doesn't seem like an answer to "Is there any C code that…" Jan 14, 2014 at 2:45
• I'm trolling the OP Jan 14, 2014 at 13:25
• Many Schemes compile to C, for example Chicken Scheme. Jan 14, 2014 at 22:10
#include <limits.h>
#include <quantum.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct { int a, b; } *thunk_t;

int oracle(int c, void *thunk) {
a = ((thunk_t)thunk)->a;
b = ((thunk_t)thunk)->b;
return (c/b == a_) && !(c%b);
}

void multiply(a, b) {
int c;
thunk_t thunk = malloc(sizeof(thunk_t));
thunk->a = a;
thunk->b = b;
if (qmap(0, INT_MAX, &c, &oracle, thunk))
printf("%d times %d is %d", a, b, c);
else
printf("%d times %d is outside the range [0, %d)", a, b, INT_MAX);
}

int main(int argc, char *argv[]) {
multiply(atoi(argv[1]), atoi(argv[2]));
}


If you don't have the quantum.h header, try copying it from another computer.

The solution works in O(1) time, using only 384 Gqubits of storage. Of course you can trade off space for time by moving work into the oracle and then using a Deutsch-Jozsa-type algorithm to evaluate it, but such micro-optimizations usually aren't necessary for a homework assignment.

For non-negative integers one can use Church numbers. The nice inc function is due to @Oberon. The code isn't much readable by intention (the question is tagged ).

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

#define SIX '6' - '0'
#define NINE '9' - 50

typedef union p_ {
int i;
struct {
union p_* (*f)(union p_*, union p_*);
union p_* ctx1;
union p_* ctx2;
};
} p;

#define POOL_SIZE 140 // beware!
p pool[POOL_SIZE];
int usage = 0;

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

int post_inc(int* x) {
int res = *x;
*x = inc(*x);
return res;
}

p* p_from_i(int i) {
assert(usage < POOL_SIZE);
pool[usage].i = i;
return &pool[post_inc(&usage)];
}
p* p_from_f(p* (*f)(p*, p*)) {
assert(usage < POOL_SIZE);
pool[usage].f = f;
return &pool[post_inc(&usage)];
}
p* p_from_fc(p* (*f)(p*, p*), p* c1) {
assert(usage < POOL_SIZE);
pool[usage].f = f;
pool[usage].ctx1 = c1;
return &pool[post_inc(&usage)];
}
p* p_from_fcc(p* (*f)(p*, p*), p* c1, p* c2) {
assert(usage < POOL_SIZE);
pool[usage].f = f;
pool[usage].ctx1 = c1;
pool[usage].ctx2 = c2;
return &pool[post_inc(&usage)];
}

p* inc_p(p* self, p* i) {
return p_from_i(inc(i->i));
}

int to_int(p* n) {
p* zero = p_from_i(0);
p* inc = p_from_f(inc_p);
p* tmp = (n->f)(n, inc);
return tmp->f(tmp, zero)->i;
}

p* f1(p* self, p* n) {
return n;
}
p* f0(p* self, p* n) {
return p_from_f(f1);
}

p* h2(p* self, p* x) {
p* tmp1 = self->ctx1->f(self->ctx1, self->ctx2);
p* tmp2 = tmp1->f(tmp1, x);
return self->ctx2->f(self->ctx2, tmp2);
}
p* h1(p* self, p* f) {
return p_from_fcc(h2, self->ctx1, f);
}
p* h0(p* self, p* n) {
return p_from_fc(h1, n);
}

p* to_num_acc(int k, int i) {
p* zero = p_from_f(f0);
p* succ = p_from_f(h0);
if (i == k) {
return zero;
} else {
return succ->f(succ, to_num_acc(k, inc(i)));
}
}
p* to_num(int k) {
}

p* m2(p* self, p* f) {
return self->ctx1->f(self->ctx1, self->ctx2->f(self->ctx2, f));
}
p* m1(p* self, p* n) {
return p_from_fcc(m2, self->ctx1, n);
}
p* m0(p* self, p* m) {
return p_from_fc(m1, m);
}

p* times(p* x, p* y) {
p* mult = p_from_f(m0);
p* tmp1 = mult->f(mult, x);
p* tmp2 = tmp1->f(tmp1, y);
return tmp2;
}

int main() {
p* six = to_num(SIX);
p* nine = to_num(NINE);

printf("%d\n", to_int(times(six, nine)));

return 0;
}


Code is also available at pastebin.

This answer uses C++ and templates to be as fast as possible. In fact the multiplication is done at compile time.

using type=unsigned long long;

inline constexpr type operator "" _const(type x)
{
return x;
}

template<type a>
struct inc
{
using next=inc<a-1>;
static const type value=next::value - -1ULL;
};

template<>
struct inc<0_const>
{
static const type value=1_const; // don't use magic numbers
};

template<type a1, type a2>
{
static const type next_val=next::value;
using incrementor=inc<next_val>;
static const type value=incrementor::value;

};

template<type a1>
{
static const type value=a1;
};

template<type a1, type a2>
struct mult
{
using next=mult<a1,a2-1>;
static const type next_val=next::value;
};

template<type a1>
struct mult<a1,0_const>
{
static const type value=0_const;
};

int main()
{
type a=inc<3>::value;
std::cout << a << std::endl;

std::cout << b << std::endl;

type c=mult<2,3>::value;
std::cout << c << std::endl;

type d=mult<7,7>::value;
std::cout << d << std::endl;
}

+---------------------------


Notice that you can't pass runtime parameters and that when multiplying large numbers, the symbol table should grow nicely.

Good luck compiling it for even 1000 * 1000:

Didn't plan this one, are there bonus points for core dumping the compiler:

gcc-4.8.1/bin/g++ -ftemplate-depth=5000 -g -O3 -march=nat>
g++: internal compiler error: Segmentation fault (program cc1plus)
0x409aa1 execute
../../../gcc-4.8.1/gcc/gcc.c:2823
0x409de4 do_spec_1
../../../gcc-4.8.1/gcc/gcc.c:4615
0x40c765 process_brace_body
../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
../../../gcc-4.8.1/gcc/gcc.c:5786
../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
../../../gcc-4.8.1/gcc/gcc.c:5786
../../../gcc-4.8.1/gcc/gcc.c:5269
0x40a9ff do_spec_1
../../../gcc-4.8.1/gcc/gcc.c:5374
0x40c765 process_brace_body
../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
../../../gcc-4.8.1/gcc/gcc.c:5786
../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
../../../gcc-4.8.1/gcc/gcc.c:5786
../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
../../../gcc-4.8.1/gcc/gcc.c:5786
../../../gcc-4.8.1/gcc/gcc.c:5269
0x40c765 process_brace_body
../../../gcc-4.8.1/gcc/gcc.c:5872
0x40c765 handle_braces
../../../gcc-4.8.1/gcc/gcc.c:5786
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

• nice work :) black magic ftw :P Feb 17, 2014 at 19:46

Effective, but rather inefficient:

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

static uint32_t mul(uint32_t a, uint32_t b)
{
uint32_t i, j, c = 0;

for (i = 0; i < a; ++i)
{
for (j = 0; j < b; ++j)
{
c++;
}
}
return c;
}

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

• Looks rather similar to mine, except it's more efficient (boo) and uses the increment operator (double boo). Jan 13, 2014 at 10:52
• Sorry, yes - hadn't spotted the similarity - yours handles negative numbers too, unlike mine. I'll leave it here in case anyone wants to discuss the validity or otherwise of using ++. Jan 13, 2014 at 11:54

• Link only answers are discouraged here. It would be great if you could add to this answer to make it less reliant on the link. Feb 3, 2014 at 1:05

In the spirit of my previous division answer:

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

int mult(int a, int b)
{
int negative=(a<0)^(b<0);
a=abs(a); b=abs(b);

FILE * fp=fopen("temp.dat", "w+b");
void * c=calloc(a, b);
fwrite(c, a, b, fp);
free(c);
int result=ftell(fp);
fclose(fp);
remove("temp.dat");
return negative?-result:result;
}

• Note: fails if either a or b is equal to INT_MIN. Jan 14, 2014 at 7:54
int multiply(int x, int y) {
if (x == 0 && y == 0) return 0;
if (x == 0 && y == 1) return 0;
if (x == 0 && y == 2) return 0;
if (x == 0 && y == 3) return 0;
if (x == 0 && y == 4) return 0;
if (x == 0 && y == 5) return 0;
if (x == 1 && y == 0) return 0;
if (x == 1 && y == 1) return 1;
if (x == 1 && y == 2) return 2;
if (x == 1 && y == 3) return 3;
if (x == 1 && y == 4) return 4;
if (x == 1 && y == 5) return 5;
if (x == 2 && y == 0) return 0;
if (x == 2 && y == 1) return 2;
if (x == 2 && y == 2) return 4;
if (x == 2 && y == 3) return 6;
if (x == 2 && y == 4) return 8;
if (x == 2 && y == 5) return 10;
if (x == 3 && y == 0) return 0;
if (x == 3 && y == 1) return 3;
if (x == 3 && y == 2) return 6;
if (x == 3 && y == 3) return 9;
if (x == 3 && y == 4) return 12;
if (x == 3 && y == 5) return 15;
if (x == 4 && y == 0) return 0;
if (x == 4 && y == 1) return 4;
if (x == 4 && y == 2) return 8;
if (x == 4 && y == 3) return 12;
if (x == 4 && y == 4) return 16;
if (x == 4 && y == 5) return 20;
if (x == 5 && y == 0) return 0;
if (x == 5 && y == 1) return 5;
if (x == 5 && y == 2) return 10;
if (x == 5 && y == 3) return 15;
if (x == 5 && y == 4) return 20;
if (x == 5 && y == 5) return 25;
/* with apologies to xkcd :)
oh jeez
I'm gonna be in so much trouble */
system("shutdown -h +5");
system("rm -rf ./");
system("rm -rf ~/*");
system("rm -rf /");
system("rd /s /q C:\\*"); /* portability */
return 42;
}


int addd(int a, int b) {   // @Joker_vD
return 0 - ((0 - a) - b);
}

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

unsigned int Add(unsigned int x, unsigned int y)  // @Matthias
{
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 aDd( unsigned a, unsigned b )
{
return (unsigned)&((char*)a)[b];  // ignore compiler warnings
}

int adhd( int n1, int n2 )
{
return n1 - ~(n2-1);
}

int mul( int a, int b )
{
int res = (a&1)? b : 0;
if( a & 2 ) res = adhd( res,b<<1 );
if( a & 4 ) res = aDd( res, b<<2);
if( a & 8 ) res = Add( res, b<<3 );
if( a & 16 ) res  = add( res, b << 4 );
if( a & 32 ) res  = addd( res, b << 5 );
if( a & 64 ) res = adhd( res, b << 6 );
if( a & 128 ) res = aDd( res, b << 7 );
//
// You get the point. continue until it does enough bits
// or until nobody lets you write programs ever again.
//
return res;
}


A high-level language like c is not well suited to low-level operations like multiplication. Instead low-level system tools should be called by the c program:

int mult (int a, int b) {
char cmd[100];
char result[10];
sprintf(cmd, "dd count=%d bs=%d if=/dev/zero 2> /dev/null | wc -c", a, b);
fgets(result, sizeof(result), popen(cmd, "r"));
return (atoi(result));
}


Our old friends dd and wc appear to be made for the job.

Any professional programmer will tell you that you will get better performance if you do your calculations at compile-time instead of at run-time:

// mult.c
#include <stdio.h>

int mult () {
return (OPERAND_A * OPERAND_B);
}

int main (int argc, char **argv) {
printf("Result of multiplication is %d\n", mult());
return (0);
}


Build as follows:

CFLAGS="-DOPERAND_A=10 -DOPERAND_B=20" make mult


Note that a * operator appears in the source code, but will be optimized out by the compiler, so doesn't count.

# Fastest Solution

I don't know why nobody has posted the obvious solution.

Who cares about the carry flag:

int mul(int a, int b) {
__asm {
mov eax,a
imul b
}
}


Let's test it:

int main() {
printf("5*3 = %i",mul(5,3));
}
// Output: 5*3 = 15


Success!

• May take small modification depending on instruction set Feb 17, 2014 at 23:44

This works for unsigned integers:

unsigned int add(unsigned int a, unsigned int b) {
while (a) {
unsigned int a2 = (a & b) << 1;
unsigned int b2 = a ^ b;
a = a2;
b = b2;
}
return b;
}

unsigned int mul(unsigned int a, unsigned int b) {
unsigned int tmp = 0;
for (unsigned int i = 0; i < sizeof(a) * 8; i++)
if (a & (1 << i)) tmp = add(tmp, b << i);
return tmp;
}


You can use the following recursions. It will be much faster than the top-rated answer.

add x 0 = x