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:

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.

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