DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for "The Power of Bit Manipulation: How to Solve Problems Efficiently"
Anurag Verma
Anurag Verma

Posted on • Updated on

"The Power of Bit Manipulation: How to Solve Problems Efficiently"

There are a few key topics that are important to understand when it comes to bit manipulation in competitive programming:

  1. Bitwise operations: It is important to understand how to use the bitwise operators (e.g., &, |, ^, ~, <<, >>) to perform various operations on binary numbers.

  2. Bitmasking: Bitmasking is a technique for setting, clearing, or checking individual bits in a number. It can be useful for representing a set of flags or for implementing certain algorithms efficiently.

  3. Bit manipulation tricks: There are a number of "tricks" that involve using bit manipulation to solve problems in clever ways. For example, you can use the x & (-x) idiom to isolate the rightmost 1-bit in a number, or you can use the x & (x - 1) idiom to clear the rightmost 1-bit in a number.

  4. Bit manipulation-based algorithms: There are a number of algorithms that make use of bit manipulation to solve problems efficiently. For example, you can use the divide and conquer approach to implement a fast algorithm for finding the median of a set of numbers, or you can use bit manipulation to implement a fast algorithm for multiplying two numbers.

Overall, it is important to have a strong foundation in the basics of bit manipulation and to be familiar with a variety of techniques and algorithms that make use of bit manipulation. Practice is also key to mastering these concepts, so it is a good idea to solve as many problems as you can that involve bit manipulation.

But don't worry here I have covered all topics in detail to "Become a Bit Manipulation Pro"

Bitwise operations:

Bitwise operations allow you to perform operations on binary numbers at the bit level. In Python, you can use the following bitwise operators:

  • &: Bitwise AND. This operator compares each bit of the first operand to the corresponding bit of the second operand, and if both bits are 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0. For example:
x = 0b10101010  # The number 170 in binary
y = 0b01010101  # The number 85 in binary
z = x & y  # The result is 0b00000000, or 0 in decimal
Enter fullscreen mode Exit fullscreen mode
  • |: Bitwise OR. This operator compares each bit of the first operand to the corresponding bit of the second operand, and if either bit is 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0. For example:
x = 0b10101010  # The number 170 in binary
y = 0b01010101  # The number 85 in binary
z = x | y  # The result is 0b11111111, or 255 in decimal
Enter fullscreen mode Exit fullscreen mode
  • ^: Bitwise XOR. This operator compares each bit of the first operand to the corresponding bit of the second operand, and if the bits are different, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0. For example:
x = 0b10101010  # The number 170 in binary
y = 0b01010101  # The number 85 in binary
z = x ^ y  # The result is 0b11111111, or 255 in decimal
Enter fullscreen mode Exit fullscreen mode
  • ~: Bitwise NOT. This operator flips all the bits of the operand. For example:
x = 0b10101010  # The number 170 in binary
y = ~x  # The result is -171 in decimal
Enter fullscreen mode Exit fullscreen mode
  • <<: Left shift. This operator shifts the bits of the operand to the left by the number of positions specified by the second operand. For example:
x = 0b10101010  # The number 170 in binary
y = x << 2  # The result is 0b1010101000, or 680 in decimal
Enter fullscreen mode Exit fullscreen mode
  • >>: Right shift. This operator shifts the bits of the operand to the right by the number of positions specified by the second operand. For example:
x = 0b10101010  # The number 170 in binary
y = x >> 2  # The result is 0b00101010, or 42 in decimal
Enter fullscreen mode Exit fullscreen mode

Bitmasking:

Bitmasking is a technique for setting, clearing, or checking individual bits in a number. It involves using bitwise operators to manipulate the bits of a number in order to set or clear specific bits or to check the values of specific bits.

For example, suppose you have a number x and you want to set the third and fifth bits (counting from the right) to 1. You can do this using the following code:

x = 0b00000000  # The number 0 in binary
mask = 0b00101000  # The mask with the third and fifth bits set to 1
x = x | mask  # The result is 0b00101000, or 40 in decimal
Enter fullscreen mode Exit fullscreen mode

Alternatively, suppose you have a number x and you want to clear the fourth and sixth bits (counting from the right). You can do this using the following code:

x = 0b11111111  # The number 255 in binary
mask = 0b11010111  # The mask with the fourth and sixth bits set to 0
x = x & mask  # The result is 0b11010111, or 215 in decimal
Enter fullscreen mode Exit fullscreen mode

Bitmasking can also be used to check the values of specific bits in a number. For example, suppose you have a number x and you want to check if the seventh bit (counting from the right) is set to 1. You can do this using the following code:

x = 0b11010111  # The number 215 in binary
mask = 0b10000000  # The mask with the seventh bit set to 1
if x & mask:
    print("The seventh bit is set to 1")
else:
    print("The seventh bit is not set to 1")
Enter fullscreen mode Exit fullscreen mode

Bitmasking is often used in programming to represent a set of flags or to implement certain algorithms efficiently. For example, you might use bitmasking to represent a set of permissions (e.g., read, write, execute) or to implement a fast algorithm for finding the intersection of two sets.

Suppose you want to represent a set of flags that indicate whether a user has read, write, and execute permissions for a particular file. You could define the following constants:

READ_PERMISSION = 0b001
WRITE_PERMISSION = 0b010
EXECUTE_PERMISSION = 0b100
Enter fullscreen mode Exit fullscreen mode

These constants represent the flags for each of the permissions, with the rightmost bit representing the read permission, the second rightmost bit representing the write permission, and the third rightmost bit representing the execute permission.

To represent a set of permissions for a particular user, you could use a variable of type int and set the appropriate bits using bitmasking. For example:

permissions = 0b000  # No permissions

# Grant the user read permission
permissions = permissions | READ_PERMISSION  # The result is 0b001

# Grant the user write permission
permissions = permissions | WRITE_PERMISSION  # The result is 0b011

# Grant the user execute permission
permissions = permissions | EXECUTE_PERMISSION  # The result is 0b111
Enter fullscreen mode Exit fullscreen mode

To check whether a user has a particular permission, you can use bitmasking to check the value of the corresponding bit. For example:

if permissions & READ_PERMISSION:
    print("The user has read permission")

if permissions & WRITE_PERMISSION:
    print("The user has write permission")

if permissions & EXECUTE_PERMISSION:
    print("The user has execute permission")
Enter fullscreen mode Exit fullscreen mode

Bit manipulation tricks:

Bit manipulation tricks are techniques that involve using bit manipulation to solve problems in clever ways. Here are a few examples of common bit manipulation tricks:

  • Isolating the rightmost 1-bit: You can use the x & (-x) idiom to isolate the rightmost 1-bit in a number. For example:
x = 0b01010101  # The number 85 in binary
y = x & (-x)  # The result is 0b00000001, or 1 in decimal
Enter fullscreen mode Exit fullscreen mode
  • Clearing the rightmost 1-bit: You can use the x & (x - 1) idiom to clear the rightmost 1-bit in a number. For example:
x = 0b01010101  # The number 85 in binary
y = x & (x - 1)  # The result is 0b01010100, or 84 in decimal
Enter fullscreen mode Exit fullscreen mode
  • Checking if a number is a power of 2: You can use the x & (x - 1) == 0 idiom to check if a number is a power of 2. For example:
x = 8  # The number 8 is a power of 2
if x & (x - 1) == 0:
    print("x is a power of 2")

x = 9  # The number 9 is not a power of 2
if x & (x - 1) == 0:
    print("x is a power of 2")  # This line will not be executed
Enter fullscreen mode Exit fullscreen mode
  • Counting the number of 1-bits: You can use the x &= (x - 1) idiom to count the number of 1-bits in a number. For example:
x = 0b01010101  # The number 85 in binary
count = 0
while x:
    count += 1
    x &= (x - 1)
print(count)  # The output is 4
Enter fullscreen mode Exit fullscreen mode
  • Swapping the values of two variables: You can use bit manipulation to swap the values of two variables without using a temporary variable. For example:
x = 10
y = 20

# Swap the values of x and y
x ^= y
y ^= x
x ^= y

print(x)  # The output is 20
print(y)  # The output is 10
Enter fullscreen mode Exit fullscreen mode
  • Checking if a number is odd or even: You can use the x & 1 idiom to check if a number is odd or even. For example:
x = 10  # The number 10 is even
if x & 1:
    print("x is odd")
else:
    print("x is even")

x = 11  # The number 11 is odd
if x & 1:
    print("x is odd")
else:
    print("x is even")
Enter fullscreen mode Exit fullscreen mode
  • Determining the sign of a number: You can use the x >> 31 idiom to determine the sign of a number. For example:
x = 10  # The number 10 is positive
if x >> 31:
    print("x is negative")
else:
    print("x is positive")

x = -10  # The number -10 is negative
if x >> 31:
    print("x is negative")
else:
    print("x is positive")
Enter fullscreen mode Exit fullscreen mode
  • Calculating the absolute value of a number: You can use the (x + (x >> 31)) ^ (x >> 31) idiom to calculate the absolute value of a number. For example:
x = 10  # The absolute value of 10 is 10
y = (x + (x >> 31)) ^ (x >> 31)
print(y)  # The output is 10

x = -10  # The absolute value of -10 is 10
y = (x + (x >> 31)) ^ (x >> 31)
print(y)  # The output is 10
Enter fullscreen mode Exit fullscreen mode
  • Reversing the bits of a number: You can use bit manipulation to reverse the bits of a number. For example:
x = 0b01010101  # The number 85 in binary
y = 0

# Reverse the bits of x
for i in range(8):
    y = (y << 1) | (x & 1)
    x >>= 1

print(y)  # The output is 0b10101010, or 170 in decimal
Enter fullscreen mode Exit fullscreen mode
  • Calculating the logarithm of a number: You can use bit manipulation to calculate the logarithm of a number. For example:
x = 256  # The logarithm of 256 is 8
y = 0
while x > 1:
    y += 1
    x >>= 1
print(y)  # The output is 8
Enter fullscreen mode Exit fullscreen mode
  • Calculating the square root of a number: You can use bit manipulation to calculate the square root of a number. For example:
x = 256  # The square root of 256 is 16
y = 0
while x > 0:
    y += 1
    x >>= 2
print(y)  # The output is 16
Enter fullscreen mode Exit fullscreen mode
  • Calculating the greatest common divisor of two numbers: You can use bit manipulation to calculate the greatest common divisor (GCD) of two numbers. For example:
def gcd(x, y):
    while y > 0:
        x, y = y, x % y
    return x
Enter fullscreen mode Exit fullscreen mode
  • Calculating the least common multiple of two numbers: You can use bit manipulation to calculate the least common multiple (LCM) of two numbers. For example:
def lcm(x, y):
    return (x * y) // gcd(x, y)  # gcd() is the function that calculates the GCD

x = 10
y = 15
z = lcm(x, y)  # The result is 30
Enter fullscreen mode Exit fullscreen mode
  • Calculating the parity of a number: You can use bit manipulation to calculate the parity of a number (i.e., whether the number has an even or odd number of 1-bits). For example:
x = 0b01010101  # The number 85 in binary
y = 0

# Calculate the parity of x
while x:
    y ^= 1
    x &= (x - 1)

if y:
    print("The number has an odd number of 1-bits")
else:
    print("The number has an even number of 1-bits")
Enter fullscreen mode Exit fullscreen mode
  • Calculating the Hamming distance between two numbers: You can use bit manipulation to calculate the Hamming distance between two numbers (i.e., the number of bit positions in which the numbers differ). For example:
x = 0b01010101  # The number 85 in binary
y = 0b10101010  # The number 170 in binary
z = 0

# Calculate the Hamming distance between x and y
while x or y:
    z += (x & 1) ^ (y & 1)
    x >>= 1
    y >>= 1

print(z)  # The output is 8
Enter fullscreen mode Exit fullscreen mode

Bit manipulation-based algorithms:

Certainly! Bit manipulation can be used to implement a variety of algorithms efficiently. Here are a few examples of algorithms that can be implemented using bit manipulation:

  • Bitonic sort: Bitonic sort is an efficient sorting algorithm that can be implemented using bit manipulation. It works by dividing the input array into pairs of elements and comparing them using bit manipulation. The algorithm then recursively sorts the resulting arrays using the same process.

  • Bitwise trie: A bitwise trie is a data structure that can be used to store and retrieve data efficiently. It works by using bit manipulation to store the data in a tree-like structure, with each bit of the data serving as a branch in the tree.

  • Bitmap: A bitmap is a data structure that can be used to store a large number of boolean values efficiently. It works by using bit manipulation to store the values in an array of bits, with each bit representing a boolean value.

  • Hash table: A hash table is a data structure that can be used to store and retrieve data efficiently. It works by using bit manipulation to compute the hash value of the data, which is then used to index into an array of buckets.

These are just a few examples of algorithms that can be implemented using bit manipulation. There are many other algorithms that can be implemented efficiently using bit manipulation, including algorithms for searching, sorting, and data compression. But are example code so you all can understand effectively.

Bitonic sort:

def bitonic_sort(arr):
    # Base case: return the array if it has 1 or 0 elements
    if len(arr) <= 1:
        return arr

    # Divide the array into two halves
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # Recursively sort the two halves
    left = bitonic_sort(left)
    right = bitonic_sort(right)

    # Compare the elements in the two halves using bit manipulation
    for i in range(mid):
        if (left[i] > right[i]) == (i & 1):
            left[i], right[i] = right[i], left[i]

    # Concatenate the sorted halves and return the result
    return left + right

arr = [3, 7, 4, 8, 6, 2, 1, 5]
sorted_arr = bitonic_sort(arr)
print(sorted_arr)  # The output is [1, 2, 3, 4, 5, 6, 7, 8]
Enter fullscreen mode Exit fullscreen mode

Bitwise trie:

class BitwiseTrie:
    def __init__(self):
        self.children = [None, None]

    def insert(self, num):
        node = self
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if not node.children[bit]:
                node.children[bit] = BitwiseTrie()
            node = node.children[bit]

trie = BitwiseTrie()
trie.insert(85)  # Insert the number 85 (0b01010101) into the trie
trie.insert(170)  # Insert the number 170 (0b10101010) into the trie
Enter fullscreen mode Exit fullscreen mode

Bitmap:

class Bitmap:
    def __init__(self, size):
        self.bits = [0] * ((size + 31) // 32)

    def set_bit(self, pos):
        self.bits[pos // 32] |= (1 << (pos % 32))

    def clear_bit(self, pos):
        self.bits[pos // 32] &= ~(1 << (pos % 32))

    def get_bit(self, pos):
        return self.bits[pos // 32] & (1 << (pos % 32))

bitmap = Bitmap(100)  # Create a bitmap with 100 bits
bitmap.set_bit(10)  # Set the 11th bit (counting from the right) to 1
bitmap.clear_bit(10)  # Clear the 11th bit (counting from the right)
if bitmap.get_bit(10):
    print("The 11th bit (counting from the right) is set to 1")
else:
    print("The 11th bit (counting from the right) is not set to 1")
Enter fullscreen mode Exit fullscreen mode

Hash table:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.buckets = [None] * size

    def hash_function(self, key):
        # Compute the hash value using bit manipulation
        hash_value = 0
        for c in key:
            hash_value = (hash_value << 5) + hash_value + ord(c)
        return hash_value % self.size

    def insert(self, key, value):
        # Compute the hash value of the key
        hash_value = self.hash_function(key)

        # Insert the key-value pair into the appropriate bucket
        self.buckets[hash_value] = (key, value)

    def lookup(self, key):
        # Compute the hash value of the key
        hash_value = self.hash_function(key)

        # Look up the key-value pair in the appropriate bucket
        return self.buckets[hash_value]

hash_table = HashTable(100)  # Create a hash table with 100 buckets
hash_table.insert("apple", "red")  # Insert the key-value pair "apple"-"red"
hash_table.insert("banana", "yellow")  # Insert the key-value pair "banana"-"yellow"
print(hash_table.lookup("apple"))  # The output is ("apple", "red")
print(hash_table.lookup("banana"))  # The output is ("banana", "yellow")
Enter fullscreen mode Exit fullscreen mode

"In conclusion, bit manipulation is a powerful tool that can help programmers solve problems efficiently and effectively. Whether you are competing in programming contests or working on real-world projects, a strong understanding of bit manipulation can give you a competitive edge.

To master bit manipulation, it is important to practice using it to solve problems. You can find many online resources, such as online judges and programming contests, that offer challenges that can help you hone your skills. You can also create your own problems to solve, or explore more advanced techniques such as bit manipulation-based algorithms and data structures.

There are many resources available for learning about bit manipulation, including books, online tutorials, and blogs. Take the time to explore these resources and continue learning about this important topic. With dedication and practice, you can become a bit manipulation pro and unlock the full potential of this powerful tool.

I hope you liked this post...sharing love and knowledge...

Happy coding...

Buy Me A Coffee

Top comments (15)

Collapse
 
cicirello profile image
Vincent A. Cicirello

You don't want to use the 3 xor swap trick. It is clever, but that is it. If you measure, you'll see it is slower than just using temp variable and 3 assignment statements. And it is less readable. So you sacrifice readability without gaining anything.

Collapse
 
anurag629 profile image
Anurag Verma

I am not sure but it will faster in other programming language😊.

Collapse
 
cicirello profile image
Vincent A. Cicirello

No, it won't be. I've measured specifically in Java. But it should be slower regardless of language. You essentially have 3 xors, plus 3 assignments for the xor trick. The more straightforward way is just 3 assignments plus declaration of temp variable. The 3 xors will be slower than the variable declaration.

Thread Thread
 
anurag629 profile image
Anurag Verma • Edited on

Ohhh i missed it. I think i should take rest from bit manipulation as i messed up these things πŸ™„πŸ€―πŸ€―πŸ˜‡

How i can do this..... πŸ˜’πŸ˜’πŸ€¬πŸ€¬

Collapse
 
cicirello profile image
Vincent A. Cicirello • Edited on

Good list of bit manipulation operations.

A good book for more bit manipulation is:

Hacker's Delight is a software algorithm book by Henry S. Warren, Jr. first published in 2002. It presents fast bit-level and low-level arithmetic algorithms for common tasks such as counting bits or improving speed of division by using multiplication.

It has some some of the tricks from your post and faster versions of others. For example, you can count 1-bits without a loop. Plus many more.

Collapse
 
anurag629 profile image
Anurag Verma

Thanks @cicirello for book I will go through this book and update this post as early as possible.

Collapse
 
cicirello profile image
Vincent A. Cicirello

Another way of isolating right most bit:

y = x & 1
Enter fullscreen mode Exit fullscreen mode
Collapse
 
anurag629 profile image
Anurag Verma

YES 😊.😊.

Collapse
 
bhagatharsh profile image
BhagatHarsh

Great read, brushed up my old bit manipulation skills😁.

Collapse
 
anurag629 profile image
Anurag Verma

Thanks @bhagatharsh Follow me for such more content.

Collapse
 
dinifarb profile image
DiniFarb

Thanks, I really enjoyed reading this article 😊

Collapse
 
anikethsdeshpande profile image
Aniketh Deshpande

Very nice list of tricks!

Collapse
 
anurag629 profile image
Anurag Verma

Thanks

Collapse
 
avtozavodetz profile image
avtozavodetz • Edited on

Thanks for the useful article!
But it looks like gcd example has some mistake: it returns None, and % should be used instead of &.

Collapse
 
anurag629 profile image
Anurag Verma

Thanks @avtozavodetz for correction.

Create an Account!
Now it's your turn!
Β 
πŸ—’ Share a tutorial
πŸ€” Reflect on your coding journey
❓ Ask a question

Create an account to join hundreds of thousands of DEV members on their journey.