S
Steve Summit
-----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
(e-mail address removed)
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3in
iQCSAwUBQk02rd6sm4I1rmP1AQGP/wPmJ+pS2DM5yxhJuanfA0qaBOWFdfYWqHp5
A/heFTMzipJEtFDazXTPlZ4KwR2XNIBvown4dTds3/JT6JYJ5bLAW0qkS5kmaQjL
cqU0NKJ3Mmvm+dtxd1Y+sLq0bF1vpfOKyhz3z/ZY9oDBXqP5/btRyIn60EkoPVk4
OFw/Rw0=
=OBO0
-----END PGP SIGNATURE-----
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
(e-mail address removed)
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3in
iQCSAwUBQk02rd6sm4I1rmP1AQGP/wPmJ+pS2DM5yxhJuanfA0qaBOWFdfYWqHp5
A/heFTMzipJEtFDazXTPlZ4KwR2XNIBvown4dTds3/JT6JYJ5bLAW0qkS5kmaQjL
cqU0NKJ3Mmvm+dtxd1Y+sLq0bF1vpfOKyhz3z/ZY9oDBXqP5/btRyIn60EkoPVk4
OFw/Rw0=
=OBO0
-----END PGP SIGNATURE-----