division by 3

[srinivasdama]

how to divide the given number by 3 using bitwise operators and what are other methods without using /,*,%.operators..

[Nick Evan]

without using /,*,%.operators..

So ' + and - ' are allowed?

example:

# include<iostream>
using std::cin;
using std::cout;
using std::endl;
using std::fixed;
 
int main()
{
 
    int iInput= 0, iTemp, iCount = 0;
    cout << "enter a number to be devided by 3" << endl;
    cin >> iInput;
    for (iTemp = iInput; iTemp >= 3; iTemp -= 3)
    {
        iCount++;
    }
    cout << iInput << " / 3 = " << iCount << " (floor)" << endl;
    cin.get();
    cin.get();
    return 0;
 }

[Rashakil Fol]

srinivasdama: Note that

1/4 + 1/16 + 1/64 + 1/256 + ...

is equal to 1/3.

You can multiply an integer by 1/4, 1/16, and other powers of 2 with the >> operator.

[Nick Evan]

1/4 + 1/16 + 1/64 + 1/256 + ... is equal to 1/3.

Ok, but:

without using /,*,%.operators

So this brings us back to the original problem. I can't see how it could be done other then my solution, or am I going blind?

[Rashakil Fol]

int y = (x * 43691) >> 17;

works for all unsigned ints x (32-bit) that are less than 98303.

And you can implement the multiplication using bitwise operators too... (note that 43691 == 0xaaab, or 1010101010101011 in binary, and the reason this works is that (1 << 17) / 3 == 0xaaaa).

unsigned int divthree(unsigned int x) {
  unsigned int y;
  y = x << 1;
  y += y << 2;
  y += y << 4;
  y += y << 8;
  y += x;
  return (y >> 17);
}

If you can use 64-bit integers, you could write the following, which works on all unsigned 32-bit ints.

unsigned int divthree(unsigned int x) {
  unsigned long long y;
  y = x << 1;
  y += y << 2;
  y += y << 4;
  y += y << 8;
  y += y << 16;
  y += x;
  return (y >> 33);
}