Bit-Level Operations in C

Technical Overview

One of the reasons why C has become so popular is that it allows the programmer to do many types of machine-level applications without resorting to using machine language as the vehicle for programming. One example of that is C's ability to work with memory addresses. Another example, or class of examples, consists of C constructs for bit-level operations, which will be described here.

AND and OR Operators

C includes the bitwise-AND operator & and the bitwise-OR operator |. To AND two bits together, one merely multiplies them: 0 AND 0 = 0, 1 AND 0 = 0, 0 AND 1 = 0, 1 AND 1 = 1. To OR two bits together, we just add them, except that 1 OR 1 is equal to 1, not 2: 0 OR 0 = 0, 1 OR 0 = 1, 0 or 1 = 1, 1 or 1 = 1.

Note that

AND-ing by a 1 simply copies the bit value
OR-ing by a 0 simply copies the bit value
AND-ing by a 0 results in a 0, not matter what the original bit value was
OR-ing by a 1 results in a 1, not matter what the original bit value was
The AND operator is useful for

(a)
putting 0s in certain bit positions of a variable, while retaining whatever original values were in the other bit positions
(b)
testing whether certain bit positions within a variable contain 1s or 0s
In the next few examples, suppose the variable X is of type int.

As an example of (a), suppose we wish to put 0s in Bit Positions 3 and 2 (the rightmost bit position being Bit Position 0), and suppose we have a machine/compiler combination which implements int variables as 4-byte quantities (again, this is typical for most workstations today). We would accomplish our goal with the statement

X &= 0xfffffff3;
Here is why: First, note that

X &= 0xfffffff3
is just a short form of

X = X & 0xfffffff3
(like X += 5 vs. X = X + 5). So we are AND-ing 0xfffffff3 with X and putting the result back in X. The constant 0xfffffff3 is, in bit form,

11111111111111111111111111110011
Most of the bits here are 1s, and since, as mentioned earlier, AND-ing by a 1 produces no change, most bits in X will not change. Only the bits at Bit Positions 3 and 2 will potentially change: They will change to 0s if they were 1s (or stay at 0s if they were 0s).

For example, after executing the statements

X = 29;
X &= 0xfffffff3;
X will have the value 17 (try this yourself on the machine, and make sure you understand).

By the way, the value to be AND-ed with X, in this case 0xfffffff3, is called a mask. To see why, think of what happens when you wish to paint the walls of a room. You would like to cover up the electrical sockets so that they don't get painted; you can do this with masking tape. Well, in the example above, we wished to ``cover up'' all the bits except those at Bit Positions 3 and 2, so we AND-ed them with 1s, so that they would not change.

As an example of (b), suppose we wish to set Z = 12 if there is a 1 in Bit Position 5 of X. We could do this with the statement

if (X & 0x00000020) Z = 12;
Here is why this statement accomplishes this goal: The mask 0x00000020 has 0s everywhere except in Bit Position 5, where there is a 1. Recall from above that AND-ing with a 0 produces a 0, no matter what value it is AND-ed with, while AND-ing with a 1 results in copying the bit value. So the quantity X & 0x00000020 will have 0s everywhere except at Bit Position 5, where there will be a copy of X's original Bit 5. If the latter is a 1, then X & 0x00000020 will be nonzero (0x00000010, to be specific), and since any nonzero value is condidered `true', Z = 12 will be executed.

OR-ing is used to put 1s at specific bit positions. You should verify, and make sure you understand, that after the statements

X = 29;
X |= 0x00000020;
are executed, X will be equal to 61.

Shift Operators

The operators << and >> shift the bits in a variable toward the left or toward the right, respectively. Suppose for example that X and Y are of type int, and we execute

X = 5;
Y = X << 3;
Then (say on the CAE machines) X will be, in bit form,

00000000000000000000000000000101
All these bits will be shifted left by 3 positions, and the result placed in Y. The latter will now be

00000000000000000000000000101000
which has the value 40.

footnote: Note that since we are tacking three 0s on the right end, and we are working in base-2, we are in effect multiplying by . (In base-10, tacking on a 0 on the right does a multiplication by 10, e.g. 52 to 520, so in base-2, appending a 0 on the right does a multiplication by 2.) Thus since X was 5, Y will be 40.
Note that the bits on the left end disappear. This may create problems. For example, shifting may turn a positive number into a negative one, or vice versa, since the leftmost bit of a number tells its sign. This presents no problem, though, for variables of type unsigned, so shift operations are typically done on variables of that type, not of type int.

Bit Fields

These arise in a special type of struct, which allows one to assign variable names to groups of bits within a variable. We will not go into this here.

http://heather.cs.ucdavis.edu/~matloff/UnixAndC/CLanguage/BitOps.html