[Pharo-project] how can I get bit representation of numbers
Hi guys I thought that printStringBase: 2 would do the trick but it only works for positive number. I would like to see the two complement representation of numbers. So I implemented something like that but I wonder if this is correct. | v | v := 10. String streamContents: [:s | 31 to: 1 by: -1 do: [:i | s nextPut: ((v bitAt: i) + 48) asCharacter ] . s contents] Integer readFrom: '0000000000000000000000000001010' base: 2 | v | v := -3. "1111111111101" String streamContents: [:s | 31 to: 1 by: -1 do: [:i | s nextPut: ((v bitAt: i) + 48) asCharacter ] . s contents ] '1111111111111111111111111111101' Now Integer readFrom: '11111111111111111111111111111101' base: 2 does not hold back -3 Stef
On 04 Jul 2011, at 20:16, Stéphane Ducasse wrote:
I would like to see the two complement representation of numbers.
This is what I do, for reading/writing unsigned or two complement signed integer from/to byte streams. Note that two complement is only defined for a specific number size, 8, 16, 32 bits. unsignedToSigned: integer size: size ^ integer < (2 raisedTo: size - 1) ifTrue: [ integer ] ifFalse: [ (self twoComplement: integer size: size) negated ] signedToUnsigned: integer size: size ^ integer negative ifTrue: [ self twoComplement: integer size: size ] ifFalse: [ integer ] twoComplement: integer size: size | mask | mask := (2 raisedTo: size) - 1. ^ mask bitAnd: ((integer abs bitXor: mask) + 1) These are also very handy in this context (I believe I once submitted that as an issue): integerFromByteArray: bytes | integer | integer := 0. bytes withIndexDo: [ :each :index | integer := integer + (each bitShift: (bytes size - index) * 8) ]. ^ integer and Integer>>#asByteArrayOfSize: Once you have a byte representation, you can render it as bits as well. Sven
Sven do your code work with Smalltalk smallInteger? Because I think that in that case you should have 31 bits?
I would like to see the two complement representation of numbers.
This is what I do, for reading/writing unsigned or two complement signed integer from/to byte streams.
Note that two complement is only defined for a specific number size, 8, 16, 32 bits.
unsignedToSigned: integer size: size ^ integer < (2 raisedTo: size - 1) ifTrue: [ integer ] ifFalse: [ (self twoComplement: integer size: size) negated ]
signedToUnsigned: integer size: size ^ integer negative ifTrue: [ self twoComplement: integer size: size ] ifFalse: [ integer ]
twoComplement: integer size: size | mask | mask := (2 raisedTo: size) - 1. ^ mask bitAnd: ((integer abs bitXor: mask) + 1)
These are also very handy in this context (I believe I once submitted that as an issue):
integerFromByteArray: bytes | integer | integer := 0. bytes withIndexDo: [ :each :index | integer := integer + (each bitShift: (bytes size - index) * 8) ]. ^ integer
and Integer>>#asByteArrayOfSize:
Once you have a byte representation, you can render it as bits as well.
Sven
Two's complement is a platform representation of integers not (necessarily) a smalltalk one. The concept of negative numbers has nothing to do with the radix a number is expressed in. There are convenient extensions to the ByteArray protocol added by FFI which allow easy conversion though. I don't have time this second to list them, but will do so in a few hours. On Jul 4, 2011, at 15:14 , Stéphane Ducasse wrote:
Sven do your code work with Smalltalk smallInteger? Because I think that in that case you should have 31 bits?
I would like to see the two complement representation of numbers.
This is what I do, for reading/writing unsigned or two complement signed integer from/to byte streams.
Note that two complement is only defined for a specific number size, 8, 16, 32 bits.
unsignedToSigned: integer size: size ^ integer < (2 raisedTo: size - 1) ifTrue: [ integer ] ifFalse: [ (self twoComplement: integer size: size) negated ]
signedToUnsigned: integer size: size ^ integer negative ifTrue: [ self twoComplement: integer size: size ] ifFalse: [ integer ]
twoComplement: integer size: size | mask | mask := (2 raisedTo: size) - 1. ^ mask bitAnd: ((integer abs bitXor: mask) + 1)
These are also very handy in this context (I believe I once submitted that as an issue):
integerFromByteArray: bytes | integer | integer := 0. bytes withIndexDo: [ :each :index | integer := integer + (each bitShift: (bytes size - index) * 8) ]. ^ integer
and Integer>>#asByteArrayOfSize:
Once you have a byte representation, you can render it as bits as well.
Sven
2011/7/5 Douglas McPherson <djm1329@san.rr.com>:
Two's complement is a platform representation of integers not (necessarily) a smalltalk one. The concept of negative numbers has nothing to do with the radix a number is expressed in.
There are convenient extensions to the ByteArray protocol added by FFI which allow easy conversion though. I don't have time this second to list them, but will do so in a few hours.
That's true, but the internal implementation leaks out the bitAnd: bitOr: and other bit operations... Nicolas
On Jul 4, 2011, at 15:14 , Stéphane Ducasse wrote:
Sven do your code work with Smalltalk smallInteger? Because I think that in that case you should have 31 bits?
I would like to see the two complement representation of numbers.
This is what I do, for reading/writing unsigned or two complement signed integer from/to byte streams.
Note that two complement is only defined for a specific number size, 8, 16, 32 bits.
unsignedToSigned: integer size: size    ^ integer < (2 raisedTo: size - 1)        ifTrue: [ integer ]        ifFalse: [ (self twoComplement: integer size: size) negated ]
signedToUnsigned: integer size: size    ^ integer negative        ifTrue: [ self twoComplement: integer size: size ]        ifFalse: [ integer ]
twoComplement: integer size: size    | mask |    mask := (2 raisedTo: size) - 1.    ^ mask bitAnd: ((integer abs bitXor: mask) + 1)
These are also very handy in this context (I believe I once submitted that as an issue):
integerFromByteArray: bytes    | integer |    integer := 0.    bytes withIndexDo: [ :each :index |        integer := integer + (each bitShift: (bytes size - index) * 8) ].    ^ integer
and Integer>>#asByteArrayOfSize:
Once you have a byte representation, you can render it as bits as well.
Sven
What I'm looking for is a way to explain/understand simply how SmallInteger are implemented.
Two's complement is a platform representation of integers not (necessarily) a smalltalk one. The concept of negative numbers has nothing to do with the radix a number is expressed in.
Yes I learned that
There are convenient extensions to the ByteArray protocol added by FFI which allow easy conversion though. I don't have time this second to list them, but will do so in a few hours.
That's true, but the internal implementation leaks out the bitAnd: bitOr: and other bit operations...
I want to explain two's complement then Smalltalk smallinteger \section{Two's complement of a number} .... Creating a two complement version of a number equals negating the number bits and adding one. \begin{code}{Calculating two complement of 3} 3 bitString '0000000000000000000000000000011' 3 bitInvert bitString '1111111111111111111111111111100' (3 bitInvert + 1) bitString '1111111111111111111111111111101' -3 bitString '1111111111111111111111111111101' \end{code} .... \section{SmallIntegers in Smalltalk} Smalltalk small integers uses a two's complement arithmetic on 31 bits. An N-bit two's-complement numeral system can represent every integer in the range $-1 * 2^{N-1}\ to\ 2^{N-1}-1$. So for 32 bits Smalltalk systems, small integers values are the range -1073741824 to 1073741823. Let's check that a bit (this is the occasion to say it). \begin{code}{} 2 raisedTo: 29 returns 536870912 536870912 class returns SmallInteger 2 raisedTo: 30 returns 1073741824 1073741824 class returns LargePositiveInteger -1073741824 class returns SmallInteger 2 class maxVal returns 1073741823 -1 * (2 raisedTo: (31-1)) returns -1073741824 (2 raisedTo: 30) - 1 returns 1073741823
On Jul 5, 2011, at 12:26 AM, Nicolas Cellier wrote:
2011/7/5 Douglas McPherson <djm1329@san.rr.com>:
Two's complement is a platform representation of integers not (necessarily) a smalltalk one. The concept of negative numbers has nothing to do with the radix a number is expressed in.
There are convenient extensions to the ByteArray protocol added by FFI which allow easy conversion though. I don't have time this second to list them, but will do so in a few hours.
That's true, but the internal implementation leaks out the bitAnd: bitOr: and other bit operations...
what do you mean by this sentence? That using bitAnd: we can get an idea of the implementation? exactly :)
Nicolas
On Jul 4, 2011, at 15:14 , Stéphane Ducasse wrote:
Sven do your code work with Smalltalk smallInteger? Because I think that in that case you should have 31 bits?
I would like to see the two complement representation of numbers.
This is what I do, for reading/writing unsigned or two complement signed integer from/to byte streams.
Note that two complement is only defined for a specific number size, 8, 16, 32 bits.
unsignedToSigned: integer size: size ^ integer < (2 raisedTo: size - 1) ifTrue: [ integer ] ifFalse: [ (self twoComplement: integer size: size) negated ]
signedToUnsigned: integer size: size ^ integer negative ifTrue: [ self twoComplement: integer size: size ] ifFalse: [ integer ]
twoComplement: integer size: size | mask | mask := (2 raisedTo: size) - 1. ^ mask bitAnd: ((integer abs bitXor: mask) + 1)
These are also very handy in this context (I believe I once submitted that as an issue):
integerFromByteArray: bytes | integer | integer := 0. bytes withIndexDo: [ :each :index | integer := integer + (each bitShift: (bytes size - index) * 8) ]. ^ integer
and Integer>>#asByteArrayOfSize:
Once you have a byte representation, you can render it as bits as well.
Sven
Am 05.07.2011 00:26, schrieb Nicolas Cellier:
2011/7/5 Douglas McPherson <djm1329@san.rr.com>:
Two's complement is a platform representation of integers not (necessarily) a smalltalk one. The concept of negative numbers has nothing to do with the radix a number is expressed in.
There are convenient extensions to the ByteArray protocol added by FFI which allow easy conversion though. I don't have time this second to list them, but will do so in a few hours.
That's true, but the internal implementation leaks out the bitAnd: bitOr: and other bit operations...
Nicolas
On Jul 4, 2011, at 15:14 , Stéphane Ducasse wrote:
Sven do your code work with Smalltalk smallInteger? Because I think that in that case you should have 31 bits?
I would like to see the two complement representation of numbers. This is what I do, for reading/writing unsigned or two complement signed integer from/to byte streams.
Note that two complement is only defined for a specific number size, 8, 16, 32 bits.
unsignedToSigned: integer size: size ^ integer < (2 raisedTo: size - 1) ifTrue: [ integer ] ifFalse: [ (self twoComplement: integer size: size) negated ]
signedToUnsigned: integer size: size ^ integer negative ifTrue: [ self twoComplement: integer size: size ] ifFalse: [ integer ]
twoComplement: integer size: size | mask | mask := (2 raisedTo: size) - 1. ^ mask bitAnd: ((integer abs bitXor: mask) + 1)
These are also very handy in this context (I believe I once submitted that as an issue):
integerFromByteArray: bytes | integer | integer := 0. bytes withIndexDo: [ :each :index | integer := integer + (each bitShift: (bytes size - index) * 8) ]. ^ integer
and Integer>>#asByteArrayOfSize:
Once you have a byte representation, you can render it as bits as well.
Sven
Sorry for breaking into the thread.
A very good hint to get the picture of Integer representation in the twos complement is the "Zahlenkreis". I always use the "Zahlenkreis" if I have to explain someone the twos complement representation of fixed point numbers. See for instance ti.uni-due.de/vs/de/education/Dv1/vorlesung2006/Folie-Zahlenkreis.pdf for a transparency. (That given link is not a special choice for any reason and I will not be paied for - you find many links with the search topic "Zahlenkreis".) I found a french translation: représentation circulaire. I think it is called fixed-point circle in english: http://www.mathworks.com/products/fixed/demos.html?file=/products/demos/ship... The Large Integers obviously are represented symmetric with a leading sign bit. (SmallInteger maxVal +1) printStringBase: 2 '1000000000000000000000000000000' It is astonisching that the smallest LargePositiveInteger has 30 0`s? (SmallInteger maxVal +2) printStringBase: 2 '1000000000000000000000000000001' (SmallInteger maxVal +1) negated printStringBase: 2 '-1000000000000000000000000000000' (SmallInteger maxVal +2) negated printStringBase: 2 '1000000000000000000000000000001' (SmallInteger maxVal raisedTo: 10) printStringBase: 2 '111111111111111111111111110110000000000000000000000000101100111111111111111111111110001000000000000000000000000011010001111111111111111111111100000100000000000000000000000011010001111111111111111111111110001000000000000000000000000000101100111111111111111111111111110110000000000000000000000000000001' (SmallInteger maxVal raisedTo: 10) negated printStringBase: 2 '-111111111111111111111111110110000000000000000000000000101100111111111111111111111110001000000000000000000000000011010001111111111111111111111100000100000000000000000000000011010001111111111111111111111110001000000000000000000000000000101100111111111111111111111111110110000000000000000000000000000001' An interesting topic! Regards BB
For positive integers, we have an infinite serie of 0 bits, but we don't care, we just don't print them. The problem with two complement is that you have an infinite serie of leading 1 bits... Otherwise, you can access the bit at any rank with bitAt: For example, you could use bitRepresentation ^(self digitLength * 8 + 1 to: 1 by: -1) collect: [:i | Character value: $0 charCode + (self bitAt: i)] as: String The first bit will aways be the sign with the + 1 trick. Nicolas 2011/7/4 Sven Van Caekenberghe <sven@beta9.be>:
On 04 Jul 2011, at 20:16, Stéphane Ducasse wrote:
I would like to see the two complement representation of numbers.
This is what I do, for reading/writing unsigned or two complement signed integer from/to byte streams.
Note that two complement is only defined for a specific number size, 8, 16, 32 bits.
unsignedToSigned: integer size: size     ^ integer < (2 raisedTo: size - 1)         ifTrue: [ integer ]         ifFalse: [ (self twoComplement: integer size: size) negated ]
signedToUnsigned: integer size: size     ^ integer negative         ifTrue: [ self twoComplement: integer size: size ]         ifFalse: [ integer ]
twoComplement: integer size: size     | mask |     mask := (2 raisedTo: size) - 1.     ^ mask bitAnd: ((integer abs bitXor: mask) + 1)
These are also very handy in this context (I believe I once submitted that as an issue):
integerFromByteArray: bytes     | integer |     integer := 0.     bytes withIndexDo: [ :each :index |         integer := integer + (each bitShift: (bytes size - index) * 8) ].     ^ integer
and Integer>>#asByteArrayOfSize:
Once you have a byte representation, you can render it as bits as well.
Sven
Salut nicolas :)
For positive integers, we have an infinite serie of 0 bits, but we don't care, we just don't print them. The problem with two complement is that you have an infinite serie of leading 1 bits...
Yes :)
Otherwise, you can access the bit at any rank with bitAt: For example, you could use bitRepresentation ^(self digitLength * 8 + 1 to: 1 by: -1) collect: [:i | Character value: $0 charCode + (self bitAt: i)] as: String
Included in my question is the fact that small integer are encoded on 31 bits (may be I'm wrong) so printing 32 bits represent LargeINteger and so far I want small integetr so was my assumption correct? and what would be a good method to return bitString of a Small Integer.s 2 raisedTo: 29 returns 536870912 536870912 class returns SmallInteger 2 raisedTo: 30 returns 1073741824 1073741824 class returns LargePositiveInteger -1073741824 class returns SmallInteger 2 class maxVal returns 1073741823 -1 * (2 raisedTo: (31-1)) returns -1073741824 (2 raisedTo: 30) - 1 returns 1073741823
The first bit will aways be the sign with the + 1 trick.
Nicolas
2011/7/4 Sven Van Caekenberghe <sven@beta9.be>:
On 04 Jul 2011, at 20:16, Stéphane Ducasse wrote:
I would like to see the two complement representation of numbers.
This is what I do, for reading/writing unsigned or two complement signed integer from/to byte streams.
Note that two complement is only defined for a specific number size, 8, 16, 32 bits.
unsignedToSigned: integer size: size ^ integer < (2 raisedTo: size - 1) ifTrue: [ integer ] ifFalse: [ (self twoComplement: integer size: size) negated ]
signedToUnsigned: integer size: size ^ integer negative ifTrue: [ self twoComplement: integer size: size ] ifFalse: [ integer ]
twoComplement: integer size: size | mask | mask := (2 raisedTo: size) - 1. ^ mask bitAnd: ((integer abs bitXor: mask) + 1)
These are also very handy in this context (I believe I once submitted that as an issue):
integerFromByteArray: bytes | integer | integer := 0. bytes withIndexDo: [ :each :index | integer := integer + (each bitShift: (bytes size - index) * 8) ]. ^ integer
and Integer>>#asByteArrayOfSize:
Once you have a byte representation, you can render it as bits as well.
Sven
If you want to know the number of bits used to represent a SmallInteger, just evaluate: SmallInteger maxVal highBit + 1. SmallInteger maxVal highBit tells the highest bit which can be used to represent a positive SmallInteger, and + 1 accounts for the sign bit of the SmallInteger (0 for positive, 1 for negative). Then you can just rewrite: bitRepresentation ^(self bitRepresentationLength to: 1 by: -1) collect: [:i | Character value: $0 charCode + (self bitAt: i)] as: String Integer>>bitRepresentationLength ^self digitLength * 8 "make sure positive integer bitRepresentation always begins with 0" + (self positive ifTrue: [1] ifFalse: [0]) SmallInteger>>bitRepresentationLength "always use as many bits as the native format to represent a SmallInteger" ^self class maxVal highBit + 1 Nicolas 2011/7/5 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Salut nicolas :)
For positive integers, we have an infinite serie of 0 bits, but we don't care, we just don't print them. The problem with two complement is that you have an infinite serie of leading 1 bits...
Yes :)
Otherwise, you can access the bit at any rank with bitAt: For example, you could use bitRepresentation    ^(self digitLength * 8 + 1 to: 1 by: -1) collect: [:i | Character value: $0 charCode + (self bitAt: i)] as: String
Included in my question is the fact that small integer are encoded on 31 bits (may be I'm wrong) so printing 32 bits represent LargeINteger and so far I want small integetr so was my assumption correct? and what would be a good method to return bitString of a Small Integer.s
2 raisedTo: 29 Â Â Â Â returns 536870912
536870912 class     returns SmallInteger
2 raisedTo: 30 Â Â Â Â returns 1073741824
1073741824 class     returns LargePositiveInteger
-1073741824 class     returns SmallInteger
2 class maxVal     returns 1073741823
-1 * (2 raisedTo: (31-1)) Â Â Â Â returns -1073741824
(2 raisedTo: 30) - 1 Â Â Â Â returns 1073741823
The first bit will aways be the sign with the + 1 trick.
Nicolas
2011/7/4 Sven Van Caekenberghe <sven@beta9.be>:
On 04 Jul 2011, at 20:16, Stéphane Ducasse wrote:
I would like to see the two complement representation of numbers.
This is what I do, for reading/writing unsigned or two complement signed integer from/to byte streams.
Note that two complement is only defined for a specific number size, 8, 16, 32 bits.
unsignedToSigned: integer size: size     ^ integer < (2 raisedTo: size - 1)         ifTrue: [ integer ]         ifFalse: [ (self twoComplement: integer size: size) negated ]
signedToUnsigned: integer size: size     ^ integer negative         ifTrue: [ self twoComplement: integer size: size ]         ifFalse: [ integer ]
twoComplement: integer size: size     | mask |     mask := (2 raisedTo: size) - 1.     ^ mask bitAnd: ((integer abs bitXor: mask) + 1)
These are also very handy in this context (I believe I once submitted that as an issue):
integerFromByteArray: bytes     | integer |     integer := 0.     bytes withIndexDo: [ :each :index |         integer := integer + (each bitShift: (bytes size - index) * 8) ].     ^ integer
and Integer>>#asByteArrayOfSize:
Once you have a byte representation, you can render it as bits as well.
Sven
participants (6)
-
bb -
Douglas McPherson -
Nicolas Cellier -
Stéphane Ducasse -
Stéphane Ducasse
-
Sven Van Caekenberghe