The proper definition of bit-reversal depends on the application for which it is needed. In the case of Fast Fourier Transform, the index is an N-bit integer that may be regarded as a modulo 2^N pointer into the numeric array of length 2^N. It is automatically twos-complement. Here the proper bit reversal consists of reversing all N bits, including leading zeros. -- Gene
________________________________ From: Gareth McCaughan <gareth.mccaughan@pobox.com> To: math-fun@mailman.xmission.com Sent: Saturday, June 2, 2012 5:01 PM Subject: Re: [math-fun] The reverse of the bits of a negative integer?
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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun