In programming, efficiency is crucial, and bit manipulation is one of the most powerful techniques for achieving it. At the core of every computer, data is represented as binary sequences of 0's and 1's — bits. Directly manipulating these bits allows you to optimize performance, save memory, and simplify algorithms, often achieving faster and more space-efficient solutions than traditional methods. Bit manipulation is especially useful in competitive programming, embedded systems, and scenarios where performance is a priority. In this blog, we’ll explore the essential bit manipulation operations and demonstrate how to apply them in problem-solving, helping you sharpen your coding skills and tackle challenges more effectively.
Basic Bit Manipulation Operations
1.AND (&):
Compares two bits and returns 1 if both are 1, otherwise it returns 0.
| X | Y | X & Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Example:
a = 10001
b = 11111
a & b = 10001
2.OR (|):
Compares two bits and returns 1 if atleast one of the bits is 1 , otherwise it produces 0.
| X | Y | X | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Example:
a = 10001
b = 11111
a | b = 11111
3.NOT (~):
It changes 1 to 0 and vice versa.
| X | ~X |
|---|---|
| 0 | 1 |
| 1 | 0 |
Example:
a = 10001
~a = 01110
4.Left Shift (<<):
Left shift moves bits to the left, filling the rightmost positions with zeros. This is equivalent to multiplying by 2 for each shift.
Example:
a = 5 (in binary: 101)
a << 2 = 10100 (which equals 20, i.e., 5 * 2 * 2 = 20)
5.Right Shift (>>):
Right shift moves bits to the right, which is equivalent to division by 2 for each shift.
Example:
a = 5 (in binary: 101)
a >> 2 = 1 (which equals 1, i.e., 5 / 2 / 2 = 1)
6.XOR (^):
XOR compares the bits and returns 1 if the bits are different, and 0 if the bits are the same. XOR is often called the "odd 1 detector."
| X | Y | X ^ Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Now that we've covered the basics of bit manipulation, let's apply these operations to solve some common problems. Below are some examples and their solutions.
1. Check If a Number Is Odd or Even
Problem Description:
To determine if a number is odd or even, we use a bitwise AND operation with 1. If the least significant bit (LSB) is 1, the number is odd; if it is 0, the number is even.
Approach:
Perform num & 1.
If the result is 0, the number is even.
If the result is 1, the number is odd.
num = int(input("Enter a number: "))
if num & 1:
print("Odd")
else:
print("Even")
2. Count the Number of 1's in a Binary Representation of a Number
Problem Description:
This approach repeatedly checks the LSB of the number using the bitwise AND operation with 1. Each time a 1 is found, we increment the count. The number is right-shifted in every iteration until all bits are processed.
Approach:
Keep shifting the number right while checking the LSB.
Count the number of times the LSB is 1
def countOnes(num):
count = 0
while num:
count += (num & 1)
num >>= 1
return count
num = int(input("Enter a number: "))
print(f"Number of 1s: {countOnes(num)}")
3. Check If a Number Is a Power of 2:
Problem Description:
A number is a power of two if it has exactly one bit set in its binary representation. Using the condition num & (num - 1), we can clear the rightmost set bit and check if the result is 0.
Approach:
Perform num & (num - 1).
If the result is 0 and the number is greater than 0, the number is a power of 2.
def isPowerOfTwo(num):
return num > 0 and (num & (num - 1)) == 0
num = int(input("Enter a number: "))
if isPowerOfTwo(num):
print("Power of 2")
else:
print("Not a power of 2")
print(f"Number of 1s: {countOnes(num)}")
4. Change the Bit of a Number at a Particular Position:
Problem Description:
To modify a bit at a specific position in a number, we use bitwise OR to set the bit to 1 and bitwise AND with a complemented mask to set the bit to 0. This allows precise control over the binary representation of the number.
Approach:
Use the bitwise OR operation to set a bit to 1.
Use the bitwise AND operation with the complement to set a bit to 0.
def changeBit(num, pos, bit):
if bit == 1:
num |= (1 << pos) # Set bit to 1
else:
num &= ~(1 << pos) # Set bit to 0
return num
num = int(input("Enter a number: "))
pos = int(input("Enter position of bit to change: "))
bit = int(input("Enter the bit value (0 or 1): "))
num = changeBit(num, pos, bit)
print(f"Updated number: {num}")
5. Find the Single Number in an Array:
Problem Description:
When every element in an array appears exactly twice except for one, XOR operation can help identify the unique element. XOR cancels out duplicate values, leaving only the single number.
Approach:
Use XOR to cancel out duplicate elements. Since 𝑎⊕𝑎=0,
and 𝑎⊕0=𝑎, XORing all elements will leave only the unique number.
def findSingleNumber(arr):
result = 0
for num in arr:
result ^= num
return result
size = int(input("Enter the size of the array: "))
arr = [int(input(f"Enter element {i + 1}: ")) for i in range(size)]
print(f"Single number: {findSingleNumber(arr)}")
6. Check Whether Two Numbers Have Opposite Signs:
Problem Description:
The XOR operation can determine if two numbers have opposite signs by checking the sign bit. If the result of XOR is negative, the numbers have opposite signs.
Approach:
Use XOR: if the result is negative, the numbers have opposite signs.
def haveOppositeSigns(a, b):
return (a ^ b) < 0
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
if haveOppositeSigns(a, b):
print("Opposite signs")
else:
print("Same sign")
7. Swap Two Numbers Without Using a Temporary Variable:
Problem Description:
Swapping two numbers without using extra memory can be achieved using the XOR operation. It allows the values to be exchanged in-place through three XOR operations.
Approach:
Use XOR to swap two numbers.
def swap(a, b):
a ^= b
b ^= a
a ^= b
return a, b
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
a, b = swap(a, b)
print(f"Swapped: a = {a}, b = {b}")
8. Reverse the Bits of a Number:
Problem Description:
Reversing the bits of a number involves iteratively shifting the bits to construct the reversed number while extracting bits from the original number.
Approach:
Use bitwise shifts and OR to reverse the bits.
def reverseBits(num):
reversed = 0
while num:
reversed = (reversed << 1) | (num & 1)
num >>= 1
return reversed
num = int(input("Enter a number: "))
print(f"Reversed bits: {reverseBits(num)}")
Conclusion
Bit manipulation is a powerful technique that allows you to solve problems efficiently by working directly with binary representations of numbers. Mastering these fundamental operations can significantly improve your problem-solving skills, especially when working with time and memory constraints.
For more examples and detailed code snippets, feel free to explore the repository where these problems and solutions are implemented: BitManipulation_Github
Top comments (1)
Helpful.
Thanks for sharing