C Bitwise Operations

1Learning Outcomes¶

• Understand how bitwise operations “flip” or “keep” bits from operands.

• Identify use cases for AND, OR, XOR, and NOT.

So far, we have learned about arithmetic operations involving binary numbers. In this section, we will learn about bitwise operations.

2Bitwise Operations¶

We denote the bitwise operations AND, OR, XOR, and NOT as the operators &, |, ^, and ~, respectively. Supposing a and b are single-bit values, the following truth tables specify the result y of each operation.^[1]

Table 1 is bitwise AND. a & b is 1 only if both a and b are 1. Otherwise, it is 0.

Table 2 is bitwise OR. a | b is 1 only if either a or b are 1. Otherwise, it is 0.

Table 3 is bitwise NOT. It is a unary operator because it only takes one operand. ~a is 1 only if a is 0. If a is 1, then ~a is 0.

Table 4 is bitwise XOR (“exclusive OR”). a ^ b is 1 only if one of a and b is 1. Otherwise if both a and b are 0 or 1, a^b is 0.

2.1Properties of Bitwise Operations¶

The below properties in Table 5 hold for a single-bit value x. We leave the proofs to you.

Because of its behavior, we also call XOR a “conditional inverter”. We discuss this more when we design logic gates (see later section).

3C: Bitwise Operations vs. Logical Operations¶

The bitwise operators &, |, and ~ are used in C. With n-bit operands, bitwise operations are performed on the binary numeral(s) one bit at a time; the result’s bitwidth depends on the input operands. See Table 6 for examples on 8-bit char values.

However, note that C bitwise operators should not be confused with the C logical operators &&, ||, and !. By contrast, Logical operations translate bit values to truthy and and falsy values. These types of operations are also known as boolean compound operators^[2].

4Bitmasks¶

This is our first foray into bitwise operations. Why do we care?

Remember that n bits can represent $2^n$ things, and we often want to use bits to represent many more things than just numbers. Suppose we wanted to use bit patterns to represent whether n things were present. We could then use each of our n bits to represent whether each thing was present (1) or not 0.

Using bitwise operations (and the properties of such bitwise operations) will be very convenient for updating state using bit patterns called bitmasks.

Bitwise operations will be very useful for boolean logic later on when we introduce logic gates.

5More C Bitwise Operators: Left and Right Shift¶

Two additional operations describe bit shifts.

Suppose you have the 8-bit bit patterns (where we put spaces between nibbles for readability):

• x, with bit pattern 0001 0001

• y, with bit pattern 1111 0001

Left shift x << n shifts the bits of x left by n bits, filling the n lower bits (“coming in from the right”) with 0’s. Mathematically, this is equivalent to multiplying x by $2^{\texttt{n}}$.

• For example, x << 2 gives the bit pattern 0100 0100. If we interpret x as a signed 8-bit integer 17, then x << 2 is indeed $17 \times 4 = 68$.

• Left shifting also encounters overflow: x << 4 gives the bit pattern 0001 0000 where the leftmost 1 gets “shifted out” of the 8-bit type (to produce the signed 8-bit integer 16, which is certainly not $17 \times 2^4$).

Right shift, x >> n shifts the bits of x right by n bits. Mathematically, this is equivalent to taking the floor of a division by $2^{\texttt{n}}$. We will still need to fill in the top bits coming in from the right somehow, but the precise operation in C depends on x’s type.

• Logical right shift “zero-extends” and fills the upper bits with 0. If x is an unsigned 8-bit integer, then x >> 2 gives the bit pattern 0000 0100, where the rightmost 1 gets shifted out. This is equivalent to (unsigned char) 17 >> 2 yielding 4.

• Arithmetic right shift “sign-extends” and fills the upper bits with the sign bit of x. Arithmetic right shift therefore preserves the sign bit of the result when using signed operands.

6Practice¶

Show answer

B. 0x3400.

• N is 0x000034FF

• N << 0x10 is 0x34FF 0000. We left shift N by 16.

• (N << 0x10) >> 0x8 is 0x0034 FF00. Because N is an unsigned integer, arithmetic right shift by 8 inserts zeros and is equivalent to logical right shift.

• N & (N << 0x10) >> 0x8 is 0x0000 3400, as per Figure 1. Note that 0x34 & 0x00 and 0xFF & 0x00 are both zero, because AND-ing anything with 0 sets all bits to zero.