how to multiply two integers using bitwise operators

Discussion in 'C Programming' started by sandy_pt_in, Sep 21, 2003.

  1. sandy_pt_in

    sandy_pt_in Guest

    How to mulitply two integer numbers using bitwise operators in C
    language.Please reply as early as possible
     
    sandy_pt_in, Sep 21, 2003
    #1
    1. Advertisements

  2. sandy_pt_in

    Aggro Guest

    You do know how to sum them, right? Well check this out:

    3*4 == 3+3+3+3

    3*4 == 4+4+4
     
    Aggro, Sep 21, 2003
    #2
    1. Advertisements

  3. sandy_pt_in

    osmium Guest

    Emulate the way you learned to do it for decimal numbers in elementary
    school.
     
    osmium, Sep 21, 2003
    #3
  4. sandy_pt_in

    Nick Austin Guest

    Well that's the easy bit. However + is not a bitwise operator.

    Adding using only the bitwise operators is the hard bit of
    this problem.

    Nick.
     
    Nick Austin, Sep 21, 2003
    #4
  5. Think about how you would do long multiplication in binary.
     
    Slartibartfast, Sep 22, 2003
    #5
  6. Can the addition operator be used?

    I was taught about left-shift and add, but adding is not a
    bitwise operator.

    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c++-faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.raos.demon.uk/acllc-c++/faq.html
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
     
    Thomas Matthews, Sep 22, 2003
    #6
  7. ....but it is easy to implement in terms of bitwise operators, as long as you remember the truth table for the full adder.
     
    Slartibartfast, Sep 22, 2003
    #7
  8. sandy_pt_in

    Micah Cowan Guest

    ....but the OP reeks of homework...
     
    Micah Cowan, Sep 22, 2003
    #8
  9. sandy_pt_in

    sandy_pt_in Guest

    Condition was to use only bitwise operators. Eventhough can you tell
    me that method you know, using add operation.I will scratch my head to
    get somthing out of it.
     
    sandy_pt_in, Sep 23, 2003
    #9
  10. sandy_pt_in

    LibraryUser Guest

    Start with a one-bit adder, where each input and output is a
    single bit. Then cascade these to form multiple bit adders.
     
    LibraryUser, Sep 23, 2003
    #10
  11. sandy_pt_in

    osmium Guest

    <I can't make sense of the attributions, so I snipped them. I suspect there
    is one person using two identities.>
    A full adder has three inputs: addend, augend and carry in and two outputs:
    sum and carry out. Carry in is 0 for the rightmost bit. Make a truth
    table and note that the exclusive or is very useful.
     
    osmium, Sep 23, 2003
    #11
  12. sandy_pt_in

    Morris Dovey Guest

    Addition can be viewed as a sequence of bitwise operations.
    Exclusive or-ing the addend and augend yields all of the partial
    sum bits; while and-ing the addend and augend yields all of the
    carry bits. Shift the carry bits left one position.

    Put the partial sum in the addend.

    If there are no 1's in the carry bits, then you're done and the
    result of the addition is in the addend.

    Otherwise put the carry bits in the augend and repeat.

    There are other ways to get the job done; but this is the easiest
    to describe. 8^)

    It's fairly easy to back into subtraction by negating and adding;
    and a (very) simplistic multiplication can be implemented using
    the addition algorithm to repeatedly add one of the factors to
    the product and addition of -1 to the other factor.

    Division can be done as a bitwise successive approximation; but
    requires development of a bitwise magnitude comparison (left as
    an exercise for the student :)
     
    Morris Dovey, Sep 23, 2003
    #12
  13. That's why I didn't say any more. I'm in a good mood so I don't mind
    giving a general hint.
     
    Slartibartfast, Sep 23, 2003
    #13
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.