Two's complement representation and Common Lisp

[Spiros Bousbouras]

Several pages in CLHS say that certain functions behave as if integers
are in "two's-complement binary representation". Such pages are for
LOGCOUNT , LOGTEST , ASH and more.

Since integers in Common Lisp do not have a fixed width , I don't know
what two's-complement representation means. For example which number is
represented by the bit pattern 1000 0000 0000 0001 ? If I know that
integers have width of 16 bits then the number is -(2^15) + 1 = -32767 .
If they have width greater than 16 bits then it's 2^15 + 1 = 32769 .
In Common Lisp I don't know.

[Ben Bacarisse]

Post by Spiros Bousbouras
Several pages in CLHS say that certain functions behave as if integers
are in "two's-complement binary representation". Such pages are for
LOGCOUNT , LOGTEST , ASH and more.
Since integers in Common Lisp do not have a fixed width , I don't know
what two's-complement representation means. For example which number is
represented by the bit pattern 1000 0000 0000 0001 ? If I know that
integers have width of 16 bits then the number is -(2^15) + 1 = -32767 .
If they have width greater than 16 bits then it's 2^15 + 1 = 32769 .
In Common Lisp I don't know.

Common Lisp behaves as if the numbers are in two's-complement with a
sign bit "at infinity". I.e.

(logtest (ash 1 n) -1)

is T for all n. Hence all bit patterns without infinite leading 1s are
positive so 1000 0000 0000 0001 means

(+ (ash 1 15) 1)

or, as you suggest, 32769.

[Kaz Kylheku]

Post by Spiros Bousbouras
Several pages in CLHS say that certain functions behave as if integers
are in "two's-complement binary representation". Such pages are for
LOGCOUNT , LOGTEST , ASH and more.
Since integers in Common Lisp do not have a fixed width , I don't know
what two's-complement representation means.

It means "infinite two's complement". This means that:

1 behaves as an infinite sequence of 0 bits followed by 1:

..000000001

-1 bhaves as an infinite sequence of 1's:

11111111111

the two's complement sign bit is "out at infinity".

In other words, when we access the bits of an integer, no matter how
far we access into the integer (quite likely within some system-specific
bignum limit, of course), that accessing operation will sign-extend the
integer for us up to at least that length.

Post by Spiros Bousbouras
For example which number is
represented by the bit pattern 1000 0000 0000 0001 ? If I know that
integers have width of 16 bits then the number is -(2^15) + 1 = -32767 .
If they have width greater than 16 bits then it's 2^15 + 1 = 32769 .
In Common Lisp I don't know.

Since the bit pattern doesn't have an infinite stream of 1's on the
left, but is actually 0000 0000 ... 0000 1000 0000 0000 0001, we know
that it is the 32769 positive value.

You can verify this notationally with #b:

#b1000000000000001 -> 32769

[Kaz Kylheku]

Post by Kaz Kylheku

Post by Spiros Bousbouras
Several pages in CLHS say that certain functions behave as if integers
are in "two's-complement binary representation". Such pages are for
LOGCOUNT , LOGTEST , ASH and more.
Since integers in Common Lisp do not have a fixed width , I don't know
what two's-complement representation means.

..000000001
11111111111
the two's complement sign bit is "out at infinity".

Errata: I had intended: ...000000001 and ...111111111.

[Pascal J. Bourguignon]

Post by Spiros Bousbouras
Several pages in CLHS say that certain functions behave as if integers
are in "two's-complement binary representation". Such pages are for
LOGCOUNT , LOGTEST , ASH and more.
Since integers in Common Lisp do not have a fixed width , I don't know
what two's-complement representation means. For example which number is
represented by the bit pattern 1000 0000 0000 0001 ? If I know that
integers have width of 16 bits then the number is -(2^15) + 1 = -32767 .
If they have width greater than 16 bits then it's 2^15 + 1 = 32769 .
In Common Lisp I don't know.

Mathematically, the two-complement representation is:

x<0 => TC(x) = B(~(-x)+1)[0/1,1/0]
x>=0 => TC(x) = B(x)

with B being the binary representation of n ∈ ℕ with an infinite number
of prefix 0. (And x[0/1,1/0] being the substitution in the sequence x
of 0 by 1 and 1 by 0).


Now this ~ operation (logical not) is defined in C, and it works on
fixed word size, so it's well defined (it's a bijection on [0..2^n-1]).

But in ℕ, there is actually no such number for ~1 (…11110). However, we
can establish a bijection between ~ℕ and -ℕ (just define ~n = -n, with
B(-n) = B(n)[0/1,1/0]. This is 1-complement. The problem
with 1-complement being that B(0) ≠ B(-0) while 0 = -0.

Therefore we use infinite 2-complement, adding one, and restoring ITC(0)=ITC(-0).

x<0 => ITC(x) = B(~(-x)+1)[0/1,1/0]
x>=0 => ITC(x) = B(x)

ie. no difference between TC and ITC, just in the definition of ~x.