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.)



    The answer with the most upvotes on January 19th 2014 wins.



    Note: This is a question. Please do not take the question and/or answers seriously. More information is in code-trolling.


    Please be more specific about "numbers".

    @PaulR use your fantasy

    I guess the original Q meant any numbers...

    The given example doesn't work with integers so I'm guessing it may be a floating point task?

    Why doesn't it work with ints? (except 0)

    1/n is 0 for n > 1 when n is an int.

    oh.. yes, you're right... doesn't matter for the question

    Code-golf.SE should not be a place for you to mock questions you've seen on StackOverflow.

    @Gareth, are you sure? The first line of this suggests this may be quite appropriate.

    @DarrenStone I've enjoyed being a member of this site for a couple of years now and I'm seriously concerned that questions like this are mean and unpleasant. I don't want to see this site become reddit-like.

    @Gareth, I certainly didn't intend to be mean with my comment. I wrestle with the spirit and noise that [tag:code-trolling] questions bring, but OP has tagged the question correctly and code-trolling is based on jest and mockery of real questions.

    @DarrenStone I think you misunderstood me, I think this type of question which mocks an SO user is a bit mean. Your comment was a reasonable one (as they usually are).

    I´m waiting for someone write an algorithm based on sleep

    Since all computers are essentially adding machines, with flow control, comparators, and about every other operation including incrementing the program counter dependent on addition then no, in the strictest sense this program can't be written, at least not for any non-analogue computer.

    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 yeah, but the O(bits^2) solution is inappropriate for a code-trolling challenge :-)

    @Gareth - I don't see that the OP is in any way being mean or "mocking" the SO user.

    @JanDvorak: Multiplying is O(digits^2). If your computer can do it faster than that, it's because it has O(digits^2) transistors that all operate simultaneously.

    last week I had an interview I was asked to multiply a number with `7` without using `+` and `*` I answered `result = (number << 3) - number`.

    @GrijeshChauhan: your solution does not work for the full valid range of possible input values (it overflows for part of the range).

    @PaulR Yes. You are correct, in-fact it can cause undefined behavior if left-shit sets sign-bit(msb). But fortunately interviewer was happy :) I guess because he asked question in Puzzle section(not in programming). Btw I now like @ MarkLakata trick.

    @GrijeshChauhan: I think you're confused between left shift and right shift of signed values - the only problem with the left shift in your solution is the potential for overflow in the intermediate result - otherwise it's fine.

    @GrijeshChauhan: To avoid overflow of the intermediate result, set `result = (number<<2) + (number <<1) + number`

    @PieterGeerkens yup, this kind of technique can be helpful, but you are using `+`!!

    @GrijeshChauhan: Oops! Time for a coffee I think.

  • Oberon

    Oberon Correct answer

    7 years ago

    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) {
    return x?add(dec(x),inc(y)):y;
    }

    int mul(int x, int y) {
    return x?x^1?add(y,mul(dec(x),y)):y:0;
    }

    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 ;)

    The sheer elegance of this has dissuaded me from posting my ripple carry adder based solution. Bit-wise addition by recursion. Wow.

    Wow. Nice increment operator, more readable than mine :-)

    If Picasso was a programmer...

    `+` can be made of two `-`s, so `add` is not necessary (only if you must deal with unsigned integers)

    @SargeBorsch But where'd the fun be in _that_?

    Could someone explain one of these functions to a relatively novice programmer? ^^

    @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.

    Always use recursion? Isn't that only true for Haskell?

    It is kind of funny that this kind of an approach would one day cause this...

    Doesn't the increment function go into an infinite loop for -1? (0xFFFF) ideone shows (-1 >> 1) == -1.

    What would this look like for floats?

    @Destrictor, that's because I'm stupid and I used `signed int`s. Problem is, GCC (and most compilers) treat shifts on `signed` types as arithmetic shifts instad of logical ones.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM