3 ms·
The top-voted answer implements addition. If you're allowed to do that, the subtraction-based division algorithm is easy and foolproof if not as fast: u32
by psykotic 14y ago
The top-voted answer implements addition. If you're allowed to do that, the subtraction-based division algorithm is easy and foolproof if not as fast:
u32 add(u32 x, u32 y)
{
u32 z = 0;
for (u32 c = 0, m = 1; m; m <<= 1)
z |= (x ^ y ^ c) & m, c = ((x & y) | (x & c) | (y & c)) << 1;
return z;
}
u32 neg(u32 x) { return add(~x, 1); }
u32 sub(u32 x, u32 y) { return add(x, neg(y)); }
u32 lt(u32 x, u32 y) { return sub(x, y) >> 31; }
u32 div3(u32 x)
{
u32 q = 0;
assert(lt(-1, x)); // x >= 0 iff -1 < x
while (!lt(x, 3)) x = sub(x, 3), q = add(q, 1);
return q;
}