Due to the imprecise nature of the question, it is hard to give a precise answer. Since my "post" mostly shares links to my own thoughts and answers to related questions, I won't even try to pretend that this would be an appropriate answer to the question (-> community wiki).

I'm asking in the context of ALU design, ...

I also pondered questions related to arithmetic and CPU primitives in the past, but more from the perspective of the "user" of the CPU, not the "designer".

The answer to my question Which associative and commutative operations are defined for any commutative ring? hints at how to answer this type of question from a category theory perspective where "natural operation" has a precise meaning. The discussion also provides examples of operations that are not "natural" in that sense, but are still defined generically for any commutative ring.

My motivation for pondering questions of which CPU primitives would be needed for "good support of parallelization" of the type that "would be available to hardware itself on the circuit level" can be seen in my question Is scalable hardware support for LogCFL (= sAC^1) possible? and in my unfocused review of related work and "opinions" in ALogTime, LogCFL, and threshold circuits: dreams of fast solutions. Uzi Vishkin seems to have made a much more serious effort than I ever will, and even argued his case from an economic perspective:

Alas, the software spiral is now broken: (a) nobody is building hardware that provides improved performance on the old serial software base; (b) there is no broad parallel computing application software base for which hardware vendors are committed to improve performance; and (c) no agreed-upon architecture currently allows application programmers to build such software base for the future

My own CPU "user" perspective (and actual relevant work and an appropriate short survey of existing work) can be seen in Theory and practice of signed-digit representations and in my answer to the question What number representation is this? This material might be interesting in that it shows that there is both relevant existing work that is not widely known, as well as useful representation systems not yet properly explored and worked out.

I recently revisited that kind of questions from the perspective to focus less on numbers and arithmetic: Useful primitives CPUs could provide, from TC0 (or NC1)

I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational primitives could exist, that are sometimes more useful than numbers.

Interestingly enough, I learned this Monday about concrete actually missing CPU primitives from this perspective: "shuffle" operations between the individual bytes and bits of CPU registers. AES seems to use those, and the non-availability of those "shuffle" operations currently seems to make hardware implementation much faster than software implementation than really necessary. But that still raises the basic question again whether it would have been possible for CPUs to provide a sufficiently comprehensive set of primitives.