14.3: Bit Manipulation and Access

Last updated
Save as PDF

Page ID: 43745

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Pharo offers common boolean operations for bit manipulation. Hence you can send the messages bitAnd:, bitOr:, and bitXor: to numbers. They will apply bit by bit the associated Boolean operation.

2r000001101 bitAnd: 2r01
    → 1
2r000001100 bitAnd: 2r01
    → 0
2r000001101 bitAnd: 2r1111
    → 1101

bitAnd: can then be used to select part of a number. For example, bitAnd: 2 r111 selects the three first bits.

2r000001101 bitAnd: 2r111
    → 5
2r000001101 bitAnd: 2r0
    → 0
2r0001001101 bitAnd: 2r1111
    → 13             "1101"
2r000001101 bitAnd: 2r111000
    → 8              "1000"
2r000101101 bitAnd: 2r111000
    → 40             "101000"

Using bitAnd: combined with a bitShift: we can select part of a number. Imagine that we encode three numbers on 10 bits: let’s say one number encoded on 3 bits (a number between 0 and 7 — noted as XXX in ZZZYYYYXXX), one number encoded on 4 bits (0 to 15 — noted as YYYY in ZZZYYYYXXX), and finally the third one is encoded on 3 bits noted as ZZZ in ZZZYYYYXXX. The following expressions are handy to manipulate these three numbers. Accessing the second number cannot simply be done using only bitShift: because we will still have the third number present. We get (2r1001111001 bitShift: -3) returns 79, while we would like to get 15. The solution is either to use a bitAnd: to clear the third number and to do a bitShift: or to do a bitShift: and to clear the third number. The bitAnd: argument has to be adapted to select the right part of the encoding.

(2r1001111001 bitShift: -3)
    → 79
(2r1001111001 bitAnd: 2r0001111000)
    → 120
(2r1001111001 bitAnd: 2r0001111000) bitShift: -3
    → 15
(2r1001111001 bitShift: -3) bitAnd: 2r0001111
    → 15

Bit access. Smalltalk lets you access bit information. The message bitAt: returns the value of the bit at a given position. It follows the Pharo convention that collection indexes start at one.

2r000001101 bitAt: 1
    → 1
2r000001101 bitAt: 2
    → 0
2r000001101 bitAt: 3
    → 1
2r000001101 bitAt: 4
    → 1
2r000001101 bitAt: 5
    → 0

With Pharo you can access the full environment and learn from the system itself. Here is the implementation of the method bitAt: on the Integer class.

Integer>>bitAt: anInteger
    "Answer 1 if the bit at position anInteger is set to 1, 0 otherwise.
    self is considered an infinite sequence of bits, so anInteger can be any strictly positive
        integer.
    Bit at position 1 is the least significant bit.
    Negative numbers are in two-complements.

    This is a naive implementation that can be refined in subclass for speed"
    
    ^ (self bitShift: 1 - anInteger) bitAnd: 1

We shift to the right from an integer minus one (hence 1 - anInteger) and with a bitAnd: we know whether there is a one or zero in the location. Imagine that we have 2r000001101, when we do 2r000001101 bitAt: 5 we will shift it from 4 and doing a bitAnd: 1 with select that bits (i.e., returns 1 if it was at 1 and zero otherwise, so its value). Doing a bitAnd: 1 is equivalent to tell whether there is a 1 in the least significant bit.

Again, nothing really special here, but this was to refresh our memories. Now we will see how numbers are internally encoded in Pharo using 2’s complement. We will start by understanding the 10’s complement and look at 2’s complement.