By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 424,853 Members | 974 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,853 IT Pros & Developers. It's quick & easy.

# bitwise decimal operators

 P: n/a -----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----- Nov 14 '05 #1
Share this Question
2 Replies

 P: n/a Steve Summit wrote: 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. I think of XOR 1 as flip bit and XOR 0 as preserve bit. unsigned char bit_rev(unsigned char byte) { unsigned hi_mask, lo_mask; hi_mask = ((unsigned char)-1 >> 1) + 1; lo_mask = 1; do { if (!(byte & hi_mask) != !(byte & lo_mask)) { byte ^= hi_mask | lo_mask; } hi_mask >>= 1; lo_mask <<= 1; } while (hi_mask > lo_mask); return byte; } -- pete Nov 14 '05 #2

 P: n/a In article , sc*@eskimo.com (Steve Summit) writes: 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. What, all that fishing and no bites? Well, *I* thought it was funny, anyway. -- Michael Wojcik mi************@microfocus.com Nov 14 '05 #3

### This discussion thread is closed

Replies have been disabled for this discussion. 