multiplying by 321 without using * or / operators

This is a discussion on multiplying by 321 without using * or / operators within the C++ Programming forums, part of the General Programming Boards category; I'm trying to write a program that multiplies any given number by 321 without using the built in multiplication or ...

  1. #1
    Banned
    Join Date
    Jan 2003
    Posts
    1,708

    multiplying by 321 without using * or / operators

    I'm trying to write a program that multiplies any given number by 321 without using the built in multiplication or division operators (cannot do x * 321 or x / (1/321) ). I think I am going to have to use the bitwise operators, and then combine some sort of a mask using some bitwise operator. If anyone has done this before I'd really appreciate some help. I tried finding a pattern in the sequence of bits as it relates x (the number I'm multiplying) and x multiplied by 321. I could not find any static mask that I can use in all situations. I think I am going to have to calculate the mask, i.e I'm going to have to use some sort of an equation to create a mask and then use the mask to multiply x by 321? This is pretty confusing stuff Does it seem like I'm remotely on the right track? I feel lost.

  2. #2
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    Hint:

    can you think of three powers of 2 that add up to 321?

  3. #3
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    1) A loop containing additions

    2) Bitshifts combined with additions. Note that 321 = 256 + 64 + 1, all three powers of 2.

    3) x + x + x + x + x + ... + x + x (321 times).
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,453
    Dont you people have any original homework anymore?

    If you really want to make it interesting, add '+' to the list of operators you can't use.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Banned
    Join Date
    Jan 2003
    Posts
    1,708
    I think it's
    rslt = (value << 8) + (value << 6) + 1;

    EDIT: This doesn't make sense, and it's how I got what I wrote above
    Hint

    To multiply by 20, you would do
    rslt = (value *16) + (value *4);

    Which can be written as
    rslt = (value <<4) + (value<<2);
    if I want to multiply 3 by 20, then we have:
    rslt = (3 << 4) + (value << 2);
    which is the same as
    rslt = (3 * 2)^4 + (3 * 2) ^2
    which does not yield 60, it yields:
    1332
    Unless I'm missing something, in which you'll kindly point it out (and not insult me)
    Last edited by Silvercord; 03-23-2003 at 12:58 PM.

  6. #6
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    no *, no /, no +, no loop

    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
        int x;
        cout << "enter an integer > ";
        cin >> x;
        cout << (x|x<<8|x<<6);
        return 0;
    }
    but it only works for inputs of 1 through 4. Otherwise, replace (x|x<<8|x<<6) with (x+(x<<8)+(x<<6))
    Last edited by R.Stiltskin; 03-23-2003 at 01:16 PM.

  7. #7
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    rslt = (3 << 4) + (value << 2);
    which is the same as
    rslt = (3 * 2)^4 + (3 * 2) ^2
    which does not yield 60, it yields:
    1332
    not true:
    (3 << 4) is the same as 3*(2^4) = 48

  8. #8
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    rslt = (value << 8) + (value << 6) + 1;
    Should be:
    rslt = (value << 8) + (value << 6) + value;
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,453
    Multiply by 321 without using a whole bunch of ops you would normally think to use

    Code:
    #include<stdio.h>
    
    int increment( int blah ) {
      unsigned int i;
      for (i = 1; i; i <<= 1) {
        if (!(blah & i)) {
          blah |= i;
          break;
        } else {
          blah ^= i;
        }
      }
      return blah;
    }
    
    int add ( int a, int b ) {
      b = ~b;
      while ( (b=increment(b)) != 0 ) a = increment( a );
      return a;
    }
    
    int mul321 ( int value ) {
      int result = 0;
      result = add( result, value << 8 );
      result = add( result, value << 6 );
      result = add( result, value      );
      return result;
    }
    
    int main ( ) {
        int i;
        for ( i = 0 ; i < 20 ; i++ ) {
            printf( "%2d %5d %5d\n", i, i*321, mul321(i) );
        }
        return 0;
    }
    Writing
    int decrement ( int blah );
    int sub ( int a, int b );
    Is left as an easy exercise for the reader
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical Operators in C++
    By Flecto in forum C++ Programming
    Replies: 4
    Last Post: 05-15-2009, 07:17 AM
  2. How Does Increment Operators Work...??
    By ajayd in forum C Programming
    Replies: 37
    Last Post: 12-31-2008, 09:01 AM
  3. Bolean Operators hurt my head. (Trouble understanding) :(
    By Funcoot in forum C++ Programming
    Replies: 3
    Last Post: 01-20-2008, 06:42 PM
  4. operators???
    By arjunajay in forum C++ Programming
    Replies: 11
    Last Post: 06-25-2005, 04:37 AM
  5. Operators
    By George in forum C++ Programming
    Replies: 3
    Last Post: 04-02-2003, 06:35 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21