how to output a signed integer in two's-complement notation.

[Jinsong Zhao]

Hi there,

I could use (format t "~B" 3) to get the binary representation of 3,
however there is no bit to represent its sign.

If I use (format t "~B" -3), I get -11. However, I hope to get the
two's-complement notation of -3, that is 101 (am I right?).

Because I don't familiar with the bitwise operation. I hope to learn it
by writing out the binary representation of integer.

Another related question is how to understand byte specifiers? For
example, how to interpret the result of (byte 2 1) or (byte 0 3)?

Thanks a lot.

Best,
Jinsong

[Spiros Bousbouras]

On Wed, 16 Nov 2022 17:54:01 +0800
Jinsong Zhao <jsz...@yeah.net> wrote:
> Hi there,
>
> I could use (format t "~B" 3) to get the binary representation of 3,
> however there is no bit to represent its sign.
>
> If I use (format t "~B" -3), I get -11. However, I hope to get the
> two's-complement notation of -3, that is 101 (am I right?).
>
> Because I don't familiar with the bitwise operation. I hope to learn it
> by writing out the binary representation of integer.

Not a direct response to your question but you may find the following
thread useful :

Newsgroups: comp.lang.lisp
Subject: Two's complement representation and Common Lisp
Message-ID: <cef5Qn4x4ec89N4...@bongo-ra.co>
NNTP-Posting-Date: Wed, 19 Jul 2017 20:47:28 UTC

The other message IDs of the thread are
<87fuds7...@bsb.me.uk>
<201707191...@kylheku.com>
<201707191...@kylheku.com>
<m2r2xb2...@despina.home>

[Jeff Barnett]

The 2s complement of -3 is not, in general, 101; Rather, it is ...101,
where the number of leading dots representing 1s depend on word size or
precision, etc. For example, -3 as an 8 bit 2s complement number is
11111101. You must specify precision to know how to represent a 2s
complement number.
--
Jeff Barnett

[Tom Russ]

On Wednesday, November 16, 2022 at 11:06:58 AM UTC-8, Jeff Barnett wrote:
> On 11/16/2022 2:54 AM, Jinsong Zhao wrote:
> > Hi there,
> >
> > I could use (format t "~B" 3) to get the binary representation of 3,
> > however there is no bit to represent its sign.
> >
> > If I use (format t "~B" -3), I get -11. However, I hope to get the
> > two's-complement notation of -3, that is 101 (am I right?).
> >
> > Because I don't familiar with the bitwise operation. I hope to learn it
> > by writing out the binary representation of integer.
> >
> > Another related question is how to understand byte specifiers? For
> > example, how to interpret the result of (byte 2 1) or (byte 0 3)?

Bytes were not always 8 bits in size. To deal with that variability the
byte accessors in Common Lisp have both a byte-size and a position
argument.
So (byte 2 1) is a 2-bit byte starting at 2^position.
The form (byte 0 3) is legal but the byte has size 0, so it may not
be that useful.
Details: http://www.lispworks.com/documentation/HyperSpec/Body/f_by_by.htm

> >
> > Thanks a lot.
> The 2s complement of -3 is not, in general, 101; Rather, it is ...101,
> where the number of leading dots representing 1s depend on word size or
> precision, etc. For example, -3 as an 8 bit 2s complement number is
> 11111101. You must specify precision to know how to represent a 2s
> complement number.

You would need to write your own conversion. There is actually no requirement
in Common Lisp that two's complement be used for integers. And, in fact, it would
be impossible to have a true (or at least naive) two's complement internal
representation for bignums.

You could generate a two's complement for negative numbers of size N
with the formula:
(defun twos-complement (value n-digits)
(if (>= value 0) value (- (expt 2 n-digits) value 1)))

You could then do this formatted by wrapping it with
(defun twos-complement-string (value n-digits)
(format nil "~v,'0B" (1+ n-digits) (twos-complement value n-digits)))

where value is the regular integer value and n-digits is the number of
non-sign binary digits in the representation.

[Kaz Kylheku]

On 2022-11-16, Jinsong Zhao <jsz...@yeah.net> wrote:
> Hi there,
>
> I could use (format t "~B" 3) to get the binary representation of 3,
> however there is no bit to represent its sign.
>
> If I use (format t "~B" -3), I get -11. However, I hope to get the
> two's-complement notation of -3, that is 101 (am I right?).

That is false. The two's complement notation requires you to be
specific about how many bits you want. These are all two's complement
representations of -3:

101 (3 bits)
1101 (4 bits)
11101 (5 bits)
...

There exists the concept of "infinite bit two's complement", in which
-3 is represented by:

...11101 (infinite number of 1's followed by 01).

In an abstract sense, Lisp integers operate in this representation;
but you can't print that!

This infinite two's complement abstraction is your dear friend if
you want to print a negative number in some two's complement bit
with, because all you have to do is truncate it:

For instance:

[1]> (format t "~b~%" (logand 255 -3))
11111101
NIL

There you have -3 in eight-bit, two's complement. This works by bitwise
AND-ing these two numbers:

......1111111111101
AND ......0000011111111
-------------------
= ,.....0000011111101

= 11111101

> Because I don't familiar with the bitwise operation. I hope to learn it
> by writing out the binary representation of integer.
>
> Another related question is how to understand byte specifiers? For
> example, how to interpret the result of (byte 2 1) or (byte 0 3)?

Those can help us, too:

[2]> (format t "~b~%" (ldb (byte 8 0) -3))
11111101
NIL

I.e. Extract the "byte" formed by bits [0, 8) of the infinite two's
complement number ..111111111111101.

[Spiros Bousbouras]

This prints wrong results. For example

* (twos-complement-string -1 7)
"10000000"

whereas the number printed actually represents -128 in two's complement
with 7 value bits.

The following works better

(defun twos-complement-repr (value n-value-digits
&aux (po2 (expt 2 n-value-digits)))
"n-value-digits must be positive"
(cond ((eql 0 value) (format nil "~v,'0B" (1+ n-value-digits) 0))
((< 0 value) (when (< (1- po2) value)
(error "~a binary digits are not enough to represent ~
value ~a~%" n-value-digits value))
(format nil "0~v,'0B" n-value-digits value))
(t (when (< value (- po2))
(error "~a binary digits are not enough to represent ~
value ~a~%" n-value-digits value))
(format nil "1~v,'0B" n-value-digits (+ po2 value)))))

--
If you like flashbacks then this has plenty of them. Each of them perfectly
placed to add nothing at all to what I guess the director hoped was a story.
Would have given 2 stars, but only if they hadn't made the film.
www.imdb.com/review/rw3224889/

[Kaz Kylheku]

Here is TXR Lisp, which doesn't have good numeric processing compared to
Common Lisp. Yet, from time to time you may find there are some nice
things about it:

(defun twos-comp-repr (n bits)
(if (>= (width n) bits)
(error "~s: ~s bits is not enough for ~s" %fun% bits n)
(fmt "~0,0*b" bits (logtrunc n bits))))

The width function returns how many bits of mantissa (i.e. not counting
the sign bit) is required for the given integer, taken as two's
complement. For instance (wdith -3) is 2. The smallest two's complement
prepresentation of -3 is 101, and if we take the sign bit away, we have
two bits.

The logtrunc function truncates to the specified number of bits.

So with those, the function becomes trivial to write.

Tests:

1> (twos-comp-repr -127 8)
"10000001"
2> (twos-comp-repr -128 8)
"10000000"
3> (twos-comp-repr -1 8)
"11111111"
4> (twos-comp-repr 0 8)
"00000000"
5> (twos-comp-repr 17 8)
"00010001"
6> (twos-comp-repr 127 8)
"01111111"
7> (twos-comp-repr 128 8)
** twos-comp-repr: 8 bits is not enough for 128
** during evaluation of form (error ":~s ~s bits is not enough for ~s"
'twos-comp-repr
bits n)
** ... an expansion of (error ":~s ~s bits is not enough for ~s"
%fun% bits
n)
** which is located at twos-comp-repr.tl:3
7> (twos-comp-repr -129 8)
** twos-comp-repr: 8 bits is not enough for -129
** during evaluation of form (error ":~s ~s bits is not enough for ~s"
'twos-comp-repr
bits n)
** ... an expansion of (error ":~s ~s bits is not enough for ~s"
%fun% bits
n)
** which is located at twos-comp-repr.tl:3

%fun% is a new feature I introduced in the last release; it is a symbol
macro which expands to the current function name, or else nil in a top
level. It doesn't see inner functions, which is useful; you often want
them to be helpers to report errors against the parent.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[Jinsong Zhao]

Thanks for the detailed reply. The purpose that I hope to output the
two's-complement notation is to use them to understand logand and its
many friends.

>> Because I don't familiar with the bitwise operation. I hope to learn it
>> by writing out the binary representation of integer.
>>
>> Another related question is how to understand byte specifiers? For
>> example, how to interpret the result of (byte 2 1) or (byte 0 3)?
>
> Those can help us, too:
>
> [2]> (format t "~b~%" (ldb (byte 8 0) -3))
> 11111101
> NIL
>
> I.e. Extract the "byte" formed by bits [0, 8) of the infinite two's
> complement number ..111111111111101.

Thanks for the example. After the above detailed reply and example. Now
I could understand what's the byte specifiers.

Best,
Jinsong

[Spiros Bousbouras]

Simpler is

(defun twos-complement-repr2 (value n-value-digits

&aux (po2 (expt 2 n-value-digits)))
"n-value-digits must be positive"

(cond ((<= 0 value) (when (<= po2 value)

[Spiros Bousbouras]

I assume it also increases the number of bits rather than truncate.

>
> So with those, the function becomes trivial to write.
>
> Tests:

[...]

> 7> (twos-comp-repr 128 8)
> ** twos-comp-repr: 8 bits is not enough for 128
> ** during evaluation of form (error ":~s ~s bits is not enough for ~s"
> 'twos-comp-repr
> bits n)
> ** ... an expansion of (error ":~s ~s bits is not enough for ~s"
> %fun% bits
> n)
> ** which is located at twos-comp-repr.tl:3
> 7> (twos-comp-repr -129 8)
> ** twos-comp-repr: 8 bits is not enough for -129
> ** during evaluation of form (error ":~s ~s bits is not enough for ~s"
> 'twos-comp-repr
> bits n)
> ** ... an expansion of (error ":~s ~s bits is not enough for ~s"
> %fun% bits
> n)
> ** which is located at twos-comp-repr.tl:3
>
> %fun% is a new feature I introduced in the last release; it is a symbol
> macro which expands to the current function name, or else nil in a top
> level. It doesn't see inner functions, which is useful; you often want
> them to be helpers to report errors against the parent.

%fun% seems useful. But it also depends on what the debugger does. In
SBCL , if you have compiled with appropriately high level of debugging ,
it can print the whole stacktrace and the source code which threw you
in the debugger. But for any code serious enough , I still like to add
in my error messages the name of function or macro which signalled the
condition.

--
I have put on record elsewhere my altercation with Edward Heath in 1966 when I
assured him that the Americans would lose the Vietnam War and be expelled from
South-East Asia, only to be told by him, puce with anger, that an ex-staff officer
ought to know better than talk such nonsense
http://archive.spectator.co.uk/article/28th-october-1978/23/what-lessons

[Spiros Bousbouras]

On Wed, 16 Nov 2022 17:54:01 +0800
Jinsong Zhao <jsz...@yeah.net> wrote:

[...]

> Another related question is how to understand byte specifiers? For
> example, how to interpret the result of (byte 2 1) or (byte 0 3)?

Byte specifiers are some implementation defined object so they are best
understood in connection with code. The function encode-3-octets below
takes as argument 3 octets and returns a string with 4 characters which is
the BASE64 encoding of the octets as defined in RFC 2045.


(defconstant base64-alphabet
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
"See RFC 2045.
For simplicity , I have written the characters explicitly as opposed
to their ASCII values which is what should be transmittied over the
wire. For most or all Common Lisp implementations , it would make no
difference."
)

(declaim (ftype (function ((unsigned-byte 8) (unsigned-byte 8) (unsigned-byte 8))
string)
encode-3-octets))

(defun encode-3-octets (a b c &aux (i 0)
(res (make-array 4 :element-type 'character)))
(declare (type (unsigned-byte 6) i))
(setf (aref res 0) (aref base64-alphabet (ldb (byte 6 2) a)))
(setq i (dpb (ldb (byte 2 0) a) (byte 2 4) 0))
(setq i (dpb (ldb (byte 4 4) b) (byte 4 0) i))
(setf (aref res 1) (aref base64-alphabet i))
(setq i (dpb (ldb (byte 4 0) b) (byte 4 2) 0))
(setq i (dpb (ldb (byte 2 6) c) (byte 2 0) i))
(setf (aref res 2) (aref base64-alphabet i))
(setf (aref res 3) (aref base64-alphabet (ldb (byte 6 0) c)))
res
)

--
Q: What sound does a drowning analytic number theorist make?
A: log log log log . . .
R. Murty

[anti...@math.uni.wroc.pl]

Tom Russ <tar...@google.com> wrote:
>
> There is actually no requirement
> in Common Lisp that two's complement be used for integers. And, in fact, it would
> be impossible to have a true (or at least naive) two's complement internal
> representation for bignums.

AFAIK Clozure CL, Poplog clisp and sbcl use two complement representation.
Given that sbcl started with cmucl code it is resonable to guess
that also cmucl uses two complement representation. In other
words, it seem that all native code Lisp compilers use two
complement representation.

ECL and GCL use GMP for bignums and it is likely that they just
use GMP representation which is sign-magnitude.

Concerning "naive": of course bignum code must allocate sufficient
number of words to represent given number and operations must
work on multiword numbers. Two complement makes addition and
subtraction easier. For multiplication and division Poplog
(and probably other native Lisps) first converts numbers to
positive ones, does the operation and then fixes signs.
This adds some complication to code, but probably is not
measurably slower than using sign-magnitude form. OTOH
sign-maginitude complicates "simple" operations.

--
Waldek Hebisch

[Spiros Bousbouras]

On Thu, 17 Nov 2022 19:08:56 -0000 (UTC)
Spiros Bousbouras <spi...@gmail.com> wrote:
> The function encode-3-octets below
> takes as argument 3 octets and returns a string with 4 characters which is
> the BASE64 encoding of the octets as defined in RFC 2045.
>
>
> (defconstant base64-alphabet
> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
> "See RFC 2045.
> For simplicity , I have written the characters explicitly as opposed

> to their ASCII values which is what should be transmitted over the

> wire. For most or all Common Lisp implementations , it would make no
> difference."
> )
>
> (declaim (ftype (function ((unsigned-byte 8) (unsigned-byte 8) (unsigned-byte 8))
> string)
> encode-3-octets))
>
> (defun encode-3-octets (a b c &aux (i 0)
> (res (make-array 4 :element-type 'character)))
> (declare (type (unsigned-byte 6) i))
> (setf (aref res 0) (aref base64-alphabet (ldb (byte 6 2) a)))
> (setq i (dpb (ldb (byte 2 0) a) (byte 2 4) 0))
> (setq i (dpb (ldb (byte 4 4) b) (byte 4 0) i))
> (setf (aref res 1) (aref base64-alphabet i))
> (setq i (dpb (ldb (byte 4 0) b) (byte 4 2) 0))
> (setq i (dpb (ldb (byte 2 6) c) (byte 2 0) i))
> (setf (aref res 2) (aref base64-alphabet i))
> (setf (aref res 3) (aref base64-alphabet (ldb (byte 6 0) c)))
> res
> )

Here is a version which I find easier to understand :

(defun copy-bit-range (source start1 end
&optional (dest 0) (start2 0)
&aux (len (+ 1 (- end start1))))

"The function copies the bits from position start1 to end
[inclusive] of integer source to integer dest starting from
position start2 and returns the integer thus constructed."

(dpb (ldb (byte len start1) source) (byte len start2) dest))

(declaim (ftype (function ((unsigned-byte 8) (unsigned-byte 8) (unsigned-byte 8))
string)

encode-3-octets-2))

(defun encode-3-octets-2 (a b c &aux (i 0)

(res (make-array 4 :element-type 'character)))
(declare (type (unsigned-byte 6) i))

(setf (aref res 0) (aref base64-alphabet (copy-bit-range a 2 7)))
(setq i (copy-bit-range a 0 1 0 4))
(setf (aref res 1) (aref base64-alphabet (copy-bit-range b 4 7 i 0)))
(setq i (copy-bit-range b 0 3 0 2))
(setf (aref res 2) (aref base64-alphabet (copy-bit-range c 6 7 i 0)))
(setf (aref res 3) (aref base64-alphabet (copy-bit-range c 0 5)))
res
)

And if you want to test that they do the same

(defun test-function2 ()
(dotimes (i1 256)
(dotimes (i2 256)
(dotimes (i3 256)
(unless (equalp (encode-3-octets i1 i2 i3)
(encode-3-octets-2 i1 i2 i3))
(error "~A ~A ~A~%" i1 i2 i3))))))

SBCL takes 21 seconds to run test-function2 , ECL and clisp much longer.
But I didn't pay any attention to optimisation settings.

--
My university's administration tended in the past to express skepticism
about the value of this ranking, which typically put us tied for 8/9 or
8/9/10. This year however, everyone here agrees that there has been a
dramatic improvement in methodology, since we're at number 4.
http://www.math.columbia.edu/~woit/wordpress/?p=3197