Signed Integer Division Optimization
I don't think you can get away without more logic gates. Consider 16-bit signed divider:


-16384 / -1 = 16384
-32768 / -1 = overflow


(-32768 is a valid two's complement 16-bit signed integer).

It's situations like this when microcode seems very alluring...