Divide a number by 3 without using any of operators (%,/,*)

[jbourne]

I have got a C function to do the above by googling it .
But can you please explain the working of the following code.

int divideby3 (int num)
{
  int sum = 0;
  while (num > 3) {
        sum += num >> 2;
                num = (num >> 2) + (num & 3);
  }
  if (num == 3) ++sum;
  return sum;
}

[Disch]

This is the wrong forum for this (this isn't an article).

But this is interesting so I'll reply. It's hard to explain in words... but it basically works like so:

To understand this.. you have to know the following 2 points:

1) num >> 2 effectively is the same as num / 4
2) and num & 3 effectively is the same as num % 4

If you don't understand why, it has to do with binary representations of integers which I don't feel like getting into right now, so just trust me.



The routine sort of picks away at num by understanding that x/3 >= x/4 (for all positive values of x). If x/4 is 3, then you know x/3 is at least 3.

Now consider this. let's plug the number 11 into this routine.

First what it does is: 11/4 = 2 remainder 3
it then figures that since 11/4=2, then 11/3 must be at least 2, so it adds that 2 to the 'sum'

it then does a neat trick to subtract 3*2 from 'num'. It does this by catching the remainder of the /4 (num&3) with the remainder of the /3 (num>>2) and adding them together. Think of it like this.... every time you subtract 4, you're subtracting 3 remainder 1:

 4 / 4 = 1.   4 \ 3 = 1 remainder 1
 8 / 4 = 2.   8 \ 3 = 2 remainder 2
12 / 4 = 3.  12 \ 3 = 3 remainder 3
16 / 4 = 4.  16 \ 3 = 4 remainder 4
..etc

(Of course the remainders are higher than 3, but that doesn't matter)

since X/4 is the same as the remainder from X/3... by summing the remainders of both X/4 and X/3 we effectively are removing the result of /3.

Gah I'm explaining this poorly.

Here's an example:

11 / 4 = 2 remainder 3
therefore 11 / 3 = 2 remainder 2 (sort of... as per the formula explained above)

since 11 / 3 got us 2, we need to subtract 2*3 from 11 to remove the 3's we just divided out of 11. But how can we get 11 - 2*3 without multiplying? By tallying the remainders:

sum the remainders = 5

And it just so happens that 11 - 2*3 is also 5. That's no coincidence... it'll work out that way every time. I can't really explain why any better than I tried to... you just have to visualize it.

ANYWAY the routine keeps doing that until num gets small enough.

[vukki]

btw, it wouldn't work with negatives of course, so choosing an int instead of unsigned type looks kinda strange.