Bit Manipulation for Algorithmic Problem Solving
Introduction to Bitwise Operators
Working with Bits
Computers store and process information as bits, which are just tiny switches that can be either on (1) or off (0). Bitwise operators in C++ let you work directly with these individual bits. They are fast, powerful, and essential for low-level programming tasks like working with hardware or optimizing code.
The Basic Logic Operators
Three fundamental operators—AND, OR, and XOR—compare the bits of two numbers and produce a new number as a result. They look at each pair of corresponding bits (one from each number) to decide what the resulting bit should be.
Bitwise AND
other
The & operator compares two bits and returns a 1 only if both bits are 1. Otherwise, it returns 0.
Let's see how 5 & 3 works. In binary, 5 is 0101 and 3 is 0011.
0101 (5)
& 0011 (3)
------
0001 (1)
The operator compares each column. Only the rightmost column has two 1s, so the final result is 1.
#include <iostream>
int main() {
int a = 5; // Binary: 0101
int b = 3; // Binary: 0011
int result = a & b; // Result: 0001
std::cout << result; // Prints 1
return 0;
}
Bitwise OR
other
The | operator compares two bits and returns a 1 if at least one of the bits is 1. It only returns 0 if both bits are 0.
Using the same numbers, 5 (0101) and 3 (0011):
0101 (5)
| 0011 (3)
------
0111 (7)
Any column with at least one 1 results in a 1. The result is 7.
#include <iostream>
int main() {
int a = 5; // Binary: 0101
int b = 3; // Binary: 0011
int result = a | b; // Result: 0111
std::cout << result; // Prints 7
return 0;
}
Bitwise XOR
other
The ^ (Exclusive OR) operator returns 1 only if the two bits are different. If they are the same (0 and 0 or 1 and 1), it returns 0.
Again, with 5 (0101) and 3 (0011):
0101 (5)
^ 0011 (3)
------
0110 (6)
The second and third bits from the right are different, so they become 1. The others are the same, so they become 0. The result is 6.
#include <iostream>
int main() {
int a = 5; // Binary: 0101
int b = 3; // Binary: 0011
int result = a ^ b; // Result: 0110
std::cout << result; // Prints 6
return 0;
}
The final basic operator is NOT. Unlike the others, it only works on a single number.
Bitwise NOT
other
The ~ operator, also known as the complement operator, is a unary operator that flips every bit of a number. Every 0 becomes a 1, and every 1 becomes a 0.
If we have the number 5 (00000101 in an 8-bit representation), applying the NOT operator gives us 11111010. The result you see in C++ might be surprising (-6) because of how computers store negative numbers (using a system called two's complement), but the core idea is simple: all bits are inverted.
#include <iostream>
int main() {
int a = 5; // Binary: ...00000101
int result = ~a; // Result: ...11111010
std::cout << result; // Prints -6
return 0;
}
Shifting Bits Around
Besides comparing bits, we can also move them left or right. These are the shift operators, and they are incredibly efficient for certain kinds of multiplication and division.
Left Shift
other
The << operator shifts the bits of a number to the left by a specified number of positions. The empty positions on the right are filled with zeros.
Let's take the number 5 (00000101) and left shift it by 2 positions (5 << 2).
Original: 00000101 (5)
Shifted: 00010100 (20)
Each bit moves two spots to the left, and two zeros are added on the right. Shifting left by n bits is the same as multiplying the number by . Here, .
#include <iostream>
int main() {
int a = 5; // Binary: 00000101
// Shift left by 2 positions
int result = a << 2; // Result: 00010100
std::cout << result; // Prints 20
return 0;
}
Right Shift
other
The >> operator shifts the bits of a number to the right by a specified number of positions. Bits on the right are discarded.
Now let's take the number 20 (00010100) and right shift it by 2 (20 >> 2).
Original: 00010100 (20)
Shifted: 00000101 (5)
Each bit moves two spots to the right. The two rightmost bits (00) are dropped. Shifting right by n bits is equivalent to integer division by $2^n$. Here, $20 / 2^2 = 20 / 4 = 5$.
#include <iostream>
int main() {
int a = 20; // Binary: 00010100
// Shift right by 2 positions
int result = a >> 2; // Result: 00000101
std::cout << result; // Prints 5
return 0;
}
Understanding these six operators gives you a new level of control, allowing you to manipulate data at its most fundamental level.
What is the decimal result of the bitwise expression 9 & 5?
Which bitwise operator is often described as a "selective bit flipper" because it inverts a bit if the corresponding bit in the other operand is 1, and leaves it unchanged if it's 0?