bit shifting

Dan Ingalls DanI at wdi.disney.com
Thu Apr 23 05:23:00 UTC 1998


Folks -

First of all, thanks to the several people who answered my questions about whether they had found it to be either useful or enlightening to do bit manipulation with negative numbers.

Out of all the correspondence, other than motherhood arguments, the only mention of any useful aspect of this came from Wim Boot:

>Yes. If you have a bit vector of arbitrary size and you want to clear
>certain bits the normal way is to bitAnd: with a negative number. It's
>the only practical way to preserve an unknown number of bits to the left.

I'm still mildly opposed to bit manipulation on negative numbers, mainly for simplicity, although ANSI compliance is a weak second reason.  To that end I have assembled a changeSet that does away with logic on negative numbers without breaking LargeInteger division.  It also adds the method
	bitClear: aMask
		"Return a number equal to the receiver, except
		with all bits cleared that are set in mask."
		^ (self bitOr: aMask) - aMask
which seems to do a fine job of clearing bit fields regardless of number size.

These changes will be available for test as part of the forthcoming 2.0 beta release (we're shooting for 1st week of May, by the way).  Also included will be a faster and more accurate print routine from Tim Olson, an isPositive/isNegative protocol (from me) to replace the methods that the mathematicians hate, and a number of Fraction speedups from Leandro Caniglia and colleagues.
-------------------------------------------------------------

That all said, of course, I sympathize with the folks who consider it non-uniform to forbid logic on negative numbers.  After all, isn't Squeak supposed to be simple and general?

Now, I believe that this is the only place where Squeak would reveal the underlying representation of negative numbers.  And -- guess what -- the ACTUAL representation is not really two's complement at all!  It's not one's complement either.  It is a mixed strategy in which SmallIntegers are two's complement, and LargeIntegers are sign-and-magnitude.  I am on the verge of implementing a uniform extension of bit logic to negative numbers (just to silence the nit-pickers ;-), but I have the following question:

If bit manipulation is the only place where we reveal the representation of negative numbers, then why on earth choose two's complement?  Sign-and-magnitude would be a much simpler choice, because bit-wise logic is the same regardless of sign, and it would be a trivial uniform interpretation (it would also tie in perfectly with the actual implementation of our LargeIntegers).  Even one's complement would seem to make more sense, since the relationship between a positive number and its negative is a simple bitwise complement.

So, if we were to reveal a specific bit representation for the purpose of allowing logic on negative numbers, can anyone explain why it should be two's complement?

	- Dan





More information about the Squeak-dev mailing list