A silly way to divide by 3 is to change base to 3 and then shift right. Example:
127(10) = 11201(3) 1120(3) = 0 + 2*3 + 1*9 + 1 * 27 = 6 + 9 + 27 = 15 + 27 = 42 No LUT needed. This is much like user3528438's answer, only he switches to base 16. Try it online.
// x=a*4+b=a*3+(a+b), all credit is due to user3528438 int div3(int const x) { if (x > 3) { int a = x >> 2; return a + div3(x - (a << 1) - a); } else if (x == 3) { return 1; } else { return 0; } } a non-recursive solution:
// x=a*4+b=a*3+(a+b) int div3(int x) { int q = 0; while (x > 3) // x > 5 { int a = x >> 2; q += a; //x -= (a << 1) + a; // reduce x x = a + (x & 0x3); // x = a + b } // return q + (x > 2); return q + (3 == x); } -- Let's do a quick Bresenham, maybe it works:
int div3(int const x) { int x0 = 0, y0 = 0; int dx = 3 << 1, dy = 1 << 1; int e = -(dx >> 1); while (x0 != x) { if (e > 0) { ++y0; e -= dx; } ++x0; e += dy; } return y0; } We draw a line from (0, 0) to (3, 1). Bresenham's algorithm feels much more like a division algorithm to me than a line-drawing algorithm.