If the P/A-M/Z is a negative value, it just means that the P/A - M/Z is no longer a valid measure of soil pressure. Assume a point of uplift, and calculate additional moment on the remaining contact area due to eccentricity, then calculate P/A and M/Z for that reduced area, and adjust the point of uplift where P/A - M/Z is zero at that point. For a rectangular area with moment aligned with a face, I think that works out to a direct solution, with circular foundations, it becomes iterative. As you get near the tipping point, soil pressure on the heavy side increases non-linearly with moment, so check with load/safety factors applied to the load, not just the soil bearing.
One of the tank standards requires with 1.5x overturning moment, bearing on the heavy side is still less than ultimate, or with 1.0x overturning, bearing on the heavy side is less than allowable. For ASCE 7, that would be 1.3 or 1.6 factor on the overturning moment and 0.9 factor on the dead load. For a crane, I assume factors would vary.
You can calculate rotation at the base and include additional moment for P-delta effects in the overturning if desired.