The "Logic" part of the ALU
The ALU is the arithmetic-logic
unit. We know that the ALU does arithmetic operations such
as ADD and MULT, but what is this "logic" stuff?
The ALU can carry out operations other than just airthmetic. It
can do comparisons, such as
whether X is greater than Y, and it also lets you play with
bits. Typical ALUs are 32 bits and
64 bits (more for floating-point operations rather than integer).
Two of the logic operations
are the bitwise OR and the bitwise AND. Here, the 32-bit
"numbers" are not actually
numbers at all--they are what are known as "bit strings". Each bit in a
bit string represents
something--not a power of 2 in this case. To illustrate, let's
have a 16-bit string for UT
students (we're numbering the bits right-to-left from 1 to 16--again,
these are NOT powers
of 2).
___ ___ ___ ___
___ ___ ___ ___ ___ ___
___ ___ ___ ___ ___ ___
16 15
14 13
12 11 10
9
8 7
6
5
4 3
2 1
meanings: 0 = false 1 = true
bits
______________________________________________________________________
1 grad
student
9 GPA is 2.00+
2
undergrad
10 GPA is 2.50+
3
in-state
11 GPA is 2.75+
4 has hope
scholarship
12 GPA is 3.00+
5
freshman
13 GPA is 3.5+
6
sophomore
14 GPA is 3.75+
7
junior
15 lives on campus
8
senior
16 on probation
Donnie Wahlberg: 0101 1111 0100
1110: lives on campus, GPA is 3.5+, junior, hope scholar,
in-state, undergrad
Ludwig Snarf:
1000 0000 1000 0110: on probation, GPA is
less than 2.0 (otherwise bit
9 would be a 1), senior, lives off-campus
(otherwise bit 15 would be a 1), in-state, undergrad.
These are patterns of bits that contain information about
students. Note that home address,
etc. are not represented here--that info would be in the student
database.
Now--bitwise operations. Bitwise means that we're not adding,
etc--no carry-in or carry-out.
We're comparing/matching two bit patterns, column by column: what
occurs in column 9, for
example, does not affect anything in other columns. You might
think of 1 as being "true", 0
as being "false".
BITWISE AND. If both bits being compared are 1's, the bitwise
result is a 1--otherwise the
result is 0. Think of someone saying "I'm a UT student and
my GPA is 3.9". Is the student
telling the truth? Suppose the GPA is indeed 3.9 but the student
is at Pellissippi, not UTK.
Or suppose the student is at UTK but the GPA is 2.3. Both parts
must be true for the whole
statement to be true.
BITWISE OR. If either (or both) bits is a 1, the result is
1. Only if both bits are 0 is the result
0. "My GPA is 3.9 or I'm a liar". If either part is true,
the statement is true. Only if both parts
are false is the statement false (this could be confusing--if the
statement is false, the person
making it is lying--so perhaps "My GPA is 3.9 or I always lie" would be
better).
1011
1001
AND 0110 OR 1100
--------- --------
0010
1101
A "BIT MASK" is a particular pattern of bits that we're looking
for. Suppose we want to know
whether a student can continue their Hope scholarship (I think this now
requires a 2.75 GPA).
To continue the scholarship, bits 2, 3, and 4 must be 1's (undergrad,
in-state, already has a Hope
scholarship (??) and bit 11 must also be a 1 (GPA is 2.75 or
better). So for each student we will
do a bitwise AND with the following pattern:
0000 0100 0000 1110
Donnie Wahlberg: 0101 1111
0100
1110
Ludwig Snarf: 1000 0000 1000 0110
bit
mask
: 0000 0100 0000
1110
mask : 0000 0100
0000 1110
AND result
-------------------------
---------------------------
0000 0100 0000
1110
0000 0000 0000 0110
If we now did a comparison, treating the results as numbers, if we
subtract the mask from the
result, in Wahlberg's case the result is 0--meaning all the right bits
were 1's, and the result
in Snarf's case is negative--meaning at least one bit which should have
been a 1 is a zero--
and hence fails to match the criteria.
--------------------------------------------------------------------------
BIT SHIFTS
The ALU can also take a bit string (or number) and perform a shift
operation--meaning that
each bit gets shifted left or right by some number of bits: a
1-bit left shift of 001101 would
produce 011010, for example. This may not seem very useful.
But suppose we have a true-
false exam with 32 questions, and we have a resulting 32-bit pattern
showing which questions
the student answered correctly. For a 6-question TF test, 110100
would mean the student
answered questions 3, 5, and 6 correctly, 1, 2, and 4 were
incorrect. So how could we figure
out how many questions the student answered correctly? We can use
bit shifts and a bit mask,
for example.
110100
AND 000001
-------------
This looks only at the rightmost bit--if the bitwise AND
is a 000001, we have a correct answer
and we add 1 to a running total of correct answers. We then shift
the pattern 110100 right 1 bit
and do another bitwise AND. Each time the bitwise AND is 1, we
add 1 to our total--this adds up
all the 1's in the pattern. To answer your unasked
question--"Yes, we could also have shifted the
mask left 1 bit instead".
XOR--exclusive-OR. XOR is a bitwise operation that is 1 (true)
only if one of, buth not both of,
the bits are 1--XOR is a 0 otherwise. So for automatic test
grading of a true-false quiz:
student's
answers: 10101101
XOR correct answers: 01111110
--------------
11010011 0 here meant that both bits were 0's or both
1's, a 1 meant
that one was a 1, the other a 0--an incorrect result. We could
nbow flip the bits and add up the
1's.