Bitwise operations
Bitwise operations work directly on the binary representation of integers.
| Operator | Symbol | Example | Meaning |
|---|---|---|---|
| Bitwise left shift | << | x << k | Shifts all bits of x to the left by k positions |
| Bitwise right shift | >> | x >> k | Shifts all bits of x to the right by k positions |
| Bitwise AND | & | x & y | Applies AND to each pair of corresponding bits |
| Bitwise OR | | | x | y | Applies OR to each pair of corresponding bits |
| Bitwise exclusive OR | ^ |
x ^ y| Applies XOR to each pair of corresponding bits |
When we shift the binary number
to the left by positions, we append zeros to the right:
So shifting left by one position is equivalent to multiplying by , and shifting left by positions is equivalent to multiplying by .
The output is:
When we shift the binary number
to the right by positions, the last bits are removed:
For non-negative integers, shifting right by one position is equivalent to integer division by , and shifting right by positions is equivalent to integer division by .
The output is:
The bitwise AND of two numbers and is a number , where
This means we apply AND to each pair of corresponding bits.
The result of x & y is 1 only if both bits are 1. Otherwise, it is 0.
| x | y | Result |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The output is:
The bitwise OR of two numbers and is a number , where
This means we apply OR to each pair of corresponding bits.
The result of x | y is 1 if at least one of the bits is 1. Otherwise, it is 0.
| x | y | Result |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The output is:
The bitwise XOR of two numbers and is a number , where
This means we apply XOR to each pair of corresponding bits.
The result of x ^ y is 1 if exactly one of the bits is 1. If both bits are the same, the result is 0.
| x | y | Result |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The output is:
Try to solve these problems on your own before looking at the solutions.
Given two integers and , where , output the value
Given two integers and , output the number obtained from after inverting the -th bit.
Given two integers and , output the number obtained from after setting the -th bit to 0.
Given two integers and , output the value of the -th bit of the number .
Given two integers and , set the last bits of the number to 0 and output the result.
Given two integers and , compute their product without using the operations *, /, or %.
To get , we can use 1 << x. Similarly, 1 << y gives .
Since , these two numbers have different single bits set, so we can combine them with bitwise OR.
To invert the -th bit, we use XOR with a mask that has only the -th bit equal to 1.
To set the -th bit to 0, we can first check whether it is 1. If it is, we flip it.
A shorter version is:
To get the value of the -th bit, we shift it to the last position and take the last bit.
Solution with a loop
We check the last bits one by one and clear them if needed.
Solution without a loop
We shift the number right by bits, which removes the last bits, and then shift it back left by bits.
We can use the binary representation of .
If the -th bit of is 1, then we add , which is the same as x << i.
int x = 11; // x = 1011 in binary
cout << (x << 2) << "\n"; // 101100 in binary
int x = 11; // x = 1011 in binary
cout << (x >> 2) << "\n"; // 10 in binary
int x = 11; // x = 1011
int y = 6; // y = 0110
cout << (x & y) << "\n"; // 0010 in binary
int x = 9; // x = 1001
int y = 4; // y = 0100
cout << (x | y) << "\n"; // 1101 in binary
int x = 12; // x = 1100
int y = 6; // y = 0110
cout << (x ^ y) << "\n"; // 1010 in binary
cout << ((1 << x) | (1 << y)) << "\n";
cout << (x ^ (1 << k)) << "\n";
if (x & (1 << k)) {
x ^= (1 << k);
}
cout << x << "\n";
cout << (x & (~(1 << k))) << "\n";
cout << ((x >> k) & 1) << "\n";
for (int i = 0; i < k; i++) {
if (x & (1 << i)) {
x ^= (1 << i);
}
}
cout << x << "\n";
cout << ((x >> k) << k) << "\n";
long long res = 0;
for (int i = 0; i < 30; i++) {
if (y & (1 << i)) {
res += (1LL * x << i);
}
}
cout << res << "\n";