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); } --
// x=2a+b=3a+(b-a) int div3(int x) { int q = 0; while ((x < 0) || (x > 5)) { int a = x >> 1; q += a; x = (x & 1) - a; // possible approximation: x = -a; } return q + (x > 2); } this is usually approximated as:
int div3(int x) { int q = 0; do { q += x >>= 1; } while (x = -x); return q; }