Bit Manipulation: A Powerful Tool for Efficient Programming

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.

Binary representation

Computers only understand binary — a series of 1s and 0s.

They have no concept of:

• Negative numbers
• Arithmetic signs like + or –

But in the real world, we frequently deal with positive and negative numbers. So we need a binary system that can represent both positive and negative integers in a way that:

• Is easy to implement in hardware (CPU)
• Supports correct arithmetic (addition, subtraction)
• Is efficient in memory
• Doesn’t create ambiguity (like multiple ways to represent zero)

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 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, even multiplication — all work with the same binary logic.

• No need for if/else or separate “signed math unit”

  5: 00000101
 -5: 11111011  (Two’s complement)
----------------
Sum: 00000000

Seamless Wraparound

If you keep incrementing the max positive number, you automatically get the most negative number.

For 8-bit:

+127 = 01111111
+128 (overflow) → -128 = 10000000

This “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 =1

The 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   => 1

OR (|):

• 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 = 7

XOR (^):

• 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 = 6

Properties

• 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 bitwise complement).

~x = -x - 1

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 = -25

Which 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.

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 to binary(number)

x = 5  # 101 in binary
print(x << 1)  # 10 (1010) # No loss of bits
print(x << 2)  # 20 (10100) # No loss of bits

1 << 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

Read more

Why 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

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 bits

Loss 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 separate negative sign representation.

2's complement(2^n) = 1's complement + 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 -5

Case 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 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 behavior, we need to manually mask it:

C or C++:

• int, short, 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

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) #13

OR (|) – 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))   # -0b1101

Note:

• Python uses infinite-bit integers, so ~x = -(x + 1)
• ~12 = -13 because 00001100 → 11110011 (in 8-bit) → -13 in two’s complement

Combine: Clear specific bit using AND with 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: 00001111

n & mask: This keeps only the lowest bits of n and discards everything else.

Used for finding 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, 5

Explanation

a = a ^ b        # a becomes a^b
b = a ^ b        # b becomes (a^b)^b => a
a = a ^ b        # a becomes (a^b)^a => b

Clearing the Rightmost Set Bit

• Clears the lowest set bit.
• E.g., 12 (1100) → 8 (1000)

n & (n - 1)

Special case

if a number is of power of 2, n&(n-1) = 0

Checking if a Number is a Power of Two

Leetcode 231

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))  # False

Explanation

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) = 0000

Special 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 = 0

Result 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)) == 0

Counting the Number of Set Bits (Hamming Weight)

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)

Normal method

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    

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: 5

Finding 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 2)

Setting 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 it works?

• 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 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)

Count set bits (Brian Kernighan’s Algorithm)

def count_bits(x):
    count = 0
    while x:
        x &= (x - 1)  # remove lowest 1
        count += 1
    return count

Turn off k-th bit

x & ~(1 << k)

Turn on k-th bit

x | (1 << k)

Toggle k-th bit

x ^ (1 << k)

Check if k-th bit is set

(x >> k) & 1

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 optimization.
• 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.

268. Missing Number

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = 0
        for n in range(len(nums)):
            result^= n^nums[n]

        return len(nums)^result

Conclusion

Bit manipulation is a powerful technique that enables efficient computations in various fields. Mastering bitwise operations allows programmers to write optimized code and solve complex problems with minimal resource consumption. By practising and applying these tricks, developers can improve their problem-solving skills and enhance the performance of their applications.

Resource

• Bit Multiplication
• Geeksforgeeks