Bitwise operators
Overview
Bitwise operators bypass high-level data abstractions to manipulate the individual ones and zeros (bits) that make up a number at the CPU level. Instead of treating `5` and `3` as whole values, they evaluate their binary representations (`101` and `011`) bit by bit in parallel.
Processing data at the register level allows for operations on 32 or 64 individual binary flags simultaneously within a single clock cycle. This creates profound performance optimizations and memory compressions, forming the backbone of cryptography, embedded systems, and efficient algorithm design.
Why learn this
- Bitwise manipulation unlocks massive O(1) space optimizations for specific algorithmic problems.
- Understanding bit-level representation is critical for avoiding language-specific integer overflow and type coercion bugs.
- It forms the foundational vocabulary required to understand advanced topics like Bloom filters, cryptography, and network protocols.
Common mistakes
- Confusing AND (`&`) with OR (`|`): AND is for **masking or checking** bits (clearing unwanted bits to 0). OR is for **setting** bits (forcing specific flags to 1). Mixing them up completely breaks the intended logic.
- Mixing up shift direction: Left shift (`<<`) multiplies by powers of two. Right shift (`>>`) divides by powers of two. A common trap is using the wrong shift to extract vs pack data.
- Arithmetic vs logical right shift: Right-shifting a NEGATIVE signed number behaves differently across languages. An arithmetic shift preserves the sign bit (filling with 1s), while a logical shift fills with 0s. This can accidentally transform a negative number into a massive positive number depending on the language's specific rules.
Recall questions
- What is the result of `x ^ x` (XORing a number with itself)?
- What is the result of `x ^ 0`?
- How do you multiply an integer by `2^k` using bitwise operators?
- What does the expression `x & 1` evaluate?
Understanding checks
What is the binary result of `1010 & 0110`?
`0010` (only the second bit from the right is 1 in both).
The bitwise AND operator evaluates each pair of bits vertically, returning 1 only if BOTH bits are 1.
Why does `~5` (bitwise NOT of 5) often output `-6` instead of just flipping bits to a positive number?
Because modern computing uses two's-complement to represent signed integers. The mathematical rule for two's complement is `~x = -x - 1`.
Inversion flips the sign bit (the highest bit) in a signed integer, turning a positive number into a negative one.
If you apply `x = x | (1 << 3)` to the binary number `0000`, what does `x` become?
`1000` (binary) or 8 (decimal).
The expression `(1 << 3)` creates a mask with only the 3rd bit set (`1000`). The OR operator `|` uses this mask to turn that specific bit ON in `x`, leaving all other bits unchanged.
Practice tasks
Fix the flag check
The code below attempts to check if the 'READ' permission flag (which is the 2nd bit) is set. However, it is using the wrong bitwise operator. Modify the code to correctly use a bitwise AND for masking.
Continue learning
Previous: Logarithms & Powers of Two
Next: Single number (XOR)
Next: Counting bits