Bit manipulation is a fundamental technique in programming that involves operating directly on bits—the basic units of information in computers. It enables high-performance solutions for many computational problems, particularly in competitive programming, cryptography, embedded systems, and optimisation tasks. Understanding bitwise operations can significantly improve code efficiency and reduce execution time.
Table of Contents
Binary Number
Computers only understand binary — a series of 1s and 0s.
Binary representation is a way of expressing numbers using only two digits: 0 and 1. It is the fundamental language used by computers because digital systems operate using two states—typically represented as off (0) and on (1).
In binary, each position represents a power of 2, starting from the right. For example, the binary number 1011 can be understood as:
1x2^3 + 0x2^2 + 1x2^1 + 1x2^0 = 8 + 0 + 2 + 1 = 11Binary representation is used to store all types of data in a computer, including numbers, text, images, and instructions. For integers, computers typically use formats like unsigned binary or two’s complement (for representing negative numbers).
This system is important because it directly maps to hardware operations, making computations efficient and reliable in digital electronics.
Binary representation
At a low level, everything in a computer is just bits (0s and 1s). But how those bits are interpreted makes all the difference. Two of the most important ways to interpret binary numbers are unsigned binary and two’s complement.
Unsigned Binary Representation
Unsigned binary is the simplest form of number representation. In this system, all bits are used purely to represent the magnitude (value) of the number. There is no concept of negative numbers.
Each bit position corresponds to a power of 2. Starting from the rightmost bit (least significant bit), the powers increase:
2^0, 2^1, 2^2, and so on.
For example, consider the binary number 1011:
1x2^3 + 0x2^2 + 1x2^1 + 1x2^0 = 8 + 0 + 2 + 1 = 11So, 1011 represents 11 in decimal.
If we use n bits, the range of numbers we can represent is:
- Minimum: 0
- Maximum:2^n -1
For example:
- 4 bits → 0 to 15
- 8 bits → 0 to 255
This system is straightforward and efficient when you only need non-negative values. However, it completely fails when negative numbers are required.
The Need for Signed Representation
In real-world computations, we frequently deal with positive and negative numbers. So we need a binary system that can represent both positive and negative integers. You need them for subtraction, balances, temperature values, and much more. Simply reserving one bit as a sign (like “+” or “−”) is not enough because it complicates arithmetic operations.
This is where two’s complement comes in—a clever system that allows both positive and negative numbers while keeping arithmetic simple and consistent.
Using the sign bit
First bit = sign
- 0 → positive
- 1 → negative
Remaining bits = value
Example (4 bits):
| Binary | Meaning |
|---|---|
| 0101 | +5 |
| 1101 | -5 |
Problem 1: Two zeros
You get two representations of zero:
- 0000 → +0
- 1000 → -0
👉 Computers don’t like this—it creates ambiguity.
Problem 2: Arithmetic becomes messy
Let’s try addition:
(+5) + (-5)
0101
+ 1101
------
10010 (incorrect in simple sign system)Now what?
- You need special rules to handle the sign separately
- The addition logic becomes complicated
👉 Hardware becomes inefficient
Problem 3: Extra logic needed
With the sign-bit method:
- Addition ≠ subtraction
- You need separate handling for:
- positive + positive
- positive + negative
- negative + negative
👉 This increases complexity a lot
Why Two’s Complement Fixes This
Two’s complement removes all these issues:
- Only one zero
- Same logic for addition & subtraction
- No need to treat the sign separately
Example: (+5) + (-5)
00000101
+ 11111011
-----------
00000000 ✅ correctNo special handling needed.
How to Represent Negatives in Binary?
Let’s say we’re using 8 bits to store numbers. That’s 2⁸ = 256 possible combinations.
We want to represent:
- Positive numbers (e.g., 0 to +127)
- Negative numbers (e.g., -1 to -128)
We need a way to use those 256 patterns to represent both signed and unsigned integers.
Why not just use a “Sign Bit”?
A naive method is the sign-magnitude representation:
- First bit = sign (0 = positive, 1 = negative)
- Remaining bits = magnitude
Example:
- +5 = 00000101
- -5 = 10000101
Problems with this approach:
Two zeros:
- 00000000 (0) and 10000000 (-0)
- Hard to compare, sort, or check for equality
Arithmetic is hard:
- Adding +5 and -5 doesn’t naturally give 0
- CPU must write special logic for different sign cases
More complexity, more bugs
Two’s Complement: A Better Way
Two’s complement solves all of these problems:
Single Zero
- 0 = 00000000
- No negative zero.
Unified Arithmetic
Addition, subtraction, and even multiplication — all work with the same binary logic.
- No need for if/else or a separate “signed math unit”
5: 00000101
-5: 11111011 (Two’s complement)
----------------
Sum: 00000000Seamless Wraparound
If you keep incrementing the max positive number, you automatically get the most negative number.
For 8-bit:
+127 = 01111111
+128 (overflow) → -128 = 10000000This “wrapping” is exactly how unsigned integers work, too — reusing existing logic.
Read More about 2’s Complement
Understanding Bitwise Operators
Bitwise operations work at the binary level and are faster than arithmetic operations. In most programming languages, the following bitwise operators are available:
AND (&):
Sets a bit if both corresponding bits are 1.
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
24 & 16 => 11000 & 10000 => 10000=> 16
5 & 3 => 1101 & 0011 => 0001 => 1 Properties
AND with 1
5&1 => 1101 & 0001 => 1
4&1 => 100 & 001 => 0
15&1 =>1111 & 0001 => 1
24&1 => 11000 & 00001 => 0 Even Odd
We have either 1 or 0, based on the results
- If 1, the number is odd
- If 0, the number is even
Explanation
see all odd ends with 1 , even with 0
0 -> 000
1 -> 001
2 -> 010
3 -> 011
4 -> 100
5 -> 101
6 -> 110
7 -> 111
1 -> 1
so a&1
even 0&1 = 0
odd 1&1 =1The last bit of binary representation
- 24=>11000 => 0
- 15=>1111 => 1
Remainder: It gives a remainder when dividing the number by 2
24 % 2 => 24 & 1 => 0
15 % 2 => 15 & 1 => 1OR (|):
- Sets a bit if at least one of the corresponding bits is 1.
- Example: 5 | 3 (0101 | 0011) = 0111 (7 in decimal)
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
5 | 3 = 0101| 0011 = 0111 = 7XOR (^):
- Sets a bit if only one of the corresponding bits is 1.
- Example: 5 ^ 3 (0101 ^ 0011) = 0110 (6 in decimal)
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
5 ^ 3 = 0101 ^ 0011 = 0110 = 6Properties
- XOR of a number with itself is zero (x^x = 0)
- XOR of a number with zero is the number itself (x^0=x)
- XOR is reversible and commutative (x^y=y^x)
NOT (~):
- Inverts all bits (also known as the bitwise complement).
~x = -x - 1
-x is represented using the 2’s complement of x
Proof
~x = -x - 1 (~x → flips all bits (1's complement))
1's complement = -x -1
1's complement +1 = -x
2's complement = -x
So, to store -x, we take the 2’s complement of x
Example
1 = 00000000 00000000 00000000 00000001
~1 = 11111111 11111111 11111111 11111110 → -2 (in two's complement)
x = 5 # Binary: 00000101
print(~x) # Output: -6 (Binary: 11111010)
x = 8
~x = -9
x = 24
~x = -25Example
x -> ~x
0 -> -1
1 -> -2
2 -> -3
3 -> -4
4 -> -5Which one ~1 =0 or ~001 = 110 ?
~1 = 0 is wrong:
That would only happen if 1 had a single bit, which is not how integers are stored in memory.
What actually happens with ~1:
- The bitwise NOT (~) does NOT turn 1 into 0.
- Instead, it flips every bit in the binary representation of the number.
Because numbers are stored in two’s complement form (to represent signed integers), flipping bits of 1 results in the binary representation of -2, not 0.
Example
Binary for 1 (in 8 bits for simplicity):
00000001
Bitwise NOT flips bits:
11111110 # In two's complement, 11111110 represents -2, not 0.Bit deeper
- MSB tells sign ✔️
- If MSB = 0 → read normally
- If MSB = 1 → number is already in 2’s complement form
- → decode (flip + 1) to get magnitude
- → then add a negative sign
Wrong example
- 0011 → 3 ✅
- 1011 → NOT -3 ❌
Leftmost is negative, but it does mean put a -ve sign get number (e.g., -3)
Correct example
Let’s decode 1011 (4-bit):
- MSB is negative
- So, it’s in 2’s complement form
- Now decode (two’s complement):
- Flip → 0100
- +1 → 0101 = 5
- put the sign = -5 ✅
Conclusion
MSB = 0 → direct
MSB = 1 → flip + 1 → add minusBinary numbers in a computer are already stored correctly
- Positive numbers → stored directly
- Negative numbers → stored in two’s complement form
We decode only when the number is negative (MSB = 1), to understand its decimal value.
Bitwise NOT vs Logical NOT
- ~ is bitwise NOT — flips bits.
- ! or not is logical NOT — flips truthiness (True to False, 1 to 0 logically).
~0 = 1
~1 = 0
Example: ~5 (0101) = 1010 (in two’s complement representation, this is -6)Left Shift (<<):
- Shifts bits to the left, effectively multiplying by powers of 2.
- Example: 5 << 1 (0101 << 1) = 1010 (10 in decimal)
- number<<n; n zeroes will be added to the left side of the binary(number)
x = 5 # 101 in binary
print(x << 1) # 10 (1010) # No loss of bits
print(x << 2) # 20 (10100) # No loss of bits1 << bits
1 << bits = 2^bits
1 = 001 = 1 = 2^0
1<<2 = 100 = 4 = 2^2
1<<10 => 2^10
1 << bits = 2^bits(1 << bits) – 1
This gives a bitmask with all bits set to 1.
- For 8-bit:
- (1 << 8) – 1 = 256 – 1 = 255 → binary: 11111111
- For 4-bit:
- (1 << 4) – 1 = 16 – 1 = 15 → binary: 1111
1<<8 = 1 0000 0000 => it become 9 bits
so -1 => will max value of 8 bit
1<<8 = 2^8 = 256Why It’s Needed
Python integers are unbounded (no fixed size), but hardware integers are not.
- This trick forces Python to behave like an N-bit machine.
- It trims the number to N bits as hardware would store it.
Summary
| Expression | Meaning |
|---|---|
1 << bits | Powers of 2 (e.g., 256 for 8-bit) |
(1 << bits) - 1 | Mask with bits 1s (e.g., 255 = 0b11111111) |
n & mask | Keep only bits bits from n |
Right Shift (>>):
- Shifts bits to the right, effectively dividing by powers of 2.
- Example: 5 >> 1 (0101 >> 1) = 0010 (2 in decimal)
x = 20 # 10100 in binary
print(x >> 1) # 10 (1010) #loss of bits
print(x >> 2) # 5 (101) #loss of bitsLoss of bits
When you perform a right shift (>>), bits are lost because they move out of the lower end of the number. However, in a left shift (<<), no bits are lost because integers can grow dynamically.
What is Two’s Complement?
Two’s complement is the most common method of representing signed integers in binary systems. It simplifies arithmetic operations and eliminates the need for a separate negative sign representation.
2's complement(2^n) = 1's complement + 1
1's complement(2^n) = ~x
2's complement(2^n) = ~x + 1
Two’s complement is a method for encoding signed integers so that:
- Positive and negative numbers can be represented.
- Arithmetic operations (addition, subtraction) work the same way as unsigned numbers.
- There’s only one representation for zero.
- The most significant bit (leftmost bit) is the sign bit:
- 0 means positive
- 1 means negative
Example
Example 1
+5 00000101
-5 11111011
Step 1 : 5 -> 00000101
Step 2 : invert all bit 11111010
Step 3 : Add 1:11111010+1 = 11111011
So, -5 = 11111011
Example 2
+8 00001000
-8 11111000
Step 1 : 8 -> 00001000
Step 2 : invert all bit 11110111
Step 3 : Add 1:11110111+1 = 11111000
So, -8 = 11111000
Code for 2’s complement
Case 1: n = ~n+1
- Invert the bits → ~5
- Add 1
Example for 8bit
+5 = 00000101
~5 = 11111010
+1 = 11111011 ← This is the 8-bit two's complement of -5Case 2: Using Mask: n & ((1 << bits) – 1)
This is the programmatic trick that simulates the same thing automatically:
Forces Python to:
- Mask off only the lowest N bits (like 8 or 16)
- Simulate fixed-width integers
- Match how real machines store and represent negative values using two’s complement.
Example for 8-bit
-5 & ((1 << 8) - 1)
= -5 & 255
= 251
= 11111011
Why is case 2 required?
Case 2 is required for some programming languages, like Python
- Python integers are arbitrary precision (they grow as big as needed).
- Python does not automatically wrap around bits like hardware does.
- So, to simulate hardware-like behaviour, we need to manually mask it:
C or C++:
- int, short, and char have fixed sizes (e.g., int = 32 bits).
- You don’t need to mask it, because the hardware + compiler already does the wraparound and bit-limiting for you.
When you do:
int n = -5;
printf("%x", n);
C automatically stores -5 using two’s complement in 32-bit, e.g.:
Summary
| Language | Integer Type | Two’s Complement Needed? | Use Mask? |
|---|---|---|---|
| Python | Arbitrary precision | Not automatic | Must use n & ((1<<bits)-1) |
| C/C++ | Fixed-size (e.g., int32) | Automatic | Not needed |
| Java | Fixed-size (int, byte) | Automatic | Not needed |
In Python,
- We use n & ((1 << bits) – 1) to simulate what languages like C do natively.
- ((1 << bits) – 1) Forces the result to be clipped to exactly N bits, just like hardware would do.
- You must manually restrict the result to a fixed number of bits — because Python doesn’t do it for you.
Python Stores integers with unlimited bits, but hardware. Uses fixed-size bits (e.g., 8, 16, 32). So to simulate fixed-size behaviour in Python, we use this
Programming 2’s complement in Python
Way1: Dynamic bits
def twos_complement(n, bits):
return format(n & ((1 << bits) - 1), f'0{bits}b')
print(" 5 (8-bit):", twos_complement(5, 8)) # 00000101
print(" -5 (8-bit):", twos_complement(-5, 8)) # 11111011
print(" 5 (16-bit):", twos_complement(5, 16)) # 0000000000000101
print(" -5 (16-bit):", twos_complement(-5, 16)) # 1111111111111011
print(" 5 (4-bit):", twos_complement(5, 4)) # 0101
print(" -5 (4-bit):", twos_complement(-5, 4)) # 1011
Way 2: Fixed Width
- 1<<bits => 2^bit
- (1<<bits) -1 => 2^bit-1
2^bit-1 represents the maximum value that can be represented using bit number of bits.
# For 4-bit
def twos_complement_4bit(n):
return format(n & 0xF, '04b') # 0xF = 15 = 4 bits
# For 16-bit
def twos_complement_16bit(n):
return format(n & 0xFFFF, '016b') # 0xFFFF = 65535 = 16 bits
# For 32-bit
def twos_complement_32bit(n):
return format(n & 0xFFFFFFFF, '032b') # 0xFFFFFFFF = 32 bits
Bitmask
Just like a mask on your face hides part of it, a bitmask “hides” or “focuses” on specific bits in a number.
AND (&) – Clear everything except selected bits
Use case: Keep only specific bits (e.g. lower 4 bits)
x = 0b10101101 # 173 in decimal
mask = 0b00001111 # Mask to keep only the last 4 bits
result = x & mask
# 10101101
# &00001111
# --------
# 00001101 → 0b00001101 → 13
print(result) # 13
print(bin(result)) # 0b1101
print(173&15) #13OR (|) – Set specific bits to 1
Use case: Turn on certain bits (e.g. set the 4th bit)
x = 0b00001001 # 9 in decimal
mask = 0b00000100 # Bit to set (3rd bit)
result = x | mask
# 00001001
# |00000100
# --------
# 00001101 → 0b00001101 → 13
print(result) # 13
print(bin(result)) # 0b1101
XOR (^) – Toggle specific bits
Use case: Flip certain bits (e.g. toggle 0 → 1 or 1 → 0)
x = 0b00001100 # 12
mask = 0b00000110 # Toggle 2nd and 3rd bits
result = x ^ mask
# 00001100
# ^00000110
# --------
# 00001010 → 0b00001010 → 10
print(result) # 10
print(bin(result)) # 0b1010
NOT (~) – Invert all bits
Use case: Flip every bit (used in two’s complement, bitwise tricks)
x = 0b00001100 # 12
result = ~x
print(result) # -13 (in Python, infinite-bit integer)
print(bin(result)) # -0b1101Note:
- Python uses infinite-bit integers, so ~x = -(x + 1)
- ~12 = -13 because 00001100 → 11110011 (in 8-bit) → -13 in two’s complement
Combine: Clear a specific bit using AND with an inverted bitmask
Clear (set to 0) the 3rd bit:
x = 0b00001111 # 15
mask = ~(1 << 2) # Clear bit at position 2 (count from 0)
result = x & mask
# 00001111
# &11111011
# --------
# 00001011 → 0b00001011 → 11
print(result) # 11
print(bin(result)) # 0b1011
'''
1 = 001
1<<2 = 100
~100 = 011
result = x&011
'''Keeps only the lowest bits of n and discards everything else.
n & ((1 << bits) - 1)(1 << bits) – 1: This gives a bitmask with all bits set to 1.
For 8-bit:
(1 << 8) - 1 = 256 - 1 = 255 → binary: 11111111
For 4-bit:
(1 << 4) - 1 = 16 - 1 = 15 → binary: 00001111n & mask: This keeps only the lowest bits of n and discards everything else.
Used for finding the two’s complement. Read
Common Bit Manipulation Tricks
Checking if a Number is Even or Odd
A number is odd if its last bit is 1, even if its last bit is 0.
if num & 1:
print("Odd")
else:
print("Even")Swapping Two Numbers Without a Temporary Variable
a = 5
b = 3
a = a ^ b
b = a ^ b
a = a ^ b
print(a, b) # Output: 3, 5Explanation
a = a ^ b # a becomes a^b
b = a ^ b # b becomes (a^b)^b => a^0 => a
a = a ^ b # a becomes (a^b)^a => 0^b => bClearing the Rightmost Set Bit
- Clears the lowest set bit.
- E.g., 12 (1100) → 8 (1000)
n & (n - 1)
n = 12 → 1100
n - 1 = 11 → 1011
------------------
AND → 1000 = 8- If the last bit of n is 1, then n-1 will be 0 => 1&0 = 0(last bit)
- If the last bit of n is 0, then n-1 will be 1 => 0%1 = 0(last bit)
Special case
If a number is a power of 2, n&(n-1) = 0
Checking if a Number is a Power of Two
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
print(is_power_of_two(16)) # True
print(is_power_of_two(18)) # FalseExplanation
Logic 1: Any power of two in binary has exactly one bit set to 1.
- 1 → 0001
- 2 → 0010
- 4 → 0100
- 8 → 1000
- 16 → 10000
Logic 2: Subtracting 1 from a power of two flips all the bits after the single 1.
- n = 1000 (e.g., 8)
- n – 1 = 0111 (e.g., 7)
Logic 3: n & (n-1) == 0 → means only one bit was set in n → power of two
n = 1000 (e.g., 8)
n - 1 = 0111 (e.g., 7)
n & (n-1) = 0000Special case
- n = 0
- n – 1 = -1
But what is -1 in binary?
In Python (and most languages), negative numbers are represented using two’s complement.
For 32-bit integers:
0 = 00000000 00000000 00000000 00000000
-1 (in two’s complement) = 11111111 11111111 11111111 11111111
0 & -1
= 00000000...0000
& 11111111...1111
= 00000000...0000
0 & -1 = 0Result is 0, i.e., it’s a power of 2, which is wrong. Hence, we need to handle this (n>0)
n > 0 and (n & (n - 1)) == 0Counting the Number of Set Bits
Finding the number of 1s/set bits
Hamming Weight (Naive Bit Counting)
def count_set_bits(self, n: int) -> int:
count =0
while(n>=1):
reminder = n%2
if reminder==1:
count+=1
n = n//2
return count Hamming Weight(Bitwise)
def count_set_bits(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
print(count_set_bits(15)) # Output: 4 (1111 has four 1s)- Checks every bit
- Time: O(number of bits)
Brian Kernighan’s Algorithm
def count_bits(x):
count = 0
while x:
x = x & (x - 1) # remove lowest 1
count += 1
return count- Runs only for set bits
- Time: O(number of 1s) (faster when bits are sparse)
Key Difference
- Hamming → scans all bits
- Kernighan → skips zeros, directly removes 1s
Finding the Only Non-Repeating Element in an Array
Using XOR, we can find a unique element when every other element appears twice.
def find_unique(arr):
result = 0
for num in arr:
result^= num
return result
print(find_unique([2, 3, 5, 3, 2])) # Output: 5Finding the Position of the Rightmost Set Bit
- Useful in problems like finding subsets or Binary Indexed Trees.
- E.g., 10 (1010) → 2 (0010)
def rightmost_set_bit(n):
return n & -n
print(rightmost_set_bit(18)) # Output: 2 (Binary: 10010, rightmost set bit is at(0010) => 2 )
print(rightmost_set_bit(16)) # 16| n | binary | n & -n (value) | position |
|---|---|---|---|
| 18 | 10010 | 2 | 1 |
| 12 | 1100 | 4 | 2 |
| 16 | 10000 | 16 | 4 |
n = 12
1100 & 0100 = 0100Setting the Rightmost 0 Bit
E.g., 1011 → 1111
n | (n + 1)Clears the lowest set bit
- Removes the rightmost 1-bit from x.
- x & (x – 1)
x = 12 # binary: 1100
x - 1 = 11 = 1011
x & (x - 1) = 1100 & 1011 = 1000 (8)Why does it work?
- Subtracting 1 flips all bits after the rightmost 1 (including that 1).
- So when you AND it with the original, that rightmost 1 becomes 0.
Use cases:
- Count the number of set bits (used in Brian Kernighan’s Algorithm)
- Check if a number is a power of two
Isolates the lowest set bit
- Keeps only the rightmost 1-bit; all others become 0.
- x & -x
x = 12 # binary: 1100
-x = -12 = 2's comp = 0100
x & -x = 1100 & 0100 = 0100 (4)Why it works:
- -x is the two’s complement of x
- So x & -x leaves only the lowest 1-bit
Use cases:
- Bitmasking
- Subset enumeration
- Binary indexed trees (Fenwick trees)
Sets all bits after the lowest set bit
- Turns all bits after the rightmost 1-bit into 1s
- x | (x – 1)
x = 12 # 1100
x - 1 = 11 = 1011
x | (x - 1) = 1100 | 1011 = 1111 (15)All bits up to the lowest set bit become 1
- Turns all bits up to and including the lowest 1-bit into 1s
- x ^ (x – 1)
x = 12 # 1100
x - 1 = 11 = 1011
x ^ (x - 1) = 1100 ^ 1011 = 0111 (7)Observation
- 1 << k → only k-th bit = 1
- 👉 Takes us to the target position(k)
- XOR (^) → toggle
- Same → 0
- Different → 1
- 👉 flips bit
- OR (|) → force 1
- Anything OR 1 → 1
- 👉 sets bit
- AND (&) → force 0
- Anything AND 0 → 0
- 👉 clears bit
Turn off the k-th bit
x & ~(1 << k)
'''
Example
x = 10 (1010)
k = 1 → 1010 & 1101 = 1000
'''Turn on the k-th bit
x | (1 << k)
'''
Example
x = 10 (1010)
k = 0 → 1010 | 0001 = 1011
k = 1 → 1010 | 0010 = 1010 (already 1)
'''Toggle k-th bit
x ^ (1 << k)
'''
Example
x = 10 (1010)
k = 1 → 1010 ^ 0010 = 1000 (bit flipped)
k = 2 → 1010 ^ 0100 = 1110
'''Check if the k-th bit is set(get the k-th bit)
(x >> k) & 1
'''
Example
x = 10 (1010)
k = 1 → (1010 >> 1) = 0101 → & 1 = 1 ✅
k = 2 → (1010 >> 2) = 0010 → & 1 = 0 ❌
''''Multiplication Using Bit Manipulation
Bitwise shifts can be used to perform fast multiplication by powers of 2. Instead of using the multiplication operator, shifting left (<<) effectively multiplies a number by 2^k.
The left shift operator (n << k) is equivalent to multiplying n by 2^k. This is because shifting a binary number left by k positions effectively multiplies it by 2^k
Examples:
17n = 16n + n = n * pow(2,4) + n = (n << 4) + n
7n = 8n - n = n * pow(2,3) - n = (n << 3) - n
54n = 64n -10n = n * pow(2,6) - 10n = (n << 6) - 10n
Why Use This?
- Bitwise shifts are faster than multiplication because they are simple bit manipulations at the CPU level.
- This is commonly used in low-level programming (e.g., embedded systems, performance-sensitive code).
Applications of Bit Manipulation
- Competitive Programming: Faster solutions for problems involving subsets, bitmasking, and optimisation.
- Cryptography: Bitwise operations play a crucial role in encryption algorithms.
- Embedded Systems: Used for direct hardware manipulation in microcontrollers.
- Image Processing: Manipulation of pixel values at the bit level.
- Networking: Efficient routing, packet processing, and error detection.
Practice
Missing number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
class Solution:
def missingNumber(self, nums: List[int]) -> int:
result = 0
for n in range(len(nums)):
result^= n^nums[n] # n : 0 to n-1
return len(nums)^result #len(nums) to get n XOR all elements of the array with all numbers from 0 to n. Since identical numbers cancel each other out (a ^ a = 0), every matched pair disappears, leaving only the missing number.
Steps
- XOR all indices (0 → n-1)
- XOR all values in the array
- Finally XOR with n
- a ^ a = 0 (cancels out)
- Only the missing number remains
nums = [3,0,1]
elements = 3^0^1
as we know element will exist in range 0 to N, so xor with this number as well
range = 0^1^2^3
final result = elements^range
= 3^0^1 ^ 0^1^2^3
= (0^0) ^ (1^1) ^ (3^3) ^ 2
= 0 ^ 0 ^ 0 ^ 2
= 2 Instead of using two separate loops—one to XOR all array elements and another to XOR numbers from 0 to n—we combine both operations into a single loop for better efficiency.
Conclusion
Bit manipulation is a powerful technique that enables efficient computations in various fields. Mastering bitwise operations allows programmers to write optimised code and solve complex problems with minimal resource consumption. By practising and applying these tricks, developers can improve their problem-solving skills and enhance their applications’ performance.
1 thought on “Bit Manipulation: A Powerful Tool for Efficient Programming”