CPSC 220, Fall 2012
Lab 1: Bitwise Operations in Java

Welcome to the first lab for CPSC 220. In this lab, you will manipulate individual bits and groups of bits in 32-bit integers using bitwise logical operations. The lab consists of a series of short exercises exploring various uses of those operators.

You should write a single Java program that does all the exercises listed below, one after the other. Write a subroutine for each exercise and a main routine that just calls each of the subroutines. You can, of course, use additional subroutines. Your program must exhibit good programming style; this includes formatting, commenting, variable and subroutine names, and quality of interaction with the user. If you have any doubt about whether the style of your program is acceptable, ask! Or, see this style guide from CS225:


Some of the exercises require you to get input from the user. You can do the input any way you like, such as with TextIO or a Scanner. You can find a copy of TextIO.java in the directory /classes/cs220, if you need it.

Your program is due at the beginning of next week's lab. To submit your work, you should find your homework folder inside the directory /classes/cs220/homework. You should put a folder named lab1 in your homework folder. You should put only your Java source code file into that folder. There is no need to include class files. (And please do not copy an entire Eclipse project folder.)

About the Operators

Java (like C and many other programming languages) has four bitwise logical operators that operate on individual bits within integers. An integer is represented internally in the binary number system, that is, as a sequence of 0's and 1's. A value of type int in Java is, for example, a 32-bit integer. The byte, short, and long data types use, respectively, 8, 16, and 64 bits. The bitwise logical operators &, |, and ^ are binary operators that operate on a pair of bits, while ~ is a unary operator that operates on a single bit. They are defined by this table:

x y x & y x | y x ^ y ~x
0 0 0 0 0 1
0 1 0 1 1 1
1 0 0 1 1 0
1 1 1 1 0 0
Meaning: x AND y x OR y x XOR y NOT x

When these operators are applied to multi-bit integers, they apply to each bit position separately. For example, 00101110 & 10100011 = 00100010, and ~00101110 = 11010001.

Java also has three bit shift operators that work on the level of bits. The bit shift operators shift all the bits in a number a specified number of positions to the left or to the right. The operators are <<, >>, and >>>, and they are defined for integers x and N as:

x << N Shift the bits in x to the left by N bit positions,
losing bits from the left end of x, and filling
in vacated positions on the right with zeros
x >>> N Shift the bits in x to the right by N bit positions,
losing bits from the right end of x, and filling
in vacated positions on the left with zeros
x >> N Shift the bits in x to the right by N bit positions,
losing bits from the right end of x, and filling
in vacated positions on the left with zeros or ones.
(Use zeros if x is positive, ones if x is negative.)

If x is a 32-bit int, then the value of N should be in the range 0 to 31. I'm not sure of the result in other cases.

The bit positions in a 32-bit integer are numbered 0, 1, 2, ..., 31, from right to left. Note in particular that (1 << N) is an integer that has a 1 in bit position N and a 0 in every other position. And (x >>> N) is a number whose 0-th bit is equal to the N-th bit of x. You can use this to set or test the N-th bit in an integer x:

x = x | (1 << N); Sets bit N of x to be 1.
x = x & ~(1 << N); Sets bit N of x to be 0.
x = x ^ (1 << N); Flips the N-th bit of x.
y = (x >>> N) & 1; y is the N-th bit of x (0 or 1).
if ( (x & (1 << N)) != 0 ) Tests if the N-th bit of x is 1.
(Parentheses around 1 << N are required.)
if ( ((x >>> N) & 1 ) != 0 ) An alternative way to test
if the N-th bit of x is 1.

(The operators >> and >>> are actually equivalent for this purpose.) You can also work with groups of bits. For example, the number 15 in binary is 00000000000000000000000000001111. If you compute y = x & 15, then y has the same bits as x in positions 0, 1, 2, and 3, while all the other bits of y are 0. This is called masking; you have "masked out" all the bits of x except for the first 4. By combining this with a shift, you can get other groups of four bits out of x. For example, (x >> 4) & 15 would get you bits 4, 5, 6, and 7 from x.

Working with groups of bits becomes easier if you use hexadecimal numbers. Hexadecimal numbers use the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. Each symbol represents a group of 4 bits, as shown in this table:

hex binary
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
hex binary
8 1000
9 1001
A 1010
B 1011
C 1100
D 1101
E 1110
F 1111

You can use hexadecimal numbers in Java by prefixing them with 0x. For example, 0xF is 15 (a number with 1111 in the rightmost four bit positions), and 0xFFFF0000 is the number with 0's in bit positions 0 through 15 and 1's in positions 16 through 31.

Note that this notation is not case-sensitive. The lowercase letters a, b, c, d, e, f are considered to be equivalent to the uppercase A, B, C, D, E, F.

Exercise 1: Bit-by-bit

For your first exercise, you should start by copying this array into your program. (You don't have to retype it! Open this page in a web browser and use copy-and-paste to get it into your program.)

    private static final int[] numbers = {

For each integer in this array, your program should write one line of output. Consider the integer as a 32-bit binary number. Go through the number bit-by-bit, from left to right. For each bit, if the bit is a 0, print a blank space; if it is a 1, print the letter 'X'. You should print 32 characters on each line.

(I expect that you will want to print out something like "Answer for Exercise 1", at the very least, before outputting the answer.)

Exercise 2: Int-to-hex

For this exercise, you should output 32-bit integers as 8-digit hexadecimal numbers, including the "0x" prefix that is used for hex numbers in Java. Use the same array as for Exercise 1. For each number in the array, output the number in its usual decimal form as well as in hexadecimal form. You should do this by manipulating the bits in the number: To get one of the hex digits in a number, grab a group of four bits from the number and convert it into the equivalent hexadecimal symbol. For example, the number 15 would come out as 0x0000000F.

(Java has built-in methods for doing this type of transformation, but you shouldn't use them for this exercise. You are being asked to do the bit manipulation yourself, using the bitwise and bit shift operators.)

Exercise 3: Binary-to-int

For this exercise, you should read binary numbers typed in by the user and convert them to ordinary int values. You should read a series of lines of input from the user. Read each line as a String value. Use an empty line of input as a signal to end the loop. Aside from the empty line at the end, each line of input should contain between 1 and 32 zeros and ones. If the user inputs anything else, output an error message, and continue on to the next line of input. If the user's input is valid, you should find and print the equivalent int value. For example, if the user's input is 1101, then your output would be the number 13.

(As in the previous exercise, you should avoid Java's built-in methods for doing the conversion. You should do the conversion yourself, using bitwise and bit shift operators. It's also acceptable to do this exercise using multiplication and addition instead of the bit operations.)

Exercise 4: Hex-to-int

Repeat the previous exercise, except that now the user will enter hexadecimal numbers instead of binary. Each line of input from the user should contain between 1 and 8 hexadecimal digits. (You can allow an optional "0x" at the beginning, if you want, but you should not require it.) You should convert the user's input to the equivalent int and print the result.