Previous page Next page Navigation bar

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:

b9b8b7b6b5b4b3b2b1b0 right shift 3 → 000b9b8b7b6b5b4b3
b9b8b7b6b5b4b3b2b1b0 left shift 3 → b6b5b4b3b2b1b0000

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

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 2m-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 011111111111111111111111111111112 is 2147483647, but incrementing this value by 1 yields 100000000000000000000000000000002, which is considered to be 2147483648. On such a machine, a logical right shift of this value would yield 010000000000000000000000000000002, 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 100000000000000000000000000000002 by one bit would be 110000000000000000000000000000002, 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:

b9b8b7b6b5b4b3b2b1b0 right rotate 3 → b2b1b0b9b8b7b6b5b4b3

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:

b9b8b7b6b5b4b3b2b1b0 right shift 3 → 000b9b8b7b6b5b4b3
b9b8b7b6b5b4b3b2b1b0 left shift 7 → b2b1b00000000
Logical Or of right shift 3 result and left shift 7 result: b2b1b0b9b8b7b6b5b4b3

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:

a9a8a7a6a5a4a3a2a1a0 op b9b8b7b6b5b4b3b2b1b0 → c9c8c7c6c5c4c3c2c1c0

where ai op bi → ci, where op is now the corresponding logical operation and ai, bi, and ci 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.

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.

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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2002 Brian Hetrick
Page last updated 27 January 2002.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Preface

Introduction

Fundamentals

Building Blocks I

Introduction

Comments

Data Types

Numbers

Variables

Expressions

Introduction

Arithmetic

Grouping

Relational

Logical

Bitwise

String

Side Effect

Functions

Control Flow I

Control Flow II

Subprograms

Basic I/O

Algorithms

A First Program

Examples

Exercises

Answers

Modularization

Data Structures I

Recursion

Program Attributes

Building Blocks II

Algorithm Analysis

Structuring

Data Structures II

Abstract Types

Objects

Problem Analysis

Reference Card

References

Puzzles

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data