16 Beginner's Lesson 10: Bit Operations

Lesson 10 attached.

Greetings,

In lesson nine we looked at the C preprocessor. In this lesson we'll
take a quick look at Bit Operations: bit operators and bitmapped graphics.
First of all, a `bit' is the smallest unit of information in a computer.
It is usually represented as either a `1' or a `0'. Bit operations are
used to control the machine at the lowest level.

Eight bits are in a "byte", represented by the C keyword `char'. This is
what a byte might look like, using 1s and 0s to represent bits:

01100100 or 0110 0100 (four bits are called a 'nibble')

In hexadeciaml, this is written as 0x64. C uses "0x" to indicate a base
16, or hexadecimal number. Hexadecimal is handy for representing binary
data because each hexadecimal digit represents a nibble.

Conversion Table:
Decimal, Hexadecimal, and Binary
-------+------------+-----------
0 | 0 | 0000
1 | 1 | 0001
2 | 2 | 0010
3 | 3 | 0011
4 | 4 | 0100
5 | 5 | 0101
6 | 6 | 0110
7 | 7 | 0111
8 | 8 | 1000
9 | 9 | 1001
10 | A | 1010
11 | B | 1011
12 | C | 1100
13 | D | 1101
14 | E | 1110
15 | F | 1111
-------+------------+-----------

So the hexadecimal number 0xAF equals binary 10101111.

Bit operators allow the programmer to work on individual bits. If you
want to learn how to write your own device drivers, or would like to
pixel-level graphics programming, then this lesson might be of interest.
If you're planning on programming higher level applications, then you'll
probably never use bit operators, and you can safely skip this lesson.

Table of Bitwise Operators
----------+---------------
Operator | Description
----------+---------------
& | bitwise AND
| | bitwise OR
^ | bitwise XOR
~ | ones complement (NOT)
<< | shift left
>> | shift right
----------+---------------

These operators work on any integer or character data type.

Bitwise AND (&)
---------------

The & operator compares two bits. If both are 1, the result is 1.

AND Truth Table
----------------
\ | 1 | 0
----+-----+-----
1 | 1 | 0
----+-----+-----
0 | 0 | 0
----+-----+-----

This is how the AND Truth Table is read:
---------+---------+------------
Bit 1 | Bit 2 | Bit 1 & 2
---------+---------+------------
1 | 1 | 1
---------+---------+------------
1 | 0 | 0
---------+---------+------------
0 | 1 | 0
---------+---------+------------
0 | 0 | 0
---------+---------+------------

When two 8-bit char variables are "ANDed" together, the & operator works
on each bit. This program fragment illustrates this:

char c1, c2;
c1 = 0x45;
c2 = 0x71;
printf("Result of %x & %x = %x\n", c1, c2, c1 & c2;

The output is:

Result of 45 & 71 = 41

Here is how it works:

c1 = 0x45 binary is 01000101
& c2 = 0x71 binary is 01110001
---------------------------------
= 0x41 binary is 01000001

The Bitwise AND (&) is similar to the Logical AND (&&). In the Logical
AND, if both operands are TRUE (nonzero), the result is true (one). In
Bitwise AND (&), if the coresponding bits of both operands are true (ones)
then the corresponding bits of the result are true (ones). However, &
and && are different operators. You can use the bitwise AND operator
to test if a number is even or odd because in base 2, all even numbers
end in 0 and all odd numbers end in 1. The following macro uses & to
pick off the last digit. If it is an even number (zero) the result is
TRUE.

#define EVEN(x) (((x) & 1) == 0)

Bitwise OR (|)
--------------

The inclusive OR operator compares two operands, and if one or the other
bit is a 1, the result is 1.

OR Truth Table
----------------
\ | 1 | 0
----+-----+-----
1 | 1 | 1
----+-----+-----
0 | 1 | 0
----+-----+-----

On a byte, this would be:

c1 = 0x47 binary is 01000111
| c2 = 0x53 binary is 01010011
---------------------------------
= 0x57 binary is 01010111

Bitwise XOR (^)
---------------

The exclusive OR (XOR) operator (^) results in a 1 when either of its
two operands is a 1, but not both.

XOR Truth Table
----------------
\ | 1 | 0
----+-----+-----
1 | 0 | 1
----+-----+-----
0 | 1 | 0
----+-----+-----

On a byte, this would be:

c1 = 0x47 binary is 01000111
^ c2 = 0x53 binary is 01010011
---------------------------------
= 0x14 binary is 00010100

The Ones Complement Operator (NOT)
----------------------------------

The bitwise NOT (~) operator (aka `invert operator' or `bit flip') is a
unary operator that return the inverse of its operand.

NOT Truth Table
Bit | ~Bit
------+-------
0 | 1
------+-------
1 | 0
------+-------

On a byte this is:

i = 0x45 binary is 01000101
~i = 0xBA binary is 10111010

The Left and Right Shift Operators
----------------------------------

The left shift operator moves the data a specified number of bits.
Any bits that are shifted out the left side disappear. New bits
coming in from the right side are zeros. The right shift does the
same thing in the other direction.

i = 0x1C binary is 00011100
i<<1 = 0x38 binary is 00111000
i>>2 = 0x07 binary is 00000111

Here is an example program which uses the bitwise shift. This program
might come in handy if you do a lot of work with binary and hexadecimal
numbers. This is a command-line program that accepts a decimal, octal,
or hexadecimal number as an argument, and outputs hexadecimal, octal,
decimal, and binary equivalents. The octal argument must begin with a
zero (ex: 07), and the hexadecimal argument must begin with "0x" (ex: 0xA). Name this program "conv.c" and compile it with: gcc conv.c -o conv

/****************************************************************/
#include <stdio.h>
#define BITS 32
/* conv.c -- July 1998 */
main(int argc, char * argv[])
{
int a;
int i;
if(argc != 2) { /* if too many, or no command-line arguments */
printf("Usage: %s n\n", argv[0]);
exit(1);
}
sscanf(argv[1], "%i", &a);
printf("%#x hexadecimal\n", a);
printf("%#o octal\n", a);
printf("%d decimal\n", a);
for(i = BITS - 1; i >= 0; i--)
{
printf("%c", '0' + ((a & (1 << i)) >> i));
if(!(i & 3))
printf(" ");
}
printf(" binary\n");
return 0;
}
/****************************************************************/

I'll leave it up to you to figure out how that works. 8^D

The best way to figure this stuff out is to play with it. Try these
exercises:

[1] Write a program that counts the number of bits set in an integer.
For example, the number 5 (decimal), which is 0000000000000101
(binary), has two bits set. Hint: Use the | operator to set a bit.
To test a bit, use the & operator.

[2] Write a program that will take the bits in a number and shift them
to the left end. For example, 01010110 (binary) would become
11110000 (binary).

Happy Programming!
--
K