Closely related to the logical operators of the previous page are the bitwise operators. But before we talk about bitwise operators, we need to talk about bits.

You may recall from the discussion of computer
numbers that computers frequently use
the binary radix.
You may recall from the discussion of data
types that computers may make a distinction between floating
point numbers and integers.
The bitwise operators are modeled on operations that binary
computers frequently allow on *words*, the fundamental type
implemented in the computer’s hardware.
These operators treat entire computer words as collections of bits
— *b*inary dig*its* — and provide
operations at the bit level.

There are two types of bitwise operators. The first is what are called shift and rotate operations. A shift operation discards some number of bits at one end of a word, shifts the remaining bits into the space thus vacated, and fills the bits vacated by the shift with zeroes. As an example, consider a ten bit quantity, and the right and left shift of this quantity by three bits:

b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}
right shift 3 → 000b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3
}b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}
left shift 3 →
b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}000

Neglecting signs, a right shift of *k* bits is equivalent to
dividing the quantity by 2* ^{k}*, and a left shift
of

This type of right shift is called a *logical shift*, or a
*zero-filled* shift.
It treats the values as unsigned quantities.
Most computers, however, deal with what is called twos complement
values: in this representation, if the leftmost bit is 1, the actual
value is 2^{m-1} less than the value expressed in the
rightmost *m*-1 bits, where *m* is the word size of the
machine.
Thus, for example, on a 32 bit machine, the value of
01111111111111111111111111111111_{2} is 2147483647, but
incrementing this value by 1 yields
10000000000000000000000000000000_{2}, which is considered to
be –2147483648.
On such a machine, a logical right shift of this value would yield
01000000000000000000000000000000_{2}, which has the value
1073741824.

In order to maintain a rough equivalence shifting right by 1 bit and
division by 2, many machines define an *arithmetic shift*, or
*sign-extended shift*.
In this variation, the fill bits in a right shift are not zeroes,
but rather copies of the original high order bit.
Thus, an arithmetic right shift of
10000000000000000000000000000000_{2} by one bit would be
11000000000000000000000000000000_{2}, or –1073741824.

A rotate operation differs by filling the bits vacated by the shift with the bits that were originally discarded. As an example, consider a ten bit quantity, right rotated by three bits:

b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}
right rotate 3 →
b_{2}b_{1}b_{0}b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3}

Rotate operations are symmetric in the sense that a right rotate
operation of *k* bits is equivalent to a left rotate operation
of *w*-*k* bits, where *w* is the word length
in bits.

Rotate operations can also be constructed out of shift operations: a
right rotate of *k* bits is equivalent to the logical or of
a right shift of *k* bits and a left shift of
*w*-*k* bits.
Consider once again the ten bit quantity:

b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}
right shift 3 →
000b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3}

b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}
left shift 7 →
b_{2}b_{1}b_{0}0000000

Logical Or of right shift 3 result and left shift 7 result: b_{2}b_{1}b_{0}b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3}

The second type of bitwise operators is combination operators.
These operators are similar to the logical operators discussed in
the previous page, but operate independently upon bits of two
quantities in similar positions.
Consider two ten bit quantities, *a* and *b*, and the
result *c* of a combination operator upon the two values:

a_{9}a_{8}a_{7}a_{6}a_{5}a_{4}a_{3}a_{2}a_{1}a_{0}
*op*
b_{9}b_{8}b_{7}b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}
→
c_{9}c_{8}c_{7}c_{6}c_{5}c_{4}c_{3}c_{2}c_{1}c_{0}

where a_{i} *op* b_{i}
→ c_{i}, where *op* is now the
corresponding logical operation and a_{i},
b_{i}, and c_{i} are logical
quantities expressed as 0 for false, and 1 for true.

Combination operators generally provided are and, or, not, and exclusive or. Other combination operators may be constructed out of these.

These operators frequently find use when a single computer word
is used to store several values, each of which is smaller than a
single computer word can hold.
This technique of *bit fields* is discussed in the section
Data Structures I.
Individual bits of a computer word can be set or cleared with the
or and and bitwise operators: oring a 1 bit sets the corresponding
bit, and anding a 0 bit clears the corresponding bit.

The JavaScript language provides bitwise shift operators and a large set of combination operators. The Visual Basic for Applications language provides combination operators, but not shift operators. The CFX-9850G calculator, too, provides combination operators, but not shift operators. The FX-7400G calculator does not provide either shift or combination operators. Also, the CFX-9850G calculator bitwise operators are available only in programs created as number base manipulation programs. The operators in the various languages are given in the following table.

Operator |
JavaScript symbol |
VBA symbol |
Calculator symbol |
---|---|---|---|

Left shift |
<< |
(none) |
(none) |

Right shift, sign extend |
>> |
(none) |
(none) |

Right shift, zero fill |
>>> |
(none) |
(none) |

Not |
~ |
Not |
Not |

And |
& |
And |
and |

Or |
| |
Or |
or |

Exclusive or |
^ |
Xor |
xor |

Visual Basic for Applications provides integral types, such as Long, which can be directly manipulated using these bitwise operators. The calculator and JavaScript provide only a “number” type, which does not necessarily correspond to a computer word. These two platforms convert arguments to these and results from these to twos complement 32-bit numbers. Such numbers are integers between -2147483648 and +2147483647.

The various bitwise operatotions can be implemented, with some amount of care, on platforms not having them — in fact, on platforms not even having bits. The problem of providing the FX-7400G and CFX-9850G calculators with bitwise operations is in fact an example in this tutorial.

[ Previous page | Top of page | Next page ]

Copyright © 2002 Brian Hetrick

Page last updated 27 January 2002.

Tutorial

Building Blocks I

Expressions

Bitwise

Control Flow II

Basic I/O

Algorithms

A First Program

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card