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   20
 2   0010   2   21
 3   0011   3
 4   0100   4   22
 5   0101   5
 6   0110   6
 7   0111   7
 8   1000   8   23
 9   1001   9
10   1010   A
11   1011   B
12   1100   C
13   1101   D
14   1110   E
15   1111   F
16  10000  10   24
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 20 is 2*2 zero times, which is 1 (not 0), and 21 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