14.2: Bit Shifting Is Multiplying by 2 Powers

Last updated
Save as PDF

Page ID: 43744

\( \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}}\)

Since integers are represented as sequences of bits, if we shift all the bits from a given amount we obtain another integer. Shifting bits is equivalent to performing a multiplication/division by two. Figure \(\PageIndex{1}\) illustrates this point. Smalltalk offers three messages to shift bits: >> aPositiveInteger, << aPositiveInteger and bitShift: anInteger. >> divides the receiver, while << multiply it by a power of two.

The following examples show how to use them.

2r000001000
        → 8
2r000001000 >> 1    "we divide by two"
        → 4
(2r000001000 >> 1) printStringBase: 2
        → '100'
2r000001000 << 1    "we multiply by two"
        → 16

The message bitShift: is equivalent to >> and <<, but it uses negative and positive integers to indicate the shift direction. A positive argument offers the same behavior as <<, multiplying the receiver by a power of 2. A negative is similar to >>.

Multiply and divide by 2. — Figure \(\PageIndex{1}\): Multiplying and dividing by 2.

2r000001000
    → 8
2r000001000 bitShift: -1
    → 4
2r000001000 bitShift: 1
    → 16

Of course, we can shift by more than one bit at a time.

2r000001000
    → 8
2r000001000 >> 2    "we divide by four"
    → 2
(2r000001000 >> 2) printStringBase: 2
    → '10'
2r000001000 << 2    "we multiply by four"
    → 32

The previous examples only show bit shifting numbers with one or two bits, but there is no constraint at this level. The complete sequence of bits can be shifted as shown with 2r000001100 below and Figure \(\PageIndex{2}\).

(2 raisedTo: 8) + (2 raisedTo: 10)
    → 1280
2r010100000000
    → 1280
2r010100000000 >> 8
    → 5

Move 8 times to the right to get 5. — Figure \(\PageIndex{2}\): We move 8 times to the right. So from 1280, we get 5.

So far, there is nothing really special. Though you should have learned this in a basic math lectures, it is always good to walk on a hill before climbing a mountain.