In Lisp, there are a number of operations on the bit representation of 2's complement arbitrary-precision integers. One function missing is that of "reverse" -- probably because no one came up with a good suggestion about what it should mean. If I have a bit _vector_ (finite ordered sequence of bits) in Lisp, the length is well-defined, so the reverse of this bit vector is also well-defined; Lisp therefore does define the reverse of a bit _vector_. For all finite bit-vectors x, we have the nice properties that reverse(reverse(x))=x; for the zero-length bit-vector x, reverse(x)=x. What now should be the definition for the reverse of the bits of an integer? If the integer is non-negative, then the function "integer-length(n)" returns the number of bits necessary to hold the integer n; if we take integer-length(n) as the length of the appropriate bit-sequence, then we get a well-defined result. In particular, for n>0, reverse(n) is always odd, because the high-order bit has become the low order bit; for n=0, where integer-length(0)=0, so we have a zero-length sequence which is an identity for reverse -- i.e., reverse(0)=0. So at least for odd n, n>0, reverse(reverse(n))=n, which is comforting. Unfortunately, for even n, this definition of reverse(n) loses all the information about the number of low order 0's in the number, and so reverse(reverse(n))/=n for all n. In order to get reverse(reverse(n))=n for all n>=0, reverse(n) needs to be 1-1 -- i.e., an injection -- i.e., it doesn't lose any information. If we consider the the bits of the bignum n>=0 to be a polynomial p(x) with coefficients in GF(2), then there _are_ no negative elements, and the above definition works when p(0)=1. After all, we reverse the list of polynomial coefficients all the time -- e.g., reversing a polynomial inverts all the roots: r->1/r; this requires r/=0 <=> p(0)=1. So this representation gains us no new insight. But what should the reverse(n) for the 2's complement integer n<0 be? I think we still need reverse(reverse(n))=n, so we obviously need to have reverse(x)<0 for some x's. Since the positive integers are already accounted for, such x's must be <0. So reverse(n)<0 for n<0. It would be nice if integer-length(reverse(n)) is O(integer-length(n)). If we consider n<0 as simply an infinite bit string, perhaps reverse(n)=reverse(n')', i.e., we first complement n = n' = lognot(n), compute reverse(n'), and then lognot again to produce reverse(n')'. This definition gets us reverse(-1)=reverse((-1)')'=reverse(0)'=0'=-1. But what other properties do we want reverse(x) to have/preserve? I haven't looked at 2-adic numbers; perhaps there is an insight there? Does anyone here have any thoughts?