Perhaps we should count the low order zero bits, remove them, reverse the rest of the number as below, and then put them back, i.e., For even n>0, reverse(n)=2*reverse(n/2). This works for polynomials over GF(2), as well. For n<0, we can still define reverse(n)=reverse(n')', where n'=lognot(n). At 11:32 AM 6/2/2012, Henry Baker wrote:
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?