CSC 161 Schedule Readings Labs & Projects Homework Deadlines Resources

Bitwise Operations and Unions

Now that we know how numeric data is represented as a sequence of bits, we will find it useful to manipulate these bits in several different ways; several bitwise operations help us in this regard. As in Scheme, sometimes we need a modest amount of flexibility with respect to the data type used in particular circumstances; the union type accomplishes this. You will learn about both in the following textbook readings.

The reading below makes reference to the struct feature of the C programming language, which we will cover in detail after the next module. For now, you may infer what you can about them from the reading, but you should not worry about understanding all the details.

Bitwise Operations

The C programming language contains six bitwise operations that may be applied to any integer type, including char, int, and long. We know each of these types consists of some number of bits, which are individually binary values, so it should not come as a surprise to know that the logical operators we've learned so far, such as AND and OR, can be applied to each positionally aligned pair of bits. For example, whereas a && b evaluates to true (really 1) if both a and b are non-zero, using the bitwise operator a & b compares the corresponding bits of a and b, yielding a 1 in positions where both operands' bits are 1 (i.e., true), and a 0 (i.e., false) in all other bit positions.

Bitwise Operators
Operation Meaning
& Bitwise AND
| Bitwise OR
^ Bitwise Exclusive OR (XOR)
~ Bitwise NOT
<< Shift Left
>> Shift Right

In considering the bitwise operators, we think of a binary bit 1 as "true" and the binary bit value 0 as "false." . The so-called "exclusive OR", often called "XOR" is true when either one or the other of the operands is true, but is false when both are true or both are false. The negation operator simply flips (or inverts) all of the bits in the value. Both the shift left (<<) and shift right (>>) operators move all bits by a specified number of places. Bits moved beyond the end of storage are lost, and bits introduced at the start of the shift become 0.

Suppose num1 is the 8-bit integer 10010110, and num2 is the 8-bit integer 00001111. When these integers are used with the bitwise operations, each bit of num1 is paired with the corresponding bit of num2. The result is an 8-bit integer, where the resulting bits are derived from the given bitwise operation for each bit.

Expression Result
num1 & num2 00000110
num1 | num2 10011111
num1 ^ num2 10011001
~num1 01101001
~num2 11110000
num1<<2 01011000
num2<<3 01111000
num1>>2 00100101
num2>>3 00000001

Bit shifting deserves a bit more discussion. Shifting left always produces zeros to fill in the spaces left vacant by the bits that have moved. However, shifting to the right may either produce zeros (called a logical shift) or ones IF the leading bit is a one (called an arithmetic shift, since it preserves the sign and remains the equivalent of dividing by 2, even when the operand is negative). The difference stems from the fact that both operations are often desirable but must be supported by the underlying hardware. C's designers have left this behavior "compiler dependent", meaning the programmer won't be able to predict what the outcome of such an expression will be when the leading bit is 1 in a right shift.

Bit Manipulation

Although many applications work with variables at the level of numbers, characters, or strings, some processing may benefit by working directly at a low level with specific bits. Two examples of this processing follow.

Multiplication and Division by 2i

The reading on the representation of integers observed that the bits in an integer increased by a factor of two in moving from right to left. Thus, given the representation for a positive integer n, the representation for 2n can be obtained by shifting all bits for n to the left 1 position—inserting 0 as the rightmost bit. Similarly, shifting the bits of n two places to the left (inserting two zeros on the right) yields the bit representation for the number 4n.

More generally, shifting the bit representation of the number n to the left by i bits (by inserting i bits at the right) yields the binary representation of the number n × 2i.

Similarly, shifting the binary representation of the number n to the right by 1 place (and dropping the rightmost bit) has the effect of dividing the number by 2 (and ignoring any remainder).

Altogether, shifting left or right is a particularly efficient mechanism to multiply or divide numbers by powers of 2.

Examples

Highest Set Bit

Given a non-negative integer n, let us number its bits from right to left, starting at 0. Thus, according to this counting, the bit 1 appears in the number 0000010 at bit 1. (For this reason, we discourage you from saying things like "the first bit", because that can be ambiguously interpreted as either bit 0 or bit 1. We prefer that nomenclature to the ordinals "first", "second", etc.)

With this counting, we write a code segment that determines the highest numbered bit that contains a 1 for the non-negative integer n.

To approach this problem, we consider shifting the bits of the number one bit to the right successively until the resulting number is 0. The relevant code is below. (Note that it will produce -1 if no bits are set.)

bit-highest.c
/* Identify the highest set bit of a given number */
#include <stdio.h>

#ifndef VALUE
#define VALUE 136
#endif

int
main(void)
{
   int count = -1; 
   int n = VALUE;

   /* Find location of the highest set bit */
   while (n != 0) {
      count++;
      n = n >> 1; /* Note: we could have written: n>>=1 */
   }
   
   printf("Highest set bit in %d: %d\n",VALUE,count);
   
   return 0;
} // main

Printing a non-negative value in binary

Before we introduce the next example, we should say that
Depending on the computer architecture, a byte may consist of 8 or more bits, the exact number provided as CHAR_BIT. [cppreference.com]

The platform-specific value CHAR_BIT is defined in limits.h.

Recall that the sizeof operator gives the number of bytes required for a data type. Therefore, to place a one in the left-most bit but one of an int, as we do in the next example, we shift a single 1 by the appropriate amount: 

unsigned mask = 1 << (int_size - 2); // 0100...000

Note that we will want to place the one in the leftmost-but-one slot because we will proceed by right shifting mask, and C does not define what values get prepended at the left when the leading bit is 1.

To approach this problem, consider the integer with bit representation 1000...000, which we might call mask. For this integer, the left-most bit, in bit i, is 1, and all of the rest are 0. Next, for a non-negative integer, consider applying the bitwise AND operation (&) to the number n and mask:

Putting the pieces together, the result of mask & n is to extract the ith bit of n and set all other bits to 0. With this observation, we can print the ith bit of n with the code: 

if ((mask & n) == 0)
   printf ("0");
else
   printf ("1");

We might express this a bit more concisely using the ternary conditional operator: 

printf( (mask & n) ? "1" : "0" );

A similar approach can be used for each bit of n, if we successively shift the mask variable right by 1 bit each time.

bit-binary.c
/* Print the binary representation of a non-negative integer */

#include <stdio.h>
#include <limits.h>

#ifndef VALUE
#define VALUE 42
#endif

int
main(void)
{
   int n = VALUE;
   
   if (n<0) {
      printf("Error: n must be non-negative");
      return 1;
   }
   
   printf ("number of bits in int:  %ld\n", sizeof(int)*CHAR_BIT);

   printf ("bit pattern for n:  ");

   int int_size = CHAR_BIT*sizeof(int);

   // initialize mask with a 1 in the leftmost-but-one position
   unsigned int mask = 1 << (int_size - 2);
   printf ("0");                             // print a leading zero 
   for (int i = 0; i < int_size-1; i++) {    // for each bit:
       printf( (mask & n) ? "1" : "0" );     //     print the bit
       mask = mask >> 1;                     //     shift the mask rightward
    }
  printf ("\n");

  return 0;
} // main
Creative Commons License This derivative work is used and licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license. The original by Henry Walker, except where noted, may be found here.
Validate HTML