[OT] help w/ bitwise comparison operators

[Erik Price]

pll at lanminds.com wrote:

> Would you mind posting a summary of the helpful tips, tricks, and 
> shortcuts sent your way?  I'm rather interested in understanding this 
> stuff a little better myself.

Sure.  In fact, they say you really know something well when you can 
explain it to someone else, and this gives anyone a chance to correct me 
if I'm wrong in what I think I know.  Here's some of the things I 
learned, combined with what I had already learned from my book (please 
*do* correct me if I'm wrong):

1.  The unary bitwise NOT operator (~) has a shortcut, but one which 
only works when two's complement is in effect.  On systems in which 
one's complement is in effect, it doesn't work.  The shortcut is that 
any number n has a bitwise NOT of -n - 1.  So

   ~5 == -6
   ~-12 == 11

Because I'm fortunate enough to be working in Java where you're writing 
for only one platform (the JVM, which has a spec), I don't have to worry 
about exceptions to this for the test.

2.  Other than the NOT operator, the bitwise operators are binary 
operators, working on pairs of numbers.  The bitwise AND operator 
returns a 1 for each pair of bits that are both 1.

So in the case of

   11001 & 10011

the result is 10001 (because only the first and last digits are *both* 1).

The bitwise OR (|) operator returns a 1 for situations in which either 
pair of bits has a 1.

So in the case of

   11001 | 10011

the result is 11011 (because the only place in both numbers where there 
is no 1 is the third digit).

The bitwise XOR (^) operator returns a 1 for situations in which either 
pair of bits, but not both, has a 1 (hence the name "exclusive OR", or XOR).

So in the case of

   11001 ^ 10011

the result is 01010 (because in the first, third, and fifth digits, 
either both numbers are 0 or 1).

The short circuit operators AND (&&) and OR (||) work just like their 
regular counterparts except they stop evaluating once they "know" the 
result (AND stops evaluating if the first operand is false, and OR stops 
evaluating if the first operand is true).

3.  So my original question, "does anyone know any mental shortcuts for 
working with bitwise operators", should have been phrased as "does 
anyone know any mental shortcuts for converting decimal numbers to 
binary".  The answer, which a couple of people provided, was that it's 
much easier to convert to binary (even if only in your head) when you 
are working from octal or hexadecimal, and that it's not too difficult 
to convert from decimal to octal or hexadecimal.

Several ways were suggested:

a) Convert the number to hex, then do the comparison a byte at a time in 
your head using a table:

   &     0x01 0x02 ... 0xff
   0x01  0x01 0x00     0x01
   0x02  0x00 0x02     0x02
   ....
   0xff  0x01 0x02     0xff

b) Convert the number to octal using a simple recursive divide-by-eight 
solution:

divide the number by eight, store the remainder as the low bit depth 
(rightmost number), then repeat the process with the quotient.

   123 / 8 = 15 remainder 3  -- 3 is rightmost digit (3)
   15 / 8 = 1 remainder 7    -- 7 is next to 3 (73)
   we don't divide 1 by 8    -- 1 is next to 7 (173)
   so 123 in octal is 0173

 From octal it's much easier to see the binary form of the number:
    1   7   3
   001 111 011

And from binary it's much easier to do a bitwise calculation.

c) Another way to convert to binary is to simply keep dividing by two 
and assigning 1 if there's a remainder and 0 if there isn't, then read 
in reverse to get the binary number:

<quote>
	If a number is even, dividing it by 2 will have 0 remainder.
If it is odd, dividing it by 2 will have a 1 remainder.  Dividing
by 2 is so easy that I, at least, can just write down a column of
successive halvings, along with 1s and 0s for their oddness.

     459 1
     229 1
     114 0
      57 1
      28 0
      14 0
       7 1
       3 1
       1 1

	Reading from bottom to top, we again get 111001011.  In this
presentation you stop when the quotient is 1, since you've already
written down the remainder that you'd get by dividing 1 by 2 when
you write down the oddness.  Remainder when dividing by 2 is easier
than quotient.
</quote>

d) A final useful tip mentioned:  as long as x is not zero,

   x & -x

will always evaluate to a power of two, which means only one bit is set 
in the number (the least significant of the bits of x that were 1s).

4.  And everyone agreed that it's foolish to do these kinds of 
computations in your head when there's no good reason not to use a 
computer to do it.  My personal preference is to use Python since the 
interactive interpreter works just like a calculator, though any 
scripting language should probably be able to handle the calculations.

(Here's a quick sample:)

|$ python
|Python 2.2.2 (#1, Dec 31 2002, 12:24:34)
|[GCC 3.2 20020927 (prerelease)] on cygwin
|Type "help", "copyright", "credits" or "license" for more information.
|>>> 12 & 14
|12
|>>> 12 | 14
|14
|>>> 12 ^ 14
|2
|>>> ~12
|-13
|>>> myResult = 0x5422CA66 & 458
|>>> myResult
|66
|>>> hex(myResult)
|'0x42'

(hey, it wouldn't be a LUG without a little evangelism, would it? :)


Much thanks to Bill, Jason, Kevin, and YATArchivist.

Erik