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.

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. We will revisit bit shifting operations later in the course. For now, we define them for the sake of being comprehensive.

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, filling the lower bits coming in from the left with 0’s. Mathematically, this is equivalent to multiplying x by $2^{\texttt{n}}$. For example, x << 3 gives the bit pattern 0000 1000, where the leftmost 1 gets “shifted out.”

Right shift, x >> n shifts the bits of x right. Mathematically, this is equivalent to taking the floor of a division by $2^{\texttt{n}}4 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 top 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 top bits with the sign bit of x. Arithmetic right shift therefore preserves the sign bit of the result when using signed operands.