C Bitwise Operations

Learning Outcomes

• Understand how bitwise operations “flip” or “keep” bits from operands.
• Identify use cases for AND, OR, XOR, and NOT.

🎥 Walkthrough Video

Please access this YouTube video using UC Berkeley login.

Our sincerest thanks for this video recording go to Adelson Chua, one of our Fall 2022 CS 61C course staff members.

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

Bitwise 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.¹

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

#tab-or is bitwise OR. a | b is 1 only if either a or b are 1. Otherwise, it is 0.

#tab-not 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.

#tab-xor 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.

Properties of Bitwise Operations

The below properties in #tab-bitwise-props 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).

C: 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 #tab-bitwise 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².

Bitmasks

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.

More 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.

Show answer

Logically, left-shifting shifts a bit pattern left and inserts zeros. Arithmetically, left-shifting a number (regardless of its sign) multiplies it by a power of two, which also inserts zeros. Arithmetic and logical left shifts are therefore equivalent.

Practice

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 #fig-bit-shift. Note that 0x34 & 0x00 and 0xFF & 0x00 are both zero, because AND-ing anything with 0 sets all bits to zero.

Result of N & (N << 0x10) >> 0x8, i.e., 0x000034FF & 0x0034 FF00

Footnotes

1. The name “truth table” comes from boolean logic itself. We discuss in a later section about logic design, when it is useful to represent signals as “high” or “low”. ↩

2. In Python, the boolean operators are and, or, and not. Python also supports bitwise operators &, |, ~, and ^. ↩