Comp 111 --- Introduction to Computers

Lecture notes for week of 11/16/98 -- 11/20/98

(Related reading in text: pp. 177--181)

Binary numbers
Two's complement
Bitwise operators
Shift operations
Applet examples:
- Click here to try an applet that demonstrates how bitwise operators can be used to check if a number is even or odd.
- Click here to try an applet that demonstrates the effects of the shift operations. Click here to see the Java code for the applet.

Binary Numbers

Just a Bunch of Zeros and Ones

Digital vs. analog
Discrete values: on or off
Two-valued memory cells
Can build all other numbers from 0s and 1s

Some Powers of Two

   power of 2    base-10     base-2 (binary)
--------------------------------------------
 2⁰     1               1
 2¹     2              10
 2²     4             100
 2³     8            1000
 2⁴    16           10000
 2⁵    32          100000
 2⁶    64         1000000
 2⁷   128        10000000
 2⁸   256       100000000
 2⁹   512      1000000000

 2¹⁰ 1024     10000000000
 2¹¹ 2048    100000000000
 2¹² 4096   1000000000000
    ...

Binary-Number Examples

  23 = 16 + 0 + 4 + 2 + 1
        1   0   1   1   1  = 10111

 252 = 128 + 64 + 32 + 16 + 8 + 4 + 0 + 0
         1    1    1    1   1   1   0   0
     = 11111100

5017 = 4096 + 0 + 0 + 512 + 256 + 
        128 + 0 + 0 + 16 + 8 + 0 + 0 + 1   
     = 1001110011001

Addition of Binary Numbers

Just as with decimal numbers:

  23           10111
 +37          100101
--------------------
  60          111100 = 32 + 16 + 8 + 4

Lingo

bit: a binary digit (i.e., either 0 or 1)
most-significant bit: left-most bit
least-significant bit: right-most bit (one's place)
byte: eight bits (256 possible values)

Review: Integer Values in Java

byte (eight bits): -128 ... 127
short (16 bits): -32,768 ... 32,767
int (32 bits): -2,147,483,648 ... 2,147,483,647

long (64 bits):

     -9,223,372,036,854,775,808 ...
      9,223,372,036,854,775,807

Two's Complement

The Other Side

Numbers are stored so as to:

make it easy to test if a number is positive, negative, or zero
be compact: don't waste memory
efficiently compute additive inverses
-0 = 0

In order to meet these needs, integer values (byte, short, int, long are stored using two's complement representation.

The two's complement of an n-bit integer value i is:

If i >= 0 then: usual binary representation of i
If i < 0 then: complement (all 1s become 0s and all 0s become 1s) plus 1.

For example, assuming byte-sized numbers:

  23 ==>  00010111

 -23 ==>  11101000 + 1 ===> 11101001

 127 ==>  01111111 

-127 ==>  10000000 + 1 ===> 10000001

  -0 ==>  11111111 + 1 ===> 00000000


  -2 ==>  11111101 + 1 ===> 11111110

  -1 ==>  11111110 + 1 ===> 11111111

   0 ==>                    00000000

   1 ==>                    00000001

   2 ==>                    00000010

Bitwise Operators

Unary Complement Operator

The unary complement operator inverts (or ``flips'') all the bits in a number:

   17  ==>  00010001
  ~17  ==>  11101110 

  -17  ==>  11101111
~(-17) ==>  00010000

Bitwise And, Or, Xor Operators

If i and j are integer values, then i & j (the ``bitwise-and'' of i and j) means:

line up the two numbers in their (two's complement) binary representation
if corresponding bits are both 1 then resulting bit is 1, otherwise resulting bit is 0 (i.e. resulting bit is 1 only if bit in first number is 1 AND bit in second number is 1)

For example:

  23 & 37       00010111
                00100101
  ----------------------
        5       00000101


  23 | 37       00010111
                00100101
  ----------------------
       55       00110111


  23 ^ 37       00010111
                00100101
  ----------------------
       50       00110010


  -123 & 1      11101001
                00000001
  ----------------------
                00000001

Parity Check

Q: What's an easy way to check if a number is even?

A: Check the least-significant bit (one's place) in the binary representation:

If it is 0 then the number is even
If it is 1 then the number is odd

Parity Examples

decimal rep     binary rep     odd/even
---------------------------------------
          5       00000101       ODD

         -5       11111011       ODD

        100       01100100       EVEN

        117       01110101       ODD

         22       00010110       EVEN

Parity-Check Method

  23 & 1      00010111
              00000001
  ----------------------
              00000001    ==> 1


  boolean isEven(int i) {
    return ((i & 1) == 0);
  }

Shift Operators

Uncovering the Binary Representation

Goal: Given an integer value i, display its underlying binary representation.

Idea: Do not treat i as if it were represented in base 10. Instead, make use of the bitwise operations.

An Algorithm (for `byte` values)

To identify the binary representation of a value of Java's byte type:

If bit in 1's place is 1 (on) then right-most character in the string is ``1'', otherwise (bit is off) its ``0'' If bit in 2's place is on then add ``1'' at front of the string, otherwise add ``0'' If bit in 4's place is on, add ``1'' else ``0'' ... If bit in 64's place is on, add ``1'' else ``0'' Finally, if bit in 128's place (sign bit) is on, add ``1'' else ``0''

Example: finding the 32-place bit (or any bit) Suppose we want to know if the 32-place bit is set in the number 91: 91 & 32 01011011 00100000 ---------------------- 00000000 ==> 0 Finding the 2^k's-place bit To find the 32-place bit we perform a bitwise and (&) with 32. To find the k-th bit from the right we perform a bitwise and (&) with 2^k-1. 2^k in binary is 1 followed by k zeros. ``Powerful'' Bit Operations Observe: 11 00001011 22 00010110 44 00101100 If we ``shift'' the bits one place to the left, and add a 0 at the last place, we double the number. The Shift-Left Operator (<<) n << k means shift n (in binary) to the left k bits and add k zeros on the right. The left-most k bits are discarded. 11 << 2 00001011 44 00101100 1 << 5 00000001 32 00100000 Shifting left by k multiplies the number by 2^k$ (modulo 2^m-1 where m is the total number of bits in the representation.)

`The Shift-Right Operator (`)

n >> k means shift n (in binary) to the right k bits and add k zeros on the left (if n > 0) or k ones on the left (if n < 0). The right-most k bits are discarded.

  22 >> 2    00010110
        5    00000101
      
-100 >> 3    10011100
      -13    11110011

Shifting right by k divides the number by 2^k (and rounds down).

Click here to try an applet that demonstrates the effects of the shift operations. Click here to see the Java code for the applet.

Examine the code below, used to display a number as a binary string. Notice how redundant the body of the method toBinaryString is. There has got to be a better way... there is! Tune in next week for more info.

    // checks if kth bit in (32-bit) binary representation of
    // integer n is on (i.e., 1)
    public boolean isKthBitOn(int n, int k) {
	if (k < 1) 
            return false;
        else {
            int i = n & (1 << (k-1));
            return (i != 0);
        }
    }

    // convert kth bit in (32-bit) binary representation of
    // integer n to string ("0" or "1")
    public String kthBit(int i, int k) {
        if (isKthBitOn(i, k)) 
            return "1";
        else
            return "0";
    }


    // convert integer i to a String revealing its 
    // (32-bit) binary representation 
    public String toBinaryString(int i) {
        String s = "";
        int k = 1;

        // bits 1-8
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;

        // bits 9-16
        s = " " + s;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;

        // bits 17-24
        s = " " + s;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;

        // bits 25-32
        s = " " + s;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;
        k = k + 1;
        s = kthBit(i,k) + s;

        return s;
    }
}