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) { int a = x >> 2; q += a; x -= (a << 1) + a; // reduce x } return 3 == x ? q + 1 : q; }