I agree with Gareth. After thinking about it some more, here's my final recommendation: We are considering finite bit sequences embedded in an infinite stream, both on the left (high order bits) and the right (low order bits below the "binary point"). In the case of "positive" integers, the bit stream is 0's far to the left (high order) and 0's below the binary point to the right (low order). One way to do reverse(n) would be to flip the number about the binary point, which would make the reverse of an integer not an integer. Furthermore, we have an ambiguity in the case of numbers with an odd number of bits in the finite portion -- e.g., "1" itself. We can't place the single "1" bit on top of the binary point, but must place it to one side or the other. Since we really don't want to deal either with this ambiguity or with fractional numbers, our only other choice is to keep the result as an integer, so the only answer that makes sense is to exactly preserve the number of "0" low-order bits. So in the case of positive integers, we are focused on that finite portion between the high order 1 bit (located at bit position integer_length(n)) and the low order 1 bit (located at bit position integer_length(n&-n)-1). We would like to reverse that finite bit string, while keeping the same number of low order 0 bits. Thus, for n>0, for odd n, we simply reverse the integer_length(n) bits, while for even n, we have reverse(n)=2*reverse(n/2). Now as Gareth (and HAKMEM item 154) rightly point out, a negative integer (-n) is really just the logical complement lognot(n). This means that such an "integer" has an infinite number of "1" bits ("sign bits") to the left, and an infinite number of "1" bits to the right of the binary point. But the bit sequence "0.111111111..." to the right of the binary point converges to the number "1.0", which is why we increment the bit-complement of the number in order to produce a "negative" integer (without an infinite fractional part). So now to reverse a negative number, we really want to complement the number, thus getting an infinite string of 0's to the left and to the right of the finite number, find the reverse of those bits (as above), and then complement again. But after this second complement, we need to eliminate that infinite string of 1's to the right of the binary point by incrementing the result by 1. We now know that reverse(0)=0, reverse(1)=0, reverse(2)=2, reverse(3)=3, reverse(4)=4, reverse(5)=5, reverse(6)=6, reverse(7)=7, reverse(8)=8, reverse(9)=9, reverse(10)=10, reverse(11)=13, reverse(12)=12, reverse(13)=11, reverse(14)=14, reverse(15)=15), reverse(16)=16, reverse(17)=17, reverse(18)=18, reverse(19)=25, reverse(20)=20, reverse(21)=21, reverse(22)=26, reverse(23)=29, reverse(24)=24, reverse(25)=19, reverse(26)=22, reverse(27)=27, reverse(28)=28, reverse(29)=23, reverse(30)=30, reverse(31)=31, reverse(32)=32, reverse(33)=33, reverse(34)=34, reverse(35)=49, etc. So the first number that isn't its own reverse is 11, whose reverse is 13, and vice versa. 11base10 = 10011base2, 13base10 = 11001base2. -11base10 = ...111101100.1111...base2, so complementing this gives us ...000010011.0000...base2, the reverse of which is ...000011001.0000...base2, and the complement of that is ...111100110.1111...base2. Now incrementing by 1 to clear the .1111...base2, we get ...111100111.0000...base2, which is -13base10. So, it appears that the correct property to preserve is reverse(-n)=-reverse(n), so we can push "-" down to the leaves, or pull "-" up to the top of any expression tree. We now get reverse(-0)=reverse(0)=-reverse(0)=0, reverse(-1)=-reverse(1)=-1, etc. So, we have successfully explained why the reverse of a negative integer -- e.g., -11 -- doesn't have an infinite number of 1's to the right of the decimal point; actually it _does_, but all these 1's have been cleared by recognizing that "0.111111...base2"="1.000000...base2", so we don't have to carry around an infinite number of 1 bits below the binary point. I now feel comfortable enough to propose that this definition of reverse should be utilized in any computer language implementing "bignums" and logical operations on such integers -- e.g., Common Lisp. At 05:01 PM 6/2/2012, Gareth McCaughan wrote:
On Saturday 02 June 2012 19:32:24 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.
It seems to me that reversing should really be defined on non-negative dyadic rationals, as reflection in the decimal (binary) point. So the reverse of 1 is .1 = 1/2, the reverse of 2 = 10 is .01 = 1/4, etc. This way, trailing zeros don't introduce ambiguity.
In that case, if n is negative then its reverse ends in an infinite string of 1s. So, e.g., the reverse of -1 = ...1111 is 0.111..., which of course equals 1. In general, reverse(-n) = reverse(~(n-1)) = ~reverse(n-1) = 1-reverse(n-1) when n is a non-negative integer. Here the first "~" means "flip all the bits before the binary point" and the second "~" means "flip all the bits after the binary point".
Of course, once we allow this sort of thing reversing is no longer injective.
But, aha, for the exact same reason it is also no longer well defined. Suppose we write 1 not as 1.0000... but as 0.1111..., and then -1 not as ...1111.0000... but as ...1110.1111...; then its reversal becomes ...1111.0111... = ...1111.1000... = -1/2. Which, not coincidentally, equals -reverse(1).
In general, perhaps we "should" adopt the convention that a positive number ends with an infinite string of 0s, and a negative number ends with an infinite string of 1s; then negation is just bitwise complement, and reversal commutes with negation.
-- g