C s Bitwise Operators

I l @ ve RuBoard

C's Bitwise Operators

C offers bitwise logical operators and shift operators. In the following examples, we will write out values in binary notation so that you can see what happens to the bits. In an actual program, you would use integer variables or constants written in the usual forms. For instance, instead of 00011001 , you would use 25 or 031 or 0x19 . For our examples, we will use 8-bit numbers , with the bits numbered 7 to 0, left to right.

Bitwise Logical Operators

The four bitwise logical operators work on integer-type data, including char. They are called bitwise because they operate on each bit independently of the bit to the left or right. Don't confuse them with the regular logical operators ( && , , and ! ), which operate on values as a whole.

One's Complement, or Bitwise Negation: ~

The unary operator ~ changes each 1 to a 0 and each 0 to a 1, as in the following example:

 ~(10011010) == (01100101) 

Suppose that val is an unsigned char assigned the value 2 . In binary, 2 is 00000010 . Then ~val has the value 11111101 , or 253 . Note that the operator does not change the value of val , just as 3 * val does not change the value of val ; val is still 2 , but it does create a new value that can be used or assigned elsewhere.

 newval = ~val; printf("%d", ~val); 

If you want to change the value of val to ~val , use simple assignment:

 val = ~val; 

Bitwise AND: &

The binary operator & produces a new value by making a bit-by-bit comparison between two operands. For each bit position, the resulting bit is 1 only if both corresponding bits in the operands are 1. (In terms of true-false, the result is true only if each of the two bit operands is true.) Therefore,

 (10010011) & (00111101) == (00010001) 

because only bits 4 and 0 are 1 in both operands.

C also has a combined bitwise AND-assignment operator: &= . The statement

 val &= 0377; 

produces the same final result as the following:

 val = val & 0377; 

Bitwise OR: ~

The binary produces a new value by making a bit-by-bit comparison between two operands. For each bit position, the resulting bit is 1 if either of the corresponding bits in the operands is 1. (In terms of true-false, the result is true if one or the other bit operands are true or if both are true.) Therefore,

 (10010011)  (00111101) == (101111111) 

because only bits 4 and 0 are 1 in both operands.

C also has a combined bitwise AND-assignment operator: &= . The statement

 val &= 0377; 

produces the same final result as the following:

 val = val & 0377; 

Bitwise OR :

The binary operator produces a new value by making a bit-by-bit comparison between two operands. For each bit position, the resulting bit is 1 if either of the corresponding bits in the operands is 1. (In terms of true-false, the result is true if one or the other bit operands are true or if both are true.) Therefore,

 (10010011)  (00111101) == (101111111) 

because all bit positions but bit 6 have the value 1 in one or the other operands.

C also has a combined bitwise OR-assignment operator: = . The statement

 val = 0377; 

produces the same final result as this:

 val = val  0377; 

Bitwise EXCLUSIVE OR : ^

The binary operator ^ makes a bit-by-bit comparison between two operands. For each bit position, the resulting bit is 1 if one or the other (but not both) of the corresponding bits in the operands is 1. (In terms of true-false, the result is true if one or the other bit operands ”but not both ” are true.) Therefore,

 (10010011) ^ (00111101) == (10101110) 

Note that because bit position 0 has the value 1 in both operands, the resulting 0 bit has value .

C also has a combined bitwise OR-assignment operator: ^= . The statement

 val ^= 0377; 

produces the same final result as this:

 val = val ^ 0377; 

Usage: Masks

The bitwise AND operator is often used with a mask. A mask is a bit pattern with some bits set to ON (1) and some bits to OFF (0). To see why a mask is called a mask, let's see what happens when a quantity is combined with a mask by using & . For example, suppose you define the symbolic constant MASK as 2 , that is, binary 00000010, with only bit number 1 being nonzero. Then the statement

 flags = flags & MASK; 

would cause all the bits of flags (except bit 1) to be set to 0 because any bit combined with 0 by using the & operator yields 0. Bit number 1 will be left unchanged. (If the bit is 1, then 1 & 1 is 1; if the bit is 0, then 0 & 1 is 0.) This process is called "using a mask" because the zeros in the mask hide the corresponding bits in flags .

Extending the analogy, you can think of the 0s in the mask as being opaque and the 1s as being transparent. The expression flags & MASK is like covering the flags bit pattern with the mask; only the bits under MASK 's 1s are visible (see Figure 15.2).

Figure 15.2. A Mask.

You can shorten the code by using the AND-assignment operator, as shown here:

 flags &= MASK; 

One common C usage is this statement:

 ch &= 0377;  /* or ch &= 0xff; */ 

The value 0377 , recall, is 11111111 in binary, as is the value 0xff . This mask leaves the final 8 bits of ch alone and sets the rest to 0. Regardless of whether the original ch is 8 bits, 16 bits, or more, the final value is trimmed to something that fits into a single byte.

Usage: Turning Bits On

Sometimes you might need to turn on particular bits in a value while leaving the remaining bits unchanged. For instance, an IBM PC controls hardware through values sent to ports. To turn on, say, the speaker, you might have to turn on 1 bit while leaving the others unchanged. You can do this with the bitwise OR operator.

For example, consider the MASK , which has bit 1 set to 1. The statement

 flags = flags  MASK; 

sets bit number 1 in flags to 1 and leaves all the other bits unchanged. This follows because any bit combined with 0 by using the operator is itself, and any bit combined with 1 by using the operator is 1.

For short, you can use the bitwise OR-assignment operator:

 flags = MASK; 

This, too, sets to 1 those bits in flags that are also on in MASK , leaving the other bits unchanged.

Usage: Turning Bits Off

Just as it's useful to be able to turn on particular bits without disturbing the other bits, it's useful to be able to turn them off. Suppose you want to turn off bit 1 in the variable flags . Once again, MASK has only the 1 bit turned on. You can do this:

 flags = flags & ~MASK; 

Because MASK is all 0s except for bit 1, ~MASK is all 1s except for bit 1. A 1 combined with any bit by using & is that bit, so the statement leaves all the bits other than bit 1 unchanged. Also, a 0 combined with any bit by using & is 0, so bit 1 is set to 0 regardless of its original value.

You can use this short form instead:

 flags &= ~MASK; 

Usage: Toggling Bits

Toggling a bit means turning it off if it is on, and turning it on if it is off. You can use the bitwise EXCLUSIVE OR operator to toggle a bit. The idea is that if b is a bit setting (1 or 0), then 1 ^ b is if b is 1 and is 1 if b is . Also 0 ^ b is b , regardless of its value. Therefore, if you combine a value with a mask by using ^ , values corresponding to 1s in the mask are toggled, and values corresponding to 0s in the mask are unaltered. To toggle bit 1 in flag , you can do either of the following:

 flag = flag ^ MASK; flag ^= MASK; 

Usage: Checking the Value of a Bit

You've seen how to change the values of bits. Suppose, instead, that you want to check the value of a bit. For example, does flag have bit 1 set to 1? You shouldn't simply compare flag to MASK .

 if (flag == MASK) puts("Wow!");    /* doesn't work right */ 

Even if bit 1 in flag is set to 1, the other bit setting in flag can make the comparison untrue. Instead, you must first mask the other bits in flag so that you compare only bit 1 of flag with MASK :

 if ((flag & MASK) == MASK) puts("Wow!"); 

The bitwise operators have lower precedence than == , so the parentheses around flag & MASK are needed.

Bitwise Shift Operators

Now let's look at C's shift operators. The bitwise shift operators shift bits to the left or right. Again, we will write binary numbers explicitly to show the mechanics.

Left Shift: <<

The << left shift operator shifts the bits of the value of the left operand to the left by the number of places given by the right operand. The vacated positions are filled with 0s, and bits moved past the end of the left operand are lost. In this statement, then,

 (10001010) << 2 == (00101000) 

each bit is moved two places to the left.

This operation produces a new bit value, but it doesn't change its operands. For example, suppose stonk is 1 . Then stonk «2 is 4 , but stonk is still 1 . You can use the leftshift assignment operator ( «== ) to actually change a variable's value. This operator shifts the bit in the variable to its left by the number of places given by the right-hand value.

 int stonk = 1; int onkoo; onkoo = stonk << 2;   /* assigns 4 to onkoo */ stonk <<== 2;          /* changes stonk to 4 */ 

Right Shift: >>

The >> right shift operator shifts the bits of the value of the left operand to the right by the number of places given by the right operand. Bits moved past the right end of the left operand are lost. For unsigned types, the places vacated at the left end are replaced by 0s. For signed types, the result is machine dependent. The vacated places may be filled with 0s, or they may be filled with copies of the sign (leftmost) bit:

 (10001010) >> 2 == (00100010)  /* signed value, some systems  */ (10001010) >> 2 == (11100010)  /* signed value, other systems */ 

For an unsigned value, you have the following:

 (10001010) >> 2 == (00100010)  /* unsigned value, all system  */ 

Each bit is moved two places to the right, and the vacated places are filled with 0s.

The right-shift assignment operator ( >>== ) shifts the bits in the lefthand variable to the right by the indicated number of places, as shown here:

 int sweet = 16; int ooosw; ooosw = sweet >> 3;  /* ooosw = 2, sweet still 16 */ sweet >>=3;          /* sweet changed to 2        */ 

Usage: Bitwise Shift Operators

The bitwise shift operators can provide swift, efficient (depending on the hardware) multiplication and division by powers of 2.

 number << n              Multiplies number by 2 to the nth power. number >> n                Divides number by 2 to the nth power if number is not negative. 

These shift operations are analogous to the decimal system procedure of shifting the decimal point to multiply or divide by 10.

The shift operators can also be used to extract groups of bits from larger units. Suppose, for example, you use an unsigned long value to represent color values, with the low-order byte holding the red intensity, the next byte holding the green intensity, and the third byte holding the blue intensity. Suppose you then wanted to store the intensity of each color in its own unsigned char variable. Then you could do something like this:

 #define BYTE_MASK 0xff unsigned long color = 0x002a162f; unsigned char blue, green, red; red = color & BYTE_MASK; green = (color >> 8) & BYTE_MASK; blue = (color >> 16) & BYTE_MASK; 

The code uses the right-shift operator to move the 8-bit color value to the low-order byte, and then uses the mask technique to assign the low-order byte to the desired variable.

Programming Example

In Chapter 9, "Functions," we used recursion to write a program to convert numbers to a binary representation. Now we'll solve the same problem by using the bitwise operators. The program in Listing 15.1 reads an integer from the keyboard and passes it and a string address to a function called itobs() (for integer to binary string, of course). This function then uses the bitwise operators to figure out the correct pattern of 1s and 0s to put into the string.

Listing 15.1 The binary.c program.

 /* binary.c -- using bit operations to display binary */ #include <stdio.h>; char * itobs(int, char *); int main(void) {    char bin_str[8 * sizeof(int) + 1];    int number;    puts("Enter integers and see them in binary.");    puts("Non-numeric input terminates program.");    while (scanf("%d", &number) == 1)         printf("%d is %s\n", number, itobs(number,bin_str));    return 0; } char * itobs(int n, char * ps) {    int i;    static int size = 8 * sizeof(int);    for (i = size - 1; i >= 0; i--, n >>= 1)         ps[i] = (01 & n) + '0';    ps[size] = ' 
 /* binary.c -- using bit operations to display binary */ #include <stdio.h>; char * itobs(int, char *); int main(void) { char bin_str[8 * sizeof(int) + 1]; int number; puts("Enter integers and see them in binary."); puts("Non-numeric input terminates program."); while (scanf("%d", &number) == 1) printf("%d is %s\n", number, itobs(number,bin_str)); return 0; } char * itobs(int n, char * ps) { int i; static int size = 8 * sizeof(int); for (i = size - 1; i >= 0; i--, n >>= 1) ps[i] = (01 & n) + '0'; ps[ size ] = '\0'; return ps; } 
 ';    return ps; } 

Listing 15.1 assumes that the system uses 8 bits to a byte. Therefore, the expression 8 * sizeof(int) is the number of bits in an int . The bin_str array has that many elements plus 1 to allow for the terminating null character.

The itobs() function returns the same address passed to it, so you can use the function as, say, an argument to printf() . The first time through the for loop, the function evaluates the quantity 01 & n . The term 01 is the octal representation of a mask with all but the zero bit set to 0. Therefore, 01 & n is just the value of the final bit in n . This value is a or a 1 , but for the array, you need the character '0' or the character '1' . Adding the ASCII code for '0' accomplishes that conversion. The result is placed in the next-to-last element of the array. (The last element is reserved for the null character.)

By the way, you can just as well use 1 & n as 01 & n . Using octal 1 instead of decimal 1 just makes the mood a bit more computerish.

Then the loop executes the statements i-- and n >>= 1 . The first statement moves you one element earlier in the array, and the second shifts the bits in n over one position to the right. The next time through the loop, then, you find the value of the new rightmost bit. The corresponding digit character is then placed in the element preceding the final digit. In this fashion, the function fills the array from right to left.

Here is a sample run:

 Enter integers and see them in binary. Non-numeric input terminates program. 7 7 is 00000000000000000000000000000111 1999 1999 is 00000000000000000000011111001111 -1 -1 is 11111111111111111111111111111111 32123 32123 is 00000000000000000111110101111011 q 

Another Example

Let's work through one more example. The goal this time is to write a function that inverts the last n bits in a value, with both n and the value being function arguments.

The ~ operator inverts bits, but it inverts all the bits in a byte, not just a select few. However, the ^ operator (exclusive or), as you have seen, can be used to toggle individual bits. Suppose you create a mask with the last n bits set to 1 and the remaining bits set to 0. Then applying ^ to that mask and a value toggles, or inverts, the last n bits, leaving the other bits unchanged. That's the approach used here:

 int invert_end(int num, int bits) {     int mask = 0;     int bitval = 1;     while (bits-- > 0)     {         mask = bitval;         bitval = 1;     }     return num ^ mask; } 

The while loop creates the mask. Initially, mask has all its bits set to . The first pass through the loop sets bit 0 to 1 and then increases the value of bitval to 2 ; that is, it sets bit 0 to and bit 1 to 1 . The next pass through then sets bit 1 of mask to 1 , and so on. Finally, the num ^ mask operation produces the desired result.

To test the function, you can slip it into the preceding program, as shown in Listing 15.2.

Listing 15.2 The invert4.c program.

 /*  invert4.c -- inverts last 4 bits of integers */ #include <stdio.h> char * itobs(int n, char * ps); int invert_end(int num, int bits); int main(void) {     char bin_str[8 * sizeof(int) + 1];     int number;     puts("Enter integers and see them in binary.");     puts("Non-numeric input terminates program.");     while (scanf("%d", &number) == 1)     {         printf("%d is %s\n", number, itobs(number,bin_str));         printf("Inverting the last 4 bits gives\n%s\n",                   itobs(invert_end(number,4),bin_str));     }     return 0; } char * itobs(int n, char * ps) {      int i;      static int size = 8 * sizeof(int);      for (i = size - 1; i >= 0; i--, n >>= 1)           ps[i] = (01 & n) + '0';      ps[size] = ' 
 /* invert4.c -- inverts last 4 bits of integers */ #include <stdio.h> char * itobs(int n, char * ps); int invert_end(int num, int bits); int main(void) { char bin_str[8 * sizeof(int) + 1]; int number; puts("Enter integers and see them in binary."); puts("Non-numeric input terminates program."); while (scanf("%d", &number) == 1) { printf("%d is %s\n", number, itobs(number,bin_str)); printf("Inverting the last 4 bits gives\n%s\n", itobs(invert_end(number,4),bin_str)); } return 0; } char * itobs(int n, char * ps) { int i; static int size = 8 * sizeof(int); for (i = size - 1; i >= 0; i--, n >>= 1) ps[i] = (01 & n) + '0'; ps[size] = '\0'; return ps; } int invert_end(int num, int bits) { int mask = 0; int bitval = 1; while (bits-- > 0) { mask = bitval; bitval  «= 1; } return num ^ mask; } 
 ';      return ps; } int invert_end(int num, int bits) {     int mask = 0;     int bitval = 1;     while (bits-- > 0)     {         mask = bitval;         bitval = 1;     }     return num ^ mask; } 

Here's a sample run:

 Enter integers and see them in binary. Non-numeric input terminates program. 7 7 is 00000000000000000000000000000111 Inverting the last 4 bits gives 00000000000000000000000000001000 255 255 is 00000000000000000000000011111111 Inverting the last 4 bits gives 00000000000000000000000011110000 q 

I l @ ve RuBoard