Let us adopt the terminology bit pattern or word for a sequence of bits of a fixed length. This way we do not need to be specific about the length of the bit pattern or think about what integer it might (or might not) represent. All data handled by digital computers is ultimately represented as bit patterns.
The bitwise operators are applied to bit patterns. They are binary operators, meaning that they take two operands. The operands must be of the same length, and the result is a bit pattern of the same length. The bitwise operators are:
Bitwise AND & is a binary operator that takes two bit patterns of the same length and returns a bit pattern of the same length. The resulting bit pattern has a 1 bit in each position where both operands have a 1 bit, and a 0 bit in all other positions.
Bitwise OR | is a binary operator that takes two bit patterns of the same length and returns a bit pattern of the same length. The resulting bit pattern has a 1 bit in each position where at least one of the operands has a 1 bit, and a 0 bit in all other positions.
Bitwise XOR ^ is a binary operator that takes two bit patterns of the same length and returns a bit pattern of the same length. The resulting bit pattern has a 1 bit in each position where exactly one of the operands has a 1 bit, and a 0 bit in all other positions.
Remark1.3.1.
In class, I previously used the symbols \(\oplus\) and \(\odot\) for bitwise OR and AND, respectively. In this section, we use different symbols, to match Python’s remark: & for bitwise AND, | for bitwise OR, and ^ for bitwise XOR. Bitwise versions of NAND, NOR, and XNOR do not appear in these notes.
The bitwise NOT operator is written \(\negg\text{.}\) It is a unary operator, meaning that it takes a single operand. The operand must be a bit pattern, and the result is a bit pattern of the same length.
Remark1.3.2.
If you have previous experience in C, Java, or closely related languages, you may have wondered why the logical operators AND and OR are written && and || in those languages. It is because the single-character variants & and | are reserved for bitwise operations.
Some other operators on bit patterns are the logical shift operators << and >>. These are also binary operators, taking a bit pattern and an integer as operands. The result is a bit pattern of the same length as the first operand. The second operand must be non-negative.
Example1.3.3.
The expression 0b1010 << 1 evaluates to 0b10100, and the expression 0b1010 >> 1 evaluates to 0b101.
Subsection1.3.1Bitmasking
Activity1.3.1.
What operation from our previous discussion of binary-encoded integers is also represented by << 1? That is, if the bit pattern \(x\) is interpreted as an integer, what integer is represented by \(x\) << 1?
What operation from our previous discussion of binary-encoded integers is also represented by >> 1? That is, if the bit pattern \(x\) is interpreted as an integer, what integer is represented by \(x\) >> 1?
Recall that bitwise operators return values of the same length as their operands. Therefore, the bitwise operators behave in the following way for a few 4-bit patterns:
Example1.3.4.
Table1.3.5.The fixed-width nature of bitwise operators
\(x\)
\(y\)
\(\negg x\)
\(x \& y\)
\(x | y\)
\(x \textrm{\^{}} y\)
\(1100\)
\(1010\)
\(0011\)
\(1000\)
\(1110\)
\(0110\)
\(0000\)
\(1111\)
\(1111\)
\(0000\)
\(1111\)
\(1111\)
\(10111111\)
\(00000010\)
\(01000000\)
\(00000010\)
\(10111111\)
\(10111101\)
Activity1.3.2.
What is the effect of applying bitwise AND to a bit pattern \(x\) and the word \(111\ldots0\) of the same length?
Activity1.3.3.
What is the effect of applying bitwise OR to a bit pattern \(x\) and the word \(000\ldots1\) of the same length?
Activity1.3.4.
How would you use a similar idea to toggle the last bit of \(x\text{?}\) That is, how would you use a bitwise operation to change the last bit of \(x\) from 0 to 1 or from 1 to 0? You cannot use a conditional statement.
