Welcome to our detailed guide on bit manipulation problems! If you’re preparing for coding interviews or just want to strengthen your understanding of bitwise operations, you’re in the right place. In this article, we’ll dive deep into two classic problems: swapping two numbers without using a temporary variable and checking if the Kth bit is set in a number’s binary representation. We’ll explain everything in simple, plain English to make it easy for students to follow along.
These problems are common in platforms like GeeksforGeeks and LeetCode, and they help build a strong foundation in data structures and algorithms. We’ll cover problem statements, intuitions, approaches, code examples, dry runs, edge cases, and time/space complexities. By the end, you’ll feel confident tackling similar challenges.
Let’s start with the first problem.
Swap Two Numbers Without a Temporary Variable
Swapping two numbers is a basic operation, but doing it without extra space (like a temporary variable) is a neat trick using bitwise XOR. This method is efficient and works in constant time, making it perfect for constrained environments.
Problem Statement
Objective: Swap the values of two integers, a and b, without using any temporary variable.
Expected Input and Output:
- Input: Two integers, a and b.
- Output: A list containing the swapped values [b, a].
Examples:
- Example 1:
- Input: a = 13, b = 9
- Output:
- Explanation: After swapping, a becomes 9 and b becomes 13.
- Example 2:
- Input: a = 15, b = 8
- Output:
- Explanation: After swapping, a becomes 8 and b becomes 15.
Constraints:
- 1 ≤ a, b ≤ 10^6
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
This problem is straightforward but teaches us about bitwise operations’ power. You don’t need to handle input/output; just complete the function that returns the swapped list.
Intuition and Approach
Intuition: We use the XOR (^) operator, a bitwise operation that flips bits. XOR has useful properties:
- Any number XOR itself is 0 (e.g., x ^ x = 0).
- Any number XOR 0 is itself (e.g., x ^ 0 = x).
- XOR is associative and commutative, so x ^ y ^ x = y.
These properties allow us to swap without losing data. Imagine XOR as a way to “encode” and “decode” values temporarily.
Approach:
- First, set a = a ^ b. Now, a holds the combined info of both numbers.
- Then, set b = a ^ b. This cancels out the original b and leaves b with the original a.
- Finally, set a = a ^ b. This cancels out the original a and leaves a with the original b.
- Return the list [a, b] with swapped values.
This works because each step builds on the previous one, using XOR to toggle between values.
Code Example in Python
Here’s the simple Python code for the solution:
class Solution:
def get(self, a, b):
a = a ^ b # Step 1: a now holds XOR of original a and b
b = a ^ b # Step 2: b now holds original a
a = a ^ b # Step 3: a now holds original b
return [a, b]Code Explanation:
- First XOR: a = a ^ b → a becomes a mix of a and b.
- Second XOR: b = a ^ b → Since a is now (original a ^ b), this becomes (original a ^ b) ^ b = original a (because b ^ b = 0).
- Third XOR: a = a ^ b → Now a is (original a ^ b) ^ original a = original b (because original a ^ original a = 0).
- Finally, return the swapped [a, b].
This is elegant and uses no extra space.
Dry Run with Example
Let’s simulate with a = 3, b = 5 (binary: 3 is 011, 5 is 101).
- Initial: a = 3 (011), b = 5 (101)
- Step 1: a = 3 ^ 5 = 011 ^ 101 = 110 (6 in decimal)
- Step 2: b = 6 ^ 5 = 110 ^ 101 = 011 (3, original a)
- Step 3: a = 6 ^ 3 = 110 ^ 011 = 101 (5, original b)
- Return: [5,erfect swap! Try it with your own numbers to see.
Edge Cases
Potential Edge Cases:
- Identical Values: a = 4, b = 4. XOR with same values gives 0, so it stays the same (which is correct for swap).
- Zero Values: a = 0, b = 5. Works fine: 0 ^ 5 = 5, then 5 ^ 5 = 0, then 5 ^ 0 = 5 → [5, Maximum Values: a = 10^6, b = 1. Handles large numbers since XOR is bitwise.
The method is robust and doesn’t fail in these scenarios because of XOR’s properties.
Time and Space Complexity
- Time Complexity: O(1) – Just three constant-time operations, no loops.
- Space Complexity: O(1) – No extra space used, only the input variables.
This makes it optimal for interviews where efficiency matters.
Now, let’s move to the second problem, which also uses bit manipulation.
Check if the Kth Bit is Set or Not
This problem tests your ability to inspect individual bits in a number’s binary form. It’s useful in scenarios like flag checking or low-level programming.
Problem Statement
Objective: Determine if the Kth bit (0-based index from the right) in the binary representation of n is set (1) or not (0).
Expected Input and Output:
- Input: Integer n and integer k (bit position).
- Output: “Yes” if set, “No” if not (but in code, we return True/False).
Examples:
- Input: n = 4 (binary 100), k = 0 → Output: No (0th bit is 0)
- Input: n = 4 (binary 100), k = 2 → Output: Yes (2nd bit is 1)
- Input: n = 500 (binary 111110100), k = 3 → Output: No (3rd bit is 0)
Constraints:
- 1 ≤ n ≤ 10^9
- 0 ≤ k ≤ 31
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Note: Bits are counted from the least significant bit (rightmost) as 0.
We’ll cover two optimal ways: using left shift and right shift. Both are efficient.
Optimal Solution 1: Using Left Shift Operator
Intuition: Create a “mask” with only the Kth bit set to 1, then AND it with n. If the result isn’t zero, the bit is set.
Approach:
- Shift 1 left by k positions: mask = 1 << k (e.g., for k=2, 1 becomes 100).
- Do n & mask. If >0, bit is set.
- Return True or False.
This isolates the exact bit we care about.
Code Example in Python (Left Shift)
class Solution:
def checkKthBit(self, n, k):
if n & (1 << k) != 0:
return True
return FalseCode Explanation:
- 1 << k creates a number with only the Kth bit as 1.
- n & that number keeps only the Kth bit from n.
- If it’s not zero, the bit was 1; else, 0.
Simple and direct.
Dry Run for Left Shift
Input: n=5 (101), k=2
- Mask: 1 << 2 = 100 (4)
- 5 & 4 = 100 (4, non-zero) → True (bit is set)
Another: n=4 (100), k=0
- Mask: 1 << 0 = 1 (001)
- 4 & 1 = 0 → False
Edge Cases for Left Shift
- k=0: Checks LSB correctly.
- k > bits in n: E.g., n=5 (3 bits), k=3 → 1<<3=8, 5&8=0 → False (correct, as higher bits are 0).
- n=0: Any k → False.
Handles all nicely.
Time and Space Complexity (Left Shift)
- Time: O(1) – Constant operations.
- Space: O(1) – No extra space.
Optimal Solution 2: Using Right Shift Operator
Intuition: Move the Kth bit to the rightmost position, then check if it’s 1.
Approach:
- Shift n right by k: n >> k (Kth bit now at position 0).
- AND with 1: (n >> k) & 1. If 1, bit was set.
- Return True or False.
This “slides” the bit into an easy-to-check spot.
Code Example in Python (Right Shift)
class Solution:
def checkKthBit(self, n, k):
if (n >> k) & 1 == 1:
return True
return FalseCode Explanation:
- n >> k moves bits right, putting Kth at LSB.
- & 1 extracts that bit (1 if set, 0 if not).
Equally efficient.
Dry Run for Right Shift
Input: n=5 (101), k=2
- 5 >> 2 = 1 (001)
- 1 & 1 = 1 → True
Another: n=4 (100), k=0
- 4 >> 0 = 4 (100)
- 4 & 1 = 0 (since LSB is 0) → False
Edge Cases for Right Shift
- k=0: Directly checks LSB.
- k > bits in n: Shifts to 0, &1=0 → False.
- n=0: Always False.
Robust like the left shift method.
Time and Space Complexity (Right Shift)
- Time: O(1) – Constant.
- Space: O(1) – Minimal.
Both methods are great; choose based on preference. Left shift might feel like “masking,” right shift like “extracting.”
Why Learn These Bit Manipulation Techniques?
Bit manipulation is crucial for optimizing code in terms of speed and space, especially in embedded systems or competitive programming. Problems like these appear in interviews at companies like Google, Amazon, and Microsoft. Practicing them builds intuition for more complex topics like bitmasks or dynamic programming with bits.
If you’re new, try implementing these in your favorite language and test with different inputs. For more practice, check GeeksforGeeks links provided in the references.
References and Further Reading
- Swap Two Numbers: GeeksforGeeks Problem
- Check Kth Bit: GeeksforGeeks Problem
Feel free to comment below if you have questions or share your own solutions! Stay tuned for more coding tutorials.
