Now that you have learned some preliminaries, it’s time to discuss the various bit opera- tors that are available. The operators that C provides for manipulating bits are presented in Table 12.1.
Table 12.1 Bit Operators
All the operators listed in Table 12.1, with the exception of the ones complement opera- tor ~, are binary operators and as such take two operands. Bit operations can be per- formed on any type of integer value in C—be it short, long, long long, and signed or unsigned—and on characters, but cannot be performed on floating-point values.
1. The Bitwise AND Operator
When two values are ANDed in C, the binary representations of the values are com- pared bit by bit. Each corresponding bit that is a 1 in the first value and a 1 in the sec- ond value produces a 1 in the corresponding bit position of the result; anything else produces a 0. If b1 and b2 represent corresponding bits of the two operands, then the following table, called a truth table, shows the result of b1 ANDed with b2 for all possible values of b1 and b2.
So, for example, if w1 and w2 are defined as short ints, and w1 is set equal to 25 and w2 is set equal to 77, then the C statement
w3 = w1 & w2;
assigns the value 9 to w3. This can be more easily seen by treating the values of w1, w2, and w3 as binary numbers. Assume that you are dealing with a short int size of 16 bits.
If you think about the way the logical AND operator && works (true only if both operands are true), you will be able to more easily remember the way the bitwise AND operator works. Incidentally, make sure that you don’t get these two operators confused! The logical AND operator && is used in logical expressions for producing a true/false result; it does not perform a bitwise AND.
Bitwise ANDing is frequently used for masking operations. That is, this operator can be used to easily set specific bits of a data item to 0. For example, the statement
w3 = w1 & 3;
assigns to w3 the value of w1 bitwise ANDed with the constant 3. This has the effect of setting all of the bits in w3, other than the rightmost two bits, to 0, and of preserving the rightmost two bits from w1.
As with all binary arithmetic operators in C, the binary bit operators can also be used as assignment operators by tacking on an equal sign. So the statement
word &= 15;
performs the same function as
word = word & 15;
and has the effect of setting all but the rightmost four bits of word to 0.
When using constants in performing bitwise operations, it is usually more convenient to express the constants in either octal or hexadecimal notation. The choice as to which to use is usually influenced by the size of the data with which you are dealing. For example, when dealing with 32-bit computers, hexadecimal notation is often used because 32 is an even multiple of 4 (the number of bits in a hexadecimal digit).
Program 12.1 is presented to illustrate the bitwise AND operator. Because you are dealing with only positive values in this program, all integers have been declared as unsigned int variables.
Program 12.1 The Bitwise AND Operator
// Program to demonstrate the bitwise AND operator
#include <stdio.h>
int main (void)
{
unsigned int word1 = 077u, word2 = 0150u, word3 = 0210u;
printf (“%o “, word1 & word2);
printf (“%o “, word1 & word1);
printf (“%o “, word1 & word2 & word3);
printf (“%o\n”, word1 & 1);
return 0;
}
Program 12.1 Output
50 77 10 1
Recall that if an integer constant has a leading 0, it represents an octal (base 8) constant in C. Therefore, the three unsigned ints, word1, word2, and word3, are given initial octal values of 077, 0150, and 0210, respectively. Recall also from Chapter 4 that if a u or U follows an integer constant, it is treated as unsigned.
The first printf call displays octal 50 as the result of bitwise ANDing word1 with word2. The following depicts how this value was calculated:
Only the rightmost nine bits of the previous values are shown because all bits to the left are 0. The binary numbers have been arranged in groups of three bits to make it easier to translate back and forth between binary and octal.
The second printf call results in the display of octal 77, which is the result of ANDing word1 with itself. By definition, any quantity x, when ANDed with itself, pro- duces x.
The third printf call displays the result of ANDing word1, word2, and word3 togeth- er. The operation of bitwise ANDing is such that it makes no difference whether an expression such as a & b & c is evaluated as (a & b) & c or as a & (b & c), but for the record, evaluation proceeds from left to right. It is left as an exercise to you to verify that the displayed result of octal 10 is the correct result of ANDing word1 with word2 with word3.
The final printf call has the effect of extracting the rightmost bit of word1. This is actually another way of testing if an integer is even or odd because that rightmost bit of any odd integer is 1 and of any even integer is 0. Therefore when the if statement
if ( word1 & 1 )
…
is executed, the expression is true if word1 is odd (because the result of the AND opera- tion is 1) and false if it is even (because the result of the AND operation is 0). (Note: On machines that use a ones complement representation for numbers, this does not work for negative integers.)
2. The Bitwise Inclusive-OR Operator
When two values are bitwise Inclusive-ORed in C, the binary representation of the two values are once again compared bit by bit. This time, each bit that is a 1 in the first value or a 1 in the second value produces a 1 in the corresponding bit of the result. The truth table for the Inclusive-OR operator is shown next.
So, if w1 is an unsigned int equal to octal 0431 and w2 is an unsigned int equal to octal 0152, then a bitwise Inclusive-OR of w1 and w2 produces a result of octal 0573 as shown:
As was pointed out with the bitwise AND operator, be sure to not confuse the opera- tion of bitwise ORing (|) with that of logical ORing (||), the latter operation being used to determine if either of two logical values is true.
Bitwise Inclusive-ORing, frequently called just bitwise ORing, is used to set some specified bits of a word to 1. For example, the statement
w1 = w1 | 07;
sets the three rightmost bits of w1 to 1, regardless of the state of these bits before the operation was performed. Of course, you could have used a special assignment operator in the statement, as follows:
w1 |= 07;
Presentation of a program example illustrating the use of the Inclusive-OR operator is deferred until later in this chapter.
3. The Bitwise Exclusive-OR Operator
The bitwise Exclusive-OR operator, which is often called the XOR operator, works as follows: For corresponding bits of the two operands, if either bit is a 1—but not both— the corresponding bit of the result is a 1; otherwise it is a 0. The truth table for this operator is as shown.
If w1 and w2 were set equal to octal 0536 and octal 0266, respectively, then the result of w1 Exclusive-ORed with w2 would be octal 0750, as illustrated:
One interesting property of the Exclusive-OR operator is that any value Exclusive- ORed with itself produces 0. Historically, this trick was often used by assembly language programmers as a fast way to set a value to 0 or to compare two values to see if they were equal. This method is not recommended for use in C programs, however, as it doesn’t save time and most likely makes the program more obscure.
Another interesting application of the Exclusive-OR operator is that it can be used to effectively exchange two values without the need for an extra memory location.You know that you would normally interchange two integers called i1 and i2 with a sequence of statements such as
temp = i1;
i1 = i2;
i2 = temp;
Using the Exclusive-OR operator, you can exchange values without the need of the temporary storage location:
i1 ^= i2;
i2 ^= i1;
i1 ^= i2;
It is left as an exercise to you to verify that the previous statements do in fact succeed in interchanging the values of i1 and i2.
4. The Ones Complement Operator
The ones complement operator is a unary operator, and its effect is to simply “flip” the bits of its operand. Each bit of the operand that is a 1 is changed to a 0, and each bit that is a 0 is changed to a 1. The truth table is shown next simply for the sake of complete- ness.
If w1 is a short int that is 16 bits long, and is set equal to octal 0122457, then taking the ones complement of this value produces a result of octal 0055320:
The ones complement operator (~) should not be confused with the arithmetic minus operator (–) or with the logical negation operator (!). So if w1 is defined as an int, and set equal to 0, then –w1 still results in 0. If you apply the ones complement operator to w1, you end up with w1 being set to all ones, which is –1 when treated as a signed value in twos complement notation. Finally, applying the logical negation operator to w1 pro- duces the result true (1) because w1 is false (0).
The ones complement operator is useful when you don’t know the precise bit size of the quantity that you are dealing with in an operation. Its use can help make a program more portable—in other words, less dependent on the particular computer on which the program is running and, therefore, easier to get running on a different machine. For example, to set the low-order bit of an int called w1 to 0, you can AND w1 with an int consisting of all 1s except for a single 0 in the rightmost bit. So a statement in C such as
w1 &= 0xFFFFFFFE;
works fine on machines in which an integer is represented by 32 bits.
If you replace the preceding statement with
w1 &= ~1;
w1 gets ANDed with the correct value on any machine because the ones complement of 1 is calculated and consists of as many leftmost one bits as are necessary to fill the size of an int (31 leftmost bits on a 32-bit integer system).
Program 12.2 summarizes the various bitwise operators presented thus far. Before proceeding, however, it is important to mention the precedences of the various opera- tors. The AND, OR, and Exclusive-OR operators each have lower precedence than any of the arithmetic or relational operators, but higher precedence than the logical AND and logical OR operators. The bitwise AND is higher in precedence than the bitwise Exclusive-OR, which in turn is higher in precedence than the bitwise OR. The unary ones complement operator has higher precedence than any binary operator. For a sum- mary of these operator precedences, see Appendix A, “C Language Summary.”
Program 12.2 Illustrate Bitwise Operators
/* Program to illustrate bitwise operators */
#include <stdio.h>
int main (void)
{
unsigned int w1 = 0525u, w2 = 0707u, w3 = 0122u;
printf (“%o %o %o\n”, w1 & w2, w1 | w2, w1 ^ w2);
printf (“%o %o %o\n”, ~w1, ~w2, ~w3);
printf (“%o %o %o\n”, w1 ^ w1, w1 & ~w2, w1 | w2 | w3);
printf (“%o %o\n”, w1 | w2 & w3, w1 | w2 & ~w3);
printf (“%o %o\n”, ~(~w1 & ~w2), ~(~w1 | ~w2));
w1 ^= w2;
w2 ^= w1;
w1 ^= w2;
printf (“w1 = %o, w2 = %o\n”, w1, w2);
return 0;
}
Program 12.2 Output
You should work out each of the operations from Program 12.2 with a paper and pencil to verify that you understand how the results were obtained. The program was run on a computer that uses 32 bits to represent an int.
In the fourth printf call, it is important to remember that the bitwise AND operator has higher precedence than the bitwise OR, because this fact influences the resulting value of the expression.
The fifth printf call illustrates DeMorgan’s rule, namely that ~(~a & ~b) is equal to a | b and that ~(~a | ~b) is equal to a & b. The sequence of statements that follow next in the program verifies that the exchange operation works as discussed in “The Bitwise Exclusive-OR Operator” section.
5. The Left Shift Operator
When a left shift operation is performed on a value, the bits contained in the value are literally shifted to the left. Associated with this operation is the number of places (bits) that the value is to be shifted. Bits that are shifted out through the high-order bit of the data item are lost, and 0s are always shifted in through the low-order bit of the value. So if w1 is equal to 3, then the expression
w1 = w1 << 1;
which can also be expressed as
w1 <<= 1;
results in 3 being shifted one place to the left, which results in 6 being assigned to w1:
w1 … 000 011 03
w1 << 1 … 000 110 06
The operand on the left of the << operator is the value to be shifted, whereas the operand on the right is the number of bit positions by which the value is to be shifted. If you shift w1 one more place to the left, you end up with octal 014 as the value of w1:
w1 … 000 110 06
w1 << 1 … 001 100 014
Left shifting actually has the effect of multiplying the value that is shifted by two. In fact, some C compilers automatically perform multiplication by a power of two by left shift- ing the value the appropriate number of places because shifting is a much faster opera- tion than multiplication on most computers.
A program example illustrating the left shift operator is presented after the right shift operator has been described.
6. The Right Shift Operator
As implied from its name, the right shift operator >> shifts the bits of a value to the right. Bits shifted out of the low-order bit of the value are lost. Right shifting an unsigned value always results in 0s being shifted in on the left; that is, through the high-order bits. What is shifted in on the left for signed values depends on the sign of the value that is being shifted and also on how this operation is implemented on your computer system. If the sign bit is 0 (meaning the value is positive), 0s are shifted in regardless of which machine you are running. However, if the sign bit is 1, on some machines 1s are shifted in, and on others 0s are shifted in. This former type of operation is known as an arithmetic right shift, whereas the latter is known as a logical right shift.
Never make any assumptions about whether a system implements an arithmetic or a logical right shift. A program that shifts signed values right might work correctly on one system but fail on another due to this type of assumption.
If w1 is an unsigned int, which is represented in 32 bits, and w1 is set equal to hexa- decimal F777EE22, then shifting w1 one place to the right with the statement
w1 >>= 1;
sets w1 equal to hexadecimal 7BBBF711.
If w1 were declared to be a (signed) int, the same result would be produced on some computers; on others, the result would be FBBBF711 if the operation were performed as an arithmetic right shift.
It should be noted that the C language does not produce a defined result if an attempt is made to shift a value to the left or right by an amount that is greater than or equal to the number of bits in the size of the data item. So, on a machine that represents integers in 32 bits, for example, shifting an integer to the left or right by 32 or more bits is not guaranteed to produce a defined result in your program.You should also note that if you shift a value by a negative amount, the result is also undefined.
7. A Shift Function
Now, it’s time to put the left and right shift operators to work in an actual program example, as shown in Program 12.3. Some computers have a single machine instruction to shift a value to the left if the shift count is positive and to the right if the shift count is negative. Now, write a function in C to mimic this type of operation.You can have the function take two arguments: the value to be shifted and the shift count. If the shift count is positive, the value is shifted left the designated number of places; otherwise, the value is shifted right the number of places as specified by the absolute value of the shift count.
Program 12.3 Implementing a Shift Function
// Function to shift an unsigned int left if
// the count is positive, and right if negative
#include <stdio.h>
unsigned int shift (unsigned int value, int n)
{
if ( n > 0 ) // left shift
value <<= n;
else // right shift
value >>= -n;
return value;
}
int main (void)
{
unsigned int w1 = 0177777u, w2 = 0444u;
unsigned int shift (unsigned int value, int n);
printf (“%o\t%o\n”, shift (w1, 5), w1 << 5);
printf (“%o\t%o\n”, shift (w1, -6), w1 >> 6);
printf (“%o\t%o\n”, shift (w2, 0), w2 >> 0);
printf (“%o\n”, shift (shift (w1, -3), 3));
return 0;
}
Program 12.3 Output
7777740 7777740
1777 1777
444 444
177770
The shift function shown in Program 12.3 declares the type of the argument value to be unsigned int, thus ensuring that a right shift of value will be zero filled; in other words, performed as a logical right shift.
If the value of n, which is the shift count, is greater than zero, the function shifts value left n bits. If n is negative (or zero), the function performs a right shift, where the number of places that value is shifted is obtained by negating the value of n.
The first call to the shift function from the main routine specifies that the value of w1 is to be left shifted five bits. The printf call that displays the result of the call to the shift function also displays the result of directly shifting w1 left five places so that these values can be compared.
The second call to the shift function has the effect of shifting w1 six places to the right. The result returned by the function is identical to the result obtained by directly shifting w1 to the right six places, as verified by the program’s output.
In the third call to shift,a shift count of zero is specified. In this case, the shift func- tion performs a right shift of value by zero bits, which, as you can see from the program’s output, has no effect on the value.
The final printf call illustrates nested function calls to the shift function. The innermost call to shift is executed first. This call specifies that w1 is to be shifted right three places. The result of this function call, which is 0017777, is then passed to the shift function to be shifted to the left three places. As you can see from the program’s output, this has the net effect of setting the low-order three bits of w1 to 0. (Of course, you know by now that this could also have been done by simply ANDing w1 with ~7.)
8. Rotating Bits
For the next program example, which ties together some of the bit operations presented in this chapter, you will develop a function to rotate a value to the left or right. The process of rotation is similar to shifting, except that when a value is rotated to the left, the bits that are shifted out of the high-order bits are shifted back into the low-order bits. When a value is rotated to the right, the bits that are shifted out of the low-order bits of the value are shifted back into the high-order bits. So, if you are dealing with 32-bit unsigned integers, the value hexadecimal 80000000 rotated to the left by one bit pro- duces hexadecimal 00000001 because the 1 from the sign bit that is normally lost by a left shift of one bit is brought around and shifted back into the low-order bit.
Your function takes two arguments: the first, the value to be rotated, and the second, the number of bits by which the object is to be rotated. If this second argument is posi- tive, you rotate the value to the left; otherwise, you rotate the value to the right.
You can adopt a fairly straightforward approach to implementing your rotate func- tion. For example, to compute the result of rotating x to the left by n bits, where x is of type int and n ranges from 0 to the number of bits in an int minus 1, you can extract the leftmost n bits of x, shift x to the left by n bits, and then put the extracted bits back into x at the right. A similar algorithm also can be used to implement the right rotate function.
Program 12.4 implements the rotate function using the algorithm described previ- ously. This function makes the assumption that an int uses 32 bits on the computer. Exercises at the end of the chapter show one way to write this function so that this assumption does not have to be made.
Program 12.4 Implementing a Rotate Function
// Program to illustrate rotation of integers
#include <stdio.h>
int main (void)
{
unsigned int w1 = 0xabcdef00u, w2 = 0xffff1122u;
unsigned int rotate (unsigned int value, int n);
printf (“%x\n”, rotate (w1, 8));
printf (“%x\n”, rotate (w1, -16));
printf (“%x\n”, rotate (w2, 4));
printf (“%x\n”, rotate (w2, -2));
printf (“%x\n”, rotate (w1, 0));
printf (“%x\n”, rotate (w1, 44));
return 0;
}
// Function to rotate an unsigned int left or right
unsigned int rotate (unsigned int value, int n)
{
unsigned int result, bits;
// scale down the shift count to a defined range if ( n > 0 )
n = n % 32;
else
n = -(-n % 32);
if ( n == 0 )
result = value;
else if ( n > 0 ) { // left rotate
bits = value >> (32 – n);
result = value << n | bits;
}
else { // right rotate
n = -n;
bits = value << (32 – n);
result = value >> n | bits;
}
return result;
}
Program 12.4 Output
cdef00ab
ef00abcd
fff1122f
Program 12.4 Continued
bfffc448
abcdef00
def00abc
The function first ensures that the shift count, n, is valid. The code
if ( n > 0 )
n = n % 32;
else
n = -(-n % 32);
checks first to see if n is positive. If it is, the value of n modulo the size of an int (assumed to be 32 in this example) is calculated and stored back inside n. This places the shift count in the range of 0 through 31. If n is negative, its value is negated before the modulus operator is applied. This is done because C does not define the sign of the result of applying the modulus operator to a negative value.Your machine can produce either a positive or negative result. By negating the value first, you ensure the result is positive.You then apply the unary minus operator to the result to turn it negative again; that is, within the range of values –31 through 0.
If the adjusted shift count is 0, the function simply assigns value to result. Otherwise, it proceeds with the rotation.
An n-bit rotation to the left is divided into three steps by the function. First, the n leftmost bits of value are extracted and shifted to the right. This is done by shifting value to the right by the size of an int (in our case, 32) minus n. Next, value is shifted n bits to the left, and finally, the extracted bits are ORed back in. A similar procedure is followed to rotate value to the right.
In the main routine, note the use of hexadecimal notation for a change. The first call to the rotate function specifies that the value of w1 is to be rotated eight bits to the left. As can be seen from the program’s output, the hexadecimal value cdef00ab is returned by the rotate function, which is in fact abcdef00 rotated to the left eight bits.
The second call to the rotate function has the effect of rotating the value of w1 16 bits to the right.
The next two calls to the rotate function do similar things with the value of w2 and are fairly self-explanatory. The next-to-last call to rotate specifies a rotate count of 0. The program’s output verifies that in such a case the function simply returns the value unchanged.
The final call to rotate specifies a left rotate 44 places. This has the net effect of rotating the value left 12 bits (44 % 32 is 12).
Source: Kochan Stephen G. (2004), Programming in C: A Complete Introduction to the C Programming Language, Sams; Subsequent edition.