In Emacs Lisp, is the sign of a fixnum part of its binary representation or stored in some metadata? What's the distinction between positive and negative fixnums?
Can the sign be switched in the result after a bit shifting operations? (It looks like it can, but how?)
I'm trying to find out how bitwise operations on fixnums work, especially when it comes to bit shifting and sign.
Yet, what I observe and what is documented seem slightly mutually contradictory (or at least I'm unsuccessfully trying to reconcile both).
Please note that by "binary representation", I mostly mean "part of actual data and not metadata".
In the GNU Emacs Lisp Reference Manual, the difference between lsh ("logical" shifting) and ash ("arithmetic" shifting) is documented with the following description and examples (that assume 30-bit fixnums):
[...] lsh behaves like ash except when integer and count are both negative [...]
; binary values
(ash -7 -1) ; -7 = ...111111111111111111111111111001
⇒ -4 ; = ...111111111111111111111111111100
(lsh -7 -1)
⇒ 536870908 ; = ...011111111111111111111111111100
(ash -5 -2) ; -5 = ...111111111111111111111111111011
⇒ -2 ; = ...111111111111111111111111111110
(lsh -5 -2)
⇒ 268435454 ; = ...001111111111111111111111111110
The difference seems to be that with right shifting, ash will introduce 1 bits on the left while lsh will introduce 0 bits. And this seems to have an impact on sign of the result as when shifting a negative fixnum to the right, lsh will evaluate to a positive fixnum while ash will result to a negative one.
This suggests to me that the sign is part of the binary representation and is impacted by right-shifting.
On the other hand, I tried to left-shift 1 until I get a bignum:
I started a ielm session in Emacs (M-x ielm RET).
ELISP> (setq mask 1)
1
(#o1, #x1, ?\C-a)
ELISP> (list (setq mask (lsh mask 1)) (fixnump mask) (natnump mask))
(2 t t)
ELISP> (list (setq mask (lsh mask 1)) (fixnump mask) (natnump mask))
(4 t t)
...
ELISP> (list (setq mask (lsh mask 1)) (fixnump mask) (natnump mask))
(1152921504606846976 t t)
ELISP> (list (setq mask (lsh mask 1)) (fixnump mask) (natnump mask))
(2305843009213693952 nil t)
ELISP>
If there was a sign bit in the binary representation, and if that bit was the most significant one, I'd expect that successive left-shifts of a 1 would ultimately result in only the sign-bit to be set to 1 (which would probably result in a most-negative-fixnum).
This suggests to me that the sign might be not a part of the binary representation.
I've found this post: Why are fixnums in Emacs only 29 bits? and the accepted answer suggests that part of the value is dedicated to describing the variable type. I'm therefore considering the possibility that part of this metadata holds the sign of a fixnum (and that it's not part of its actual data).
lsh/ash don't exactly do a raw bit-shift:They are described this way (using M-h f FUNC RET in Emacs):
ash:(ash VALUE COUNT)
[...]
Mathematically, the return value is VALUE multiplied by 2 to the power of COUNT, rounded down. If the result is non-zero, its sign is the same as that of VALUE. In terms of bits, when COUNT is positive, the function moves the bits of VALUE to the left, adding zero bits on the right; when COUNT is negative, it moves the bits of VALUE to the right, discarding bits.
[...]
lsh:(lsh VALUE COUNT)
[...]
Return VALUE with its bits shifted left by COUNT. If COUNT is negative, shifting is actually to the right. In this case, if VALUE is a negative fixnum treat it as unsigned, i.e., subtract 2 * ‘most-negative-fixnum’ from VALUE before shifting it.
[...]
This doesn't tell much about how the sign is represented, but since those function also accept bignums, I doubt they simply do a straight raw bit shift.
So, how does all of this work in the end?
Fixnums are represented in two's complement format. In this representation, the high-order bit is the sign; if it's set, the number is negative. You can see this in the binary representation of -7
111111111111111111111111111001
Arithmetic shift preserves the sign of the number, it's equivalent to multiplying by the given power of 2. When you shift right (negative count), the sign bit is shifted as with data bits, but also refilled in with the same value.
Logical shift treats the value as just raw bits, like an unsigned type in C. When shifting right, the sign bit is shifted, but refilled with a 0 bit. The result is that shifting a negative value will produce a positive number. This is what the documentation means when it says "In this case, if VALUE is a negative fixnum treat it as unsigned".
This is only true for right shifts. When shifting left, fixnums will graduate to bignums when necessary, so arithmetic and logical shifting are equivalent. The sign bit is effectively propagated infinitely in the high-order direction.