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 32bit 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:
http://math.hws.edu/eck/cs225/s12/style_guide.html
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 32bit 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 multibit 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 32bit 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 32bit 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 0th 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 Nth bit of x. 
y = (x >>> N) & 1;  y is the Nth bit of x (0 or 1). 
if ( (x & (1 << N)) != 0 )  Tests if the Nth bit of x is 1. (Parentheses around 1 << N are required.) 
if ( ((x >>> N) & 1 ) != 0 )  An alternative way to test if the Nth 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:


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 casesensitive. 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: Bitbybit
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 copyandpaste to get it into your program.)
private static final int[] numbers = { 1044480, 15732480, 117440736, 402653208, 819990028, 1088425474, 2132799999, 2147483647, 2147385343, 2122317439, 1081085446, 806350852, 402653192, 117440624, 16256896, 520192, 0, 1 };
For each integer in this array, your program should write one line of output. Consider the integer as a 32bit binary number. Go through the number bitbybit, 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: Inttohex
For this exercise, you should output 32bit integers as
8digit 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 builtin 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: Binarytoint
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 builtin 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: Hextoint
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.