Calculator Programming Tutorial

Programming Building Blocks I

Expressions

Bitwise Operators

Introduction

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 — binary digits — and provide operations at the bit level.

Shift and Rotate Operators

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₉b₈b₇b₆b₅b₄b₃b₂b₁b₀ right shift 3 → 000b₉b₈b₇b₆b₅b₄b₃
b₉b₈b₇b₆b₅b₄b₃b₂b₁b₀ left shift 3 → b₆b₅b₄b₃b₂b₁b₀000

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

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₂ is 2147483647, but incrementing this value by 1 yields 10000000000000000000000000000000₂, which is considered to be –2147483648. On such a machine, a logical right shift of this value would yield 01000000000000000000000000000000₂, 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₂ by one bit would be 11000000000000000000000000000000₂, 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₉b₈b₇b₆b₅b₄b₃b₂b₁b₀ right rotate 3 → b₂b₁b₀b₉b₈b₇b₆b₅b₄b₃

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₉b₈b₇b₆b₅b₄b₃b₂b₁b₀ right shift 3 → 000b₉b₈b₇b₆b₅b₄b₃
b₉b₈b₇b₆b₅b₄b₃b₂b₁b₀ left shift 7 → b₂b₁b₀0000000
Logical Or of right shift 3 result and left shift 7 result: b₂b₁b₀b₉b₈b₇b₆b₅b₄b₃

Combination Operators

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₉a₈a₇a₆a₅a₄a₃a₂a₁a₀ op b₉b₈b₇b₆b₅b₄b₃b₂b₁b₀ → c₉c₈c₇c₆c₅c₄c₃c₂c₁c₀

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.

Bitwise Operator Symbols

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.

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.

Programmatic Bitwise Operators

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.