Bitwise Operations Overview
Description
Bit manipulation is a technique that operates directly on the binary representation of numbers using special operators. Every integer stored in a computer is internally a sequence of bits (binary digits — 0s and 1s). Bitwise operators work on these individual bits, making them extremely fast since they map directly to single CPU instructions.
There are six fundamental bitwise operators available in most programming languages:
| Operator | Symbol | Description |
|---|---|---|
| AND | & | Returns 1 only if both bits are 1 |
| OR | | | Returns 1 if at least one bit is 1 |
| XOR | ^ | Returns 1 if the bits are different |
| NOT | ~ | Flips every bit (0 → 1, 1 → 0) |
| Left Shift | << | Shifts all bits left by k positions (fills with 0s on the right) |
| Right Shift | >> | Shifts all bits right by k positions (fills with 0s on the left for unsigned) |
Given two integers a and b, compute the result of each bitwise operation and understand how the binary digits interact at each position.
Beyond the basic operators, bit manipulation enables powerful single-bit operations — checking, setting, clearing, and toggling individual bits — which form the building blocks for countless algorithmic techniques.
Examples
Example 1
Input: a = 5, b = 9
Output:
- a & b = 1 (AND)
- a | b = 13 (OR)
- a ^ b = 12 (XOR)
- ~a = -6 (NOT, assuming 32-bit signed integer)
- b << 1 = 18 (Left Shift by 1)
- b >> 1 = 4 (Right Shift by 1)
Explanation:
- a = 5 in binary is
0101, b = 9 in binary is1001 - AND:
0101 & 1001 = 0001→ 1 (both bits must be 1) - OR:
0101 | 1001 = 1101→ 13 (at least one bit is 1) - XOR:
0101 ^ 1001 = 1100→ 12 (bits differ) - NOT: ~
0101flips all 32 bits →11111111111111111111111111111010→ -6 in two's complement - Left shift:
1001 << 1=10010→ 18 (equivalent to multiplying by 2) - Right shift:
1001 >> 1=0100→ 4 (equivalent to integer division by 2)
Example 2
Input: a = 12, b = 10
Output:
- a & b = 8
- a | b = 14
- a ^ b = 6
- ~a = -13
- a << 2 = 48
- a >> 2 = 3
Explanation:
- a = 12 in binary is
1100, b = 10 in binary is1010 - AND:
1100 & 1010 = 1000→ 8 (only bit position 3 has both set) - OR:
1100 | 1010 = 1110→ 14 (positions 1, 2, and 3 have at least one set) - XOR:
1100 ^ 1010 = 0110→ 6 (positions 1 and 2 differ between a and b) - NOT: ~12 = -13 (flip all bits and interpret in two's complement)
- Left shift by 2:
1100 << 2 = 110000→ 48 (multiplied by 2² = 4) - Right shift by 2:
1100 >> 2 = 0011→ 3 (integer division by 4)
Example 3
Input: a = 0, b = 15
Output:
- a & b = 0
- a | b = 15
- a ^ b = 15
Explanation:
- a = 0 → all bits are 0. AND with anything is 0. OR and XOR with b return b itself. This demonstrates the identity properties:
X & 0 = 0,X | 0 = X,X ^ 0 = X.
Constraints
- -2^31 ≤ a, b ≤ 2^31 - 1 (standard 32-bit signed integer range)
- 0 ≤ k ≤ 31 for shift and single-bit operations (k is the bit position or shift amount)
- Operations are performed on the binary representation of the integers
Editorial
Brute Force - Manual Binary Conversion
Intuition
Before using any special operators, let us understand bitwise operations from first principles. Every integer can be written as a sequence of binary digits. To perform a bitwise operation manually, we:
- Convert both numbers to their binary representations (arrays of 0s and 1s)
- Align the arrays so corresponding bit positions match
- Apply the operation rules bit-by-bit (position by position)
- Convert the resulting binary array back to a decimal number
Think of two rows of light bulbs, where ON = 1 and OFF = 0. For AND, a result bulb turns ON only if both corresponding bulbs are ON. For OR, it turns ON if either bulb is ON. For XOR, it turns ON only if exactly one is ON.
This manual approach makes the bit-level behavior completely transparent — you can see exactly what happens at each position.
Step-by-Step Explanation
Let's trace AND, OR, and XOR manually for a = 5, b = 9 using 4-bit representation:
Step 1: Convert a = 5 to binary → [0, 1, 0, 1] (from MSB to LSB: positions 3, 2, 1, 0).
Step 2: Convert b = 9 to binary → [1, 0, 0, 1].
Step 3: AND — Process bit position 3: a[3]=0, b[3]=1. Both must be 1 for AND to yield 1. Since a[3]=0, result[3] = 0.
Step 4: AND — Process bit position 2: a[2]=1, b[2]=0. a[2] is 1 but b[2] is 0. Result[2] = 0.
Step 5: AND — Process bit position 1: a[1]=0, b[1]=0. Both are 0. Result[1] = 0.
Step 6: AND — Process bit position 0: a[0]=1, b[0]=1. Both are 1! Result[0] = 1.
Step 7: AND result binary = [0, 0, 0, 1] = 1 in decimal. Only position 0 had both bits set.
Step 8: OR — Apply bit-by-bit: [0|1, 1|0, 0|0, 1|1] = [1, 1, 0, 1] = 13.
Step 9: XOR — Apply bit-by-bit: [0^1, 1^0, 0^0, 1^1] = [1, 1, 0, 0] = 12. Position 0 has matching bits (both 1), so XOR gives 0 there.
Manual Bit-by-Bit AND Operation: 5 & 9 — Watch how we compare corresponding bits of two numbers position by position, applying the AND rule: output is 1 only when both input bits are 1.
Algorithm
For any bitwise operation between two numbers a and b:
- Determine the number of bits needed: k = max(number of bits in a, number of bits in b)
- Create binary arrays of length k for both a and b:
- For each position i from 0 to k-1: bit[i] = (number >> i) & 1
- Create a result array of length k
- For each position i from 0 to k-1:
- AND: result[i] = a_bits[i] AND b_bits[i]
- OR: result[i] = a_bits[i] OR b_bits[i]
- XOR: result[i] = 1 if a_bits[i] ≠ b_bits[i], else 0
- Convert result array back to decimal: sum of result[i] × 2^i for all i
For NOT: flip every bit of a's binary representation
For shifts: move all bits left or right by k positions
Code
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;
class Solution {
public:
// Convert integer to binary array (LSB at index 0)
vector<int> toBinary(int num, int bits) {
vector<int> result(bits, 0);
for (int i = 0; i < bits; i++) {
result[i] = (num >> i) & 1;
}
return result;
}
// Convert binary array back to integer
int toDecimal(vector<int>& bits) {
int result = 0;
for (int i = 0; i < bits.size(); i++) {
if (bits[i]) result += (1 << i);
}
return result;
}
int manualAND(int a, int b) {
int bits = 32;
vector<int> aBits = toBinary(a, bits);
vector<int> bBits = toBinary(b, bits);
vector<int> result(bits);
for (int i = 0; i < bits; i++) {
result[i] = aBits[i] & bBits[i]; // both must be 1
}
return toDecimal(result);
}
int manualOR(int a, int b) {
int bits = 32;
vector<int> aBits = toBinary(a, bits);
vector<int> bBits = toBinary(b, bits);
vector<int> result(bits);
for (int i = 0; i < bits; i++) {
result[i] = aBits[i] | bBits[i]; // at least one is 1
}
return toDecimal(result);
}
int manualXOR(int a, int b) {
int bits = 32;
vector<int> aBits = toBinary(a, bits);
vector<int> bBits = toBinary(b, bits);
vector<int> result(bits);
for (int i = 0; i < bits; i++) {
result[i] = (aBits[i] != bBits[i]) ? 1 : 0;
}
return toDecimal(result);
}
};class Solution:
def to_binary(self, num: int, bits: int) -> list[int]:
"""Convert integer to binary array (LSB at index 0)"""
return [(num >> i) & 1 for i in range(bits)]
def to_decimal(self, binary: list[int]) -> int:
"""Convert binary array back to integer"""
result = 0
for i, bit in enumerate(binary):
if bit:
result += (1 << i)
return result
def manual_and(self, a: int, b: int) -> int:
bits = 32
a_bits = self.to_binary(a, bits)
b_bits = self.to_binary(b, bits)
result = [a_bits[i] & b_bits[i] for i in range(bits)]
return self.to_decimal(result)
def manual_or(self, a: int, b: int) -> int:
bits = 32
a_bits = self.to_binary(a, bits)
b_bits = self.to_binary(b, bits)
result = [a_bits[i] | b_bits[i] for i in range(bits)]
return self.to_decimal(result)
def manual_xor(self, a: int, b: int) -> int:
bits = 32
a_bits = self.to_binary(a, bits)
b_bits = self.to_binary(b, bits)
result = [1 if a_bits[i] != b_bits[i] else 0 for i in range(bits)]
return self.to_decimal(result)class Solution {
// Convert integer to binary array (LSB at index 0)
public int[] toBinary(int num, int bits) {
int[] result = new int[bits];
for (int i = 0; i < bits; i++) {
result[i] = (num >> i) & 1;
}
return result;
}
// Convert binary array back to integer
public int toDecimal(int[] binary) {
int result = 0;
for (int i = 0; i < binary.length; i++) {
if (binary[i] == 1) result += (1 << i);
}
return result;
}
public int manualAND(int a, int b) {
int bits = 32;
int[] aBits = toBinary(a, bits);
int[] bBits = toBinary(b, bits);
int[] result = new int[bits];
for (int i = 0; i < bits; i++) {
result[i] = aBits[i] & bBits[i];
}
return toDecimal(result);
}
public int manualOR(int a, int b) {
int bits = 32;
int[] aBits = toBinary(a, bits);
int[] bBits = toBinary(b, bits);
int[] result = new int[bits];
for (int i = 0; i < bits; i++) {
result[i] = aBits[i] | bBits[i];
}
return toDecimal(result);
}
public int manualXOR(int a, int b) {
int bits = 32;
int[] aBits = toBinary(a, bits);
int[] bBits = toBinary(b, bits);
int[] result = new int[bits];
for (int i = 0; i < bits; i++) {
result[i] = (aBits[i] != bBits[i]) ? 1 : 0;
}
return toDecimal(result);
}
}Complexity Analysis
Time Complexity: O(k) where k is the number of bits (typically 32)
We iterate through all k bit positions for each operation. Converting to binary takes O(k), performing the operation takes O(k), and converting back takes O(k). Total: O(k) per operation.
Space Complexity: O(k)
We create three arrays of size k (one for each operand's binary form, one for the result). For 32-bit integers, this is O(32) = O(1), but conceptually it is proportional to the number of bits.
Why This Approach Is Not Efficient
The manual approach is excellent for understanding, but wasteful for actual computation:
1. Unnecessary conversion overhead: We convert integers to binary arrays and back, but the numbers are already stored as binary bits inside the CPU. We're doing work the hardware does for free.
2. Loop over all 32 bits: Even if only a few low-order bits matter (e.g., 5 & 9 only needs 4 bits), we process all 32 bits. The hardware performs all 32-bit operations in a single clock cycle through parallel circuits.
3. Array allocation: Creating arrays for bit representations wastes memory when the CPU already has the bits readily available in registers.
Key insight: Modern CPUs have dedicated circuits for bitwise operations. a & b, a | b, a ^ b each execute as a single machine instruction taking O(1) time. The bitwise operators &, |, ^, ~, <<, >> give us direct access to this hardware-level parallelism — processing all 32 (or 64) bits simultaneously rather than one at a time.
Optimal Approach - Direct Bitwise Operators
Intuition
Instead of manually converting numbers to binary arrays, we use the language's built-in bitwise operators which map directly to CPU instructions. Each operator processes all bits in parallel — in a single operation.
Here is the truth table that governs all bitwise operators:
| a | b | a & b (AND) | a | b (OR) | a ^ b (XOR) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
Key identity properties (essential for problem-solving):
X & 0 = 0— AND with 0 always clears bitsX & 1 = X— AND with 1 preserves bits (used to extract bits)X | 0 = X— OR with 0 preserves bitsX | 1 = 1— OR with 1 always sets bits (used to set bits)X ^ 0 = X— XOR with 0 preserves bitsX ^ 1 = ~X— XOR with 1 flips bits (used to toggle bits)X ^ X = 0— XOR with itself cancels (used to find unique elements)
Shift operators serve as fast multiplication and division:
a << kis equivalent toa × 2^k(left shift = multiply by power of 2)a >> kis equivalent toa ÷ 2^k(right shift = integer divide by power of 2)
These operators combine into four essential single-bit manipulation patterns:
- Get Bit at position k:
(n >> k) & 1— extracts the k-th bit - Set Bit at position k:
n | (1 << k)— forces the k-th bit to 1 - Clear Bit at position k:
n & ~(1 << k)— forces the k-th bit to 0 - Toggle Bit at position k:
n ^ (1 << k)— flips the k-th bit
Step-by-Step Explanation
Let's demonstrate all six operators with a = 5, b = 9, then show the four single-bit operations on n = 13 (binary: 1101) at position k = 1:
Part A: The Six Operators
Step 1: a = 5 (binary: 0101), b = 9 (binary: 1001). All operations below process all bit positions simultaneously.
Step 2: AND: 5 & 9. Binary: 0101 & 1001 = 0001 → 1. Only bit 0 has both set.
Step 3: OR: 5 | 9. Binary: 0101 | 1001 = 1101 → 13. Bits 0, 2, and 3 have at least one set.
Step 4: XOR: 5 ^ 9. Binary: 0101 ^ 1001 = 1100 → 12. Bits 2 and 3 differ between a and b.
Step 5: NOT: ~5. Flips all 32 bits: ...11111010 → -6 in two's complement.
Step 6: Left shift: 9 << 1. Binary: 1001 becomes 10010 → 18 (9 × 2 = 18).
Step 7: Right shift: 9 >> 1. Binary: 1001 becomes 0100 → 4 (9 ÷ 2 = 4, integer division).
Part B: Single-Bit Operations on n = 13 (1101), k = 1
Step 8: Get Bit: (13 >> 1) & 1. Shift right by 1: 1101 → 0110. AND with 1: 0110 & 0001 = 0. Bit 1 of 13 is 0.
Step 9: Set Bit: 13 | (1 << 1). Create mask: 1 << 1 = 0010. OR: 1101 | 0010 = 1111 → 15. Bit 1 is now forced to 1.
Step 10: Clear Bit: 13 & ~(1 << 1). Mask: ~(0010) = 1101. AND: 1101 & 1101 = 1101 → 13 (bit 1 was already 0, so no change). If we try k=0: 13 & ~(0001) = 1101 & 1110 = 1100 → 12.
Step 11: Toggle Bit: 13 ^ (1 << 1). Mask: 0010. XOR: 1101 ^ 0010 = 1111 → 15. Bit 1 was 0, now it's 1. If we toggle again: 15 ^ (1 << 1) = 1111 ^ 0010 = 1101 → 13 (back to original).
Bitwise Operations on 5 and 9 + Single-Bit Manipulation on 13 — Watch how each bitwise operator processes all bits in parallel, then see how combining shift, AND, OR, XOR enables precise single-bit manipulation.
Algorithm
Basic Operators (all O(1)):
- AND:
result = a & b - OR:
result = a | b - XOR:
result = a ^ b - NOT:
result = ~a - Left Shift:
result = a << k - Right Shift:
result = a >> k
Single-Bit Operations (all O(1)):
- Get Bit k:
(n >> k) & 1— shift bit k to position 0, then isolate with AND - Set Bit k:
n | (1 << k)— create a mask with only bit k set, OR forces it on - Clear Bit k:
n & ~(1 << k)— create a mask with all bits EXCEPT k set, AND clears it - Toggle Bit k:
n ^ (1 << k)— create a mask with only bit k set, XOR flips it
Useful Shortcuts:
- Check even/odd:
n & 1(0 = even, 1 = odd) - Multiply by 2^k:
n << k - Divide by 2^k:
n >> k - Check if power of 2:
n > 0 && (n & (n-1)) == 0
Code
#include <iostream>
using namespace std;
class Solution {
public:
// --- Six Fundamental Operators ---
void demonstrateOperators(int a, int b) {
cout << "a & b = " << (a & b) << endl; // AND
cout << "a | b = " << (a | b) << endl; // OR
cout << "a ^ b = " << (a ^ b) << endl; // XOR
cout << "~a = " << (~a) << endl; // NOT
cout << "b << 1 = " << (b << 1) << endl; // Left Shift
cout << "b >> 1 = " << (b >> 1) << endl; // Right Shift
}
// --- Single-Bit Operations ---
// Returns the value of the k-th bit (0 or 1)
int getBit(int n, int k) {
return (n >> k) & 1;
}
// Sets the k-th bit to 1 and returns the result
int setBit(int n, int k) {
return n | (1 << k);
}
// Clears the k-th bit to 0 and returns the result
int clearBit(int n, int k) {
return n & ~(1 << k);
}
// Toggles the k-th bit and returns the result
int toggleBit(int n, int k) {
return n ^ (1 << k);
}
// --- Useful Shortcuts ---
bool isOdd(int n) {
return (n & 1) != 0;
}
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
};class Solution:
# --- Six Fundamental Operators ---
def demonstrate_operators(self, a: int, b: int):
print(f"a & b = {a & b}") # AND
print(f"a | b = {a | b}") # OR
print(f"a ^ b = {a ^ b}") # XOR
print(f"~a = {~a}") # NOT
print(f"b << 1 = {b << 1}") # Left Shift
print(f"b >> 1 = {b >> 1}") # Right Shift
# --- Single-Bit Operations ---
def get_bit(self, n: int, k: int) -> int:
"""Returns the value of the k-th bit (0 or 1)"""
return (n >> k) & 1
def set_bit(self, n: int, k: int) -> int:
"""Sets the k-th bit to 1"""
return n | (1 << k)
def clear_bit(self, n: int, k: int) -> int:
"""Clears the k-th bit to 0"""
return n & ~(1 << k)
def toggle_bit(self, n: int, k: int) -> int:
"""Toggles the k-th bit"""
return n ^ (1 << k)
# --- Useful Shortcuts ---
def is_odd(self, n: int) -> bool:
return (n & 1) != 0
def is_power_of_two(self, n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0class Solution {
// --- Six Fundamental Operators ---
public void demonstrateOperators(int a, int b) {
System.out.println("a & b = " + (a & b)); // AND
System.out.println("a | b = " + (a | b)); // OR
System.out.println("a ^ b = " + (a ^ b)); // XOR
System.out.println("~a = " + (~a)); // NOT
System.out.println("b << 1 = " + (b << 1)); // Left Shift
System.out.println("b >> 1 = " + (b >> 1)); // Right Shift
}
// --- Single-Bit Operations ---
public int getBit(int n, int k) {
return (n >> k) & 1;
}
public int setBit(int n, int k) {
return n | (1 << k);
}
public int clearBit(int n, int k) {
return n & ~(1 << k);
}
public int toggleBit(int n, int k) {
return n ^ (1 << k);
}
// --- Useful Shortcuts ---
public boolean isOdd(int n) {
return (n & 1) != 0;
}
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}Complexity Analysis
Time Complexity: O(1)
Every bitwise operation (&, |, ^, ~, <<, >>) is a single CPU instruction that processes all bits in parallel. The number of bits (32 or 64) is a fixed constant, not a function of input size. Therefore, each operation takes O(1) time.
Space Complexity: O(1)
Bitwise operations work directly on the integer values stored in CPU registers. No additional data structures or arrays are needed. Only a constant number of integer variables are used.
Why this is optimal: The hardware performs these operations in a single clock cycle using parallel logic gates. There is no way to process individual bits faster than having dedicated circuitry handle all of them simultaneously. Bitwise operators give us direct access to this hardware capability.