#
Learn Programming in Java

<<Previous | ToC
| Next >>

###
Simple Bitwise Operators

In the next lesson we would like to do an interesting program, something
like a game -- better than Chomp, where you only programmed how to play
the game, now you will actually write the game engine -- where the computer
plays one side and a person (you) plays the other. One of the requirements
for building larger programs is the ability to access values indirectly.
This is really one of the topics for next week, but I don't want to wait
that long before you get to work with a fun program, so this is a little
bit of esoterica that you won't see in your average beginning programming
class.
We start by understanding binary numbers. Pretty much everybody understands
binary numbers, right? They started teaching that stuff in grade school
about the time I got out of college. Here is counting from zero to twenty
in decimal (base ten), binary (base two), and hexadecimal (base 16):

`Dec Bin Hex Power`

` 0 0000 0`

` 1 0001 1 2`^{0}

` 2 0010 2 2`^{1}

` 3 0011 3`

` 4 0100 4 2`^{2}

` 5 0101 5`

` 6 0110 6`

` 7 0111 7`

` 8 1000 8 2`^{3}

` 9 1001 9`

`10 1010 A`

`11 1011 B`

`12 1100 C`

`13 1101 D`

`14 1110 E`

`15 1111 F`

`16 10000 10 2`^{4}

`17 10001 11`

`18 10010 12`

`19 10011 13`

`20 10100 14`

I listed the hexadecimal next to the binary because each four binary
digits (called *bits*) corresponds to exactly one hex digit. When
the binary spills over into a fifth digit, the hex spills over into a second
digit. This is important because if you want to spell a binary number in
your program, you normally use hex, so that (for example)

(binary) `1101 1110 1010 1101 1011 1110 1110 1111 = 0xDEADBEEF`
(hexadecimal)

where the "`0x`" at the front of the number tells Java that it's
a number (because only numbers start with a digit like 0) but hexadecimal
is not decimal (that's what the "x" is for). After a while you will have
the important bit patterns memorized, and maybe even be able to convert
from common hex numbers to decimal and back in your head.

As you know, each binary digit, each `0` or `1`, represents
exactly one minimal piece of information, yes or no, hot or cold, `true`
or `false`. Because we have 32-bit numbers in Java, that gives us
32 different pieces of information we can store in each number. For example,
a checker board has 64 squares, but for the game of checkers we only use
half of them, so we could make a single number represent all the squares
that have a piece on them, or better, we can use two variables, one to
hold all the squares that have black pieces, and another with all the squares
that have red pieces. We do this by numbering the squares that can have
a piece of any color, from 0 to 31 (in computers we always count from zero)
from left to right, bottom to top, so the black initial position would
be binary `0000 0000 0000 0000 0000 1111 1111 1111` (hex `0x00000FFF`,
decimal 4095), and the red initial position (using the same numbering scheme)
would be `1111 1111 1111 0000 0000 0000 0000 0000` or `0xFFF00000`
(decimal -1048576).

Notice how each bit in the binary number represents a particular power
of two, 2 times itself that many times (where `2`^{0}
is 2*2 zero times, which is 1 (not 0), and `2`^{1}
is a single 2, as in the table above). This suggests that we can use a
power function to get at those bits. But this is binary,and the hardware
thinks in binary, so there's an easier way to get a bit into a particular
position, which we call *shift.* Shifting a bit (or group of bits)
*left*
effectively doubles its value; shifting it *right* halves the value.
The Java operator to do this is "`<<`" to shift left, and
"`>>`" to shift right.
Now, as long as there isn't something already in that bit position,
you can turn it on by adding a number with just that bit on, and every
other bit off. However, if it's already set, that starts to scramble other
bits in the number, so we have a couple of operators that operate only
on their corresponding bits, with no carries out into adjacent bits. To
turn a bit on, we use the *logical OR* ("`|`")
and to turn it off we use *logical AND* ("`&`").
It's also useful to flip one or more bits from one to zero or zero to one,
which is called *exclusive OR* ("`^`").
All of these (including the shifts) are called *bitwise* operators.
You could write a little program to try these out and see what they do,
but that will be easier after the next couple of lessons. So for now you
get tables, like the times table you memorized in grade school -- or maybe
they don't do that any more, y'all have calculators in your phones...

` & | 0 1
| | 0 1 ^ | 0 1`

`---+------ ---+------
---+------`

` 0 | 0 0 0 | 0
1 0 | 0 1`

` 1 | 0 1 1 | 1
1 1 | 1 0`

Before we leave arithmetic and assignments, I should mention two useful
shortcuts that show up everywhere, the *increment* (`++`) and
*decrement*
(`--`) operators. In a program where variable `i` is an integer,
"i++;" is syntactic sugar for (means exactly the same as) "`i=i+1;`"
and "`i--;`" means the same as "`i=i-1;`". You may also see
the operator before the variable "`++i;`" which is the same, except
when used inside an expression value. Java allows any assignment statement
to be used as a value, but I do not recommend it. My college-level students
sometimes got that wrong, and you don't need that kind of problem in your
programs.
Next: Conditionals & Input

Optional: Chomp in Java (this
needs revision)

<<Previous | ToC
| Next >>

Revised: 2020 November 13