CPSC 220, Fall 2018
Lab 1: Numbers and Bits
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 task is to write a Java program that can work with strings representing numbers in decimal, binary, and hexadecimal number form, doing conversions between the three forms.
The assignment is to complete the program Lab1.java, as discussed below. The 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 and copy your completed Lab1.java into that folder. Please submit only the program, and do not change its name.
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 shift operators that work on the level
of bits. The 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.) |
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. |
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 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.
Both hexadecimal and binary numbers can be used in a Java program to represent integers. A hexadecimal literal must start with 0x or 0X — for example, 0xFACE1234. A binary literal must start with 0b or 0B — for example, 0b10010101. A 32-bit integer can be represented by a 32-bit binary literal or by an 8-digit hexadecimal literal.
The Assignment
You should start with a copy of Lab1.java, which
you can get from /classes/cs220 or from a link on this web page.
The main()
routine from that file is shown here. You should not
change this main()
routine in any way:
public static void main(String[] args) { System.out.println("Enter positive or negative decimal numbers,"); System.out.println("binary numbers starting with 0b, or hexadecimal"); System.out.println("numbers starting with 0x. Press return to end."); System.out.println(); Scanner in = new Scanner(System.in); while (true) { System.out.print("INPUT>> "); String token = in.nextLine().trim(); if (token.length() == 0) return; int n; try { n = stringToInt(token); } catch (IllegalArgumentException e) { System.out.printf("Illegal input '%s'%nError: %s%n%n", token, e.getMessage()); continue; } System.out.printf("Decimal: %d%nBinary: %s%nHexadecimal: %s%n%n", n, toBinaryString(n), toHexString(n)); } }
Your assignment is to complete the program. You will need to define the
methods stringToInt()
, toBinaryString()
, and
toHexString()
. You can add other methods and variables as needed.
The main requirements are as follows: You should not use any of Java's built-in
methods for converting between numbers and strings, and you should not use multiplication
or division (except in one case as noted below). You should Use Java's logical bitwise
operators and shift operators to do the conversions. You can use basic String
methods such as charAt()
and length()
. For both input and output,
hexadecimal numbers must start with "0x", and binary numbers must start with "0b".
Decimal numbers can start with a minus sign. The stringToInt()
method must
be able to deal with all of these possibilities in the input string.
The program should not crash. You should
detect any errors in the input and throw an IllegalArgumentException when
an error is found.
The one conversion that can't be done with bit operations is from a decimal String to an int. Ignoring the possibility of negative numbers, that could be done as follows, where str is the string that represents the decimal number:
long n = 0; for (int i = 0; i < str.length(); i++) { char ch = str.charAt(i); if (ch <= '9' && ch >= '0') n = n * 10 + (ch - '0'); else throw new IllegalArgumentException( "Illegal character '" + ch + "'in decimal string."); if (n > Integer.MAX_VALUE) throw new IllegalArgumentException( "Decimal value outside range for int."); }
You can use this code in your program, adapted to include the case of a negative number. (Do you see why n is declared as type long rather than int?) This code also has some hints about how to handle other conversions.
Here is a sample run from a completed version of the program, showing some typical conversions and errors:
INPUT>> 255 Decimal: 255 Binary: 0b11111111 Hexadecimal: 0xFF INPUT>> 0x100 Decimal: 256 Binary: 0b100000000 Hexadecimal: 0x100 INPUT>> 0b000100100011 Decimal: 291 Binary: 0b100100011 Hexadecimal: 0x123 INPUT>> 1234567890123456789 Illegal input '1234567890123456789' Error: Decimal value outside range for int. INPUT>> 0b1020 Illegal input '0b1020' Error: Illegal character '2'in binary string. INPUT>> 0x Illegal input '0x' Error: No hex digits in string. INPUT>> -1 Decimal: -1 Binary: 0b11111111111111111111111111111111 Hexadecimal: 0xFFFFFFFF INPUT>> 0x80000000 Decimal: -2147483648 Binary: 0b10000000000000000000000000000000 Hexadecimal: 0x80000000