-----BEGIN PGP SIGNED MESSAGE-----

It's often explained that the reason for some of the imprecision

in C's definition is so that C can be implemented on different

kinds of machines -- say, those with 2's complement,

1's complement, or sign-magnitude arithmetic. But the followup

remark is sometimes also made that the choice of arithmetic isn't

completely unconstrained, since the bitwise operators seem to

presume a base-2 machine.

In fact, this is an unnecessarily restrictive argument. As I'll

show, there are valid -- even useful -- interpretations of the

bitwise operators when applied to base-10 numbers. Furthermore,

these interpretations make it easy to perform bitwise arithmetic

on decimal numbers in your head, without performing cumbersome

conversions from decimal to binary and back.

First of all, remember that in the binary case, and even though

we call them "bitwise" operators, it's not necessary to think

of a computer as computing them one bit at a time. A modern

computer, of course, works on several bits in parallel, and if

you write down some binary numbers in hexadecimal, where each

hexadecimal digit -- or "hexit" -- represents exactly 4 bits, you

can fairly easily work a bitwise problem 4 bits or 1 hexit at a

time, if you also learn a bunch of rules such as that E&7 is 6.

In all honesty, though, for hand calculation, this doesn't end up

being any more practical than working in base 2, since base 16

isn't any more familiar to us than base 2 is, and there are far

too many of those inscrutable rules to remember. However,

thinking about the base 16 working of bitwise operators gives us

an important clue: when applying the bitwise operators to decimal

numbers, we're allowed to approach the problem one digit at a

time, without worrying individually about the underlying bits.

We also need to discover a more intuitive "meaning" for those

abstract operators AND, OR, and XOR. Fortunately, this is easily

done. The AND operator generates a 1 bit only when both of its

inputs is 1. That is, in binary,

0 AND 0 is 0

0 AND 1 is 0

1 AND 0 is 0

1 AND 1 is 1

The practical upshot of this is that the AND operation yields

the *smaller* of its two inputs, and this is a much easier rule

for you and me to remember and to apply.

The OR operator generates a 1 bit when either of its inputs

(or both) is 1. If you work through a table like the above,

you will discover that the OR operator yields the *larger* of

its two inputs. So for the two contrasting binary operators with

their inscrutable base-2 truth tables, we have two contrasting

logical operators "minimum" and "maximum" which are much easier

for us to think about. This is a very nice result, and it's far

too regular and orthogonal to be a mere coincidence. In fact,

it's the cornerstone of the method we'll use to simplify the

application of bitwise operators to decimal numbers.

However, we still have to examine the behavior of the XOR, or

"exclusive or", operator. The output of the XOR operator is 1 if

either of its inputs is 1, but *not* both. That is, returning to

the ugly tabular notation, we have:

0 XOR 0 is 0

0 XOR 1 is 1

1 XOR 0 is 1

1 XOR 1 is 0

Examining the digits, we see that the XOR output is always the

difference between the two input bits, that is, the larger minus

the smaller. So when we're trying to understand the operation

of XOR, it will be much easier to think of it in terms of

subtraction.

So now we can put this all together. To work a bitwise problem

in decimal, examine the two numbers by digits, pairwise, one pair

of digits at a time. If you're computing the bitwise OR, take

the larger digit of each pair. If you're computing the bitwise

AND, take the smaller digit. And if you're computing the bitwise

XOR, take the difference between the two digits.

Let's illustrate this with some examples. Suppose we're

computing the bitwise XOR of 22 and 55. At each digit position,

the larger of the two digits is 5, so the bitwise OR is 55.

The smaller digit is 2, so the bitwise AND is 22. And the

difference between the two digits is 3, so the bitwise XOR is 33.

Another example: 35 and 53. At each digit position, the larger

digit is 5, so the bitwise OR is again 55. The smaller digit is

3, so the bitwise AND is 33. The difference between the two

digits is 2, so the bitwise XOR is 22.

Those are pretty trivial examples, and you may be suspicious that

they're contrived, so let's look at a longer one: 4829 and 6670.

To compute the bitwise OR, take the largest digit at each

position. 4 vs. 6 is 6, 8 vs. 6 is 8, 2 vs. 7 is 7, and 9 vs. 0

is 9, so the result is 6879. To compute the bitwise AND, take

the smaller of each pair: 4620. And to compute the exclusive OR,

take the difference between the digits: 6-4 is 2, 8-6 is 2, 7-2

is 5, and 9-0 is 9, so the XOR is 2259. (Check these results

with your C compiler if you like.)

* * *

The fact that the bitwise operators have a natural and

easy-to-compute interpretation for decimal numbers is more than

just an intellectual curiosity. Decimal bitwise operators are

only interesting if they have practical uses. As it turns out,

the interpretations I've described here *do* have practical

uses, and moreover, they're analogous to the traditional uses

which the bitwise operators have, when applied to binary numbers.

For example, consider the problem of extracting certain bits from

a binary number. This is commonly done using a "bitmask" and the

bitwise AND operator. For example, if we perform the operation

110101010 & 000111000

we extract the middle three bits from the binary number on the

left-hand side, discarding the rest. The operation of the base-2

bitwise AND operator is such that wherever there's a 1, the bits

of the other number are passed through, but wherever there's a 0,

any 1 bits in the other number are suppressed, leaving only 0's.

So the bitmask 000111000 selects just the middle 3 bits of the

9-bit field: 000101000.

Extracting digits from decimal numbers is a common problem.

Wouldn't it be nice if we could use "decimal bitmasks", or

"ditmasks", to extract the digits of a decimal number? In fact,

we can, and we'll use the decimal bitwise AND operator to do so.

Remember, the operation of the decimal bitwise AND operator is to

take the smaller of the two digits in each position. So if we

prepare a ditmask consisting of 0's and 9's, we'll get just what

we want. Wherever there's a 0 in the ditmask, that 0 will be

smaller of the two digits, so the corresponding digit in the

other number will be suppressed. Wherever there's a 9 in the

ditmask, the corresponding digit in the other number will either

be smaller, or will be 9, and in either case the corresponding

digit in the other number will be effectively selected.

To see how this works, let's try an example: we'll use the ditmask

090 to select the middle digit from the three-digit number 884.

The rule as I've just described it works, and you can try it with

your C compiler to double check. Another example: the 5-digit

ditmask 00990, to select the tens and hundreds digits. Try it

on the number 781, you get 780. Try it on 43869, you get 00860.

The 9's in the ditmask do not have to be adjacent, any more than

the 1's in a binary bitmask have to be adjacent -- for example,

the ditmask 090090 when applied to the number 471458 selects the

digits 7 and 5, yielding 070050, or when applied to 3821149

selects the 2 and 4 (0020040).

* * *

In conclusion, C's bitwise operators have meaningful

interpretations and work quite well on decimal numbers.

C would be straightforward to implement on a machine using

base-10 integers, using the interpretations I've described here.

Furthermore, since the definitions of the decimal bitwise

operators I've provided are of necessity compatible (at the

numerical level) with the traditional interpretation, and since

the actual number system used by a computer's CPU is effectively

invisible to a portably-written program, a programmer who wishes

to do so can use the decimal interpretations even on a binary

computer. (After all, this makes just as much sense as assuming

that the base-2 integers of a conventional binary computer are

decimal in some other context, e.g. printing them out using %d.)

For example, the ditmask technique for extracting digits from

decimal numbers works just as well on a binary computer as it

would on a decimal computer, as the examples above (if you try

them on your favorite binary computer) all demonstrate.

Steve Summit

sc*@eskimo.com
-----BEGIN PGP SIGNATURE-----

Version: 2.6.3in

iQCSAwUBQk02rd6sm4I1rmP1AQGP/wPmJ+pS2DM5yxhJuanfA0qaBOWFdfYWqHp5

A/heFTMzipJEtFDazXTPlZ4KwR2XNIBvown4dTds3/JT6JYJ5bLAW0qkS5kmaQjL

cqU0NKJ3Mmvm+dtxd1Y+sLq0bF1vpfOKyhz3z/ZY9oDBXqP5/btRyIn60EkoPVk4

OFw/Rw0=

=OBO0

-----END PGP SIGNATURE-----