mptz
commented
5 years ago Another source for operations would be MMIX, which includes ANDN (bitclear above; Knuth uses '\' as his C-style syntax), ORN (|~), and SADD--sideways addition, a binary operation generalizing popcount. He has a number of other interesting bitops.
Nats should support bit operations including bit-length, bitwise NOT, count-leading-ones, count-trailing-ones/zeroes, population count, set-bit, clear-bit, test-bit, AND, NAND, OR, NOR, XOR, XNOR (bitwise equality), bitclear (AND NOT), SET (to all 1s), CLEAR (to all 0s), left & right shifts, left & right rotations. These operations must not expose the representation of nats via 32-bit limbs--they might treat nats as bitstrings whose length is defined by the highest set bit, or they could take an additional bit-length argument. The additional argument would enable a count-leading-zeroes operation and would affect the semantics of binary operations in general.
Since this will add 16+ binary operations for nats alone it's worth thinking about whether they should all be first-class native VPU operations (bloating the instruction set) or implemented via a CISC mechanism. At least some should be the latter. Bitwise nat operations should be rare in most code bases and this may form a good first virtual coprocessor.
Ints will not support bitwise operations for now due to my unwillingness to expose their representation (as the current sign-magnitude, potential 2's complement, etc). Java's solution for BigInteger is to define the visible operations in terms of 2's complement while hiding the representation, which seems reasonable at first sight, but I'm not going there without a more pressing need given the ease of int->nat conversions.