write a function to divide a number by 3 without using /, % and * operators . itoa() avalable ?

Question

I tried myself to solve but I could not get any clue.

Please help me to solve this.

Answer 1

Sounds like homework :)

I image you can write a function which iteratively divides a number. E.g. you can model what you do with a pen and a piece of paper to divide numbers. Or you can use shift operators and + to figure out if your intermediate results is too small/big and iteratively apply corrections. I'm not going to write down the code though ...

Answer 2

Slow and naive, but it should work, if an exact divisor exists. Addition is allowed, right?

for number from 1 to input
  if number == input+input+input
    return number

Extending it for fractional divisors is left as an exercise to the reader. Basically test for +1 and +2 I think...

Answer 3

for positive integer division

result = 0
while (result + result + result < input)
 result +=1
return result

Answer 4

How about this, in some kind of Python like pseudo-code. It divides the answer into an integer part and a fraction part. If you want to convert it to a floating point representation then I am not sure of the best way to do that.

 x = <a number>  
 total = x
 intpart = 0
 fracpart = 0

 % Find the integer part
 while total >= 3
    total = total - 3
    intpart = intpart + 1

 % Fraction is what remains
 fracpart = total


 print "%d / 3 = %d + %d/3" % (x, intpart, fracpart)

Note that this will not work for negative numbers. To fix that you need to modify the algorithm:

  total = abs(x)
  is_neg = abs(x) != x

  ....

  if is_neg
      print "%d / 3 = -(%d + %d/3)" % (x, intpart, fracpart)

Answer 5

if(number<0){ // Edited after comments
number = -(number);
}
quotient = 0;
while (number-3 >= 0){ //Edited after comments..
number = number-3;
quotient++;
}//after loop exits value in number will give you reminder

EDIT: Tested and working perfectly fine :(

Hope this helped. :-)

Answer 6

EDIT: Oops, I misread the title's question. Multiply operator is forbidden as well.

Anyway, I believe it's good not to delete this answer for those who didn't know about dividing by non power of two constants.

---

The solution is to multiply by a magic number and then to extract the 32 leftmost bits:

divide by 3 is equivalent to multiply by 1431655766 and then to shift by 32, in C:

int divideBy3(int n)
{
  return (n * 1431655766) >> 32;
}

See Hacker's Delight Magic number calculator.

Answer 7

If you can use bitwise o

Answer 8

Hi

This is very easy, so easy I'm only going to hint at the answer --

Basic boolean logic gates (and,or,not,xor,...) don't do division. Despite this handicap CPUs can do division. Your solution is obvious: find a reference which tells you how to build a divisor with boolean logic and write some code to implement that.

Regards

Mark

Answer 9

Using the mathematical relation:

1/3 == Sum[1/2^(2n), {n, 1, Infinity}]

We have

int div3 (int x) {
   int64_t blown_up_x = x;
   for (int power = 1; power < 32; power += 2)
      blown_up_x += ((int64_t)x) << power;
   return (int)(blown_up_x >> 33);
}

If you can only use 32-bit integers,

int div3 (int x) {
     int two_third = 0, four_third = 0;
     for (int power = 0; power < 31; power += 2) {
        four_third += x >> power;
        two_third += x >> (power + 1);
     }
     return (four_third - two_third) >> 2;
}

The 4/3 - 2/3 treatment is used because x >> 1 is floor(x/2) instead of round(x/2).

Answer 10

Are you supposed to use itoa() for this assignment? Because then you could use that to convert to a base 3 string, drop the last character, and then restore back to base 10.

Answer 11

Here's a solution implemented in C++:

#include <iostream>

int letUserEnterANumber()
{
    int numberEnteredByUser;
    std::cin >> numberEnteredByUser;
    return numberEnteredByUser;
}

int divideByThree(int x)
{
    std::cout << "What is " << x << " divided by 3?" << std::endl;
    int answer = 0;
    while ( answer + answer + answer != x )
    {
        answer = letUserEnterANumber();
    }
}

;-)

Answer 12

unsigned int  div3(unsigned int m) {
   unsigned long long n = m;
   n += n << 2;
   n += n << 4;
   n += n << 8;
   n += n << 16;
   return (n+m) >> 32;
}

Answer 13

x/3 = e^(ln(x) - ln(3))

Answer 14

Convert 1/3 into binary

so 1/3=0.01010101010101010101010101

and then just "multiply" whit this number using shifts and sum

Answer 15

long divByThree(int x)
{    
  char buf[100];
  itoa(x, buf, 3); 
  buf[ strlen(buf) - 1] = 0; 
  char* tmp; 
  long res = strtol(buf, &tmp, 3);

  return res;
}