Mastering Bit Manipulation: Unleashing the Power of Binary Operations

Bit manipulation is a powerful technique in programming that allows you to perform operations at the bit level, often leading to more efficient algorithms and lower memory usage. This powerful skill can significantly enhance your coding prowess, making your code more elegant and effective, whether you are working on competitive programming, system programming, or performance-critical applications. In this article, we will explore some of the coolest bit manipulation tricks and hacks you can use to optimize your code.

Check if a Number is Even or Odd

Easily determine if a number is even or odd by checking the least significant bit (LSB). Here’s how you can do it:

is_even  (num  1)  0

Swap Two Numbers Without a Temporary Variable

Swap two numbers using the XOR technique, a clever and memory-efficient method:

a  a ^ bb  a ^ ba  a ^ b

Set a Specific Bit

Set the k-th bit of a number n to 1:

n  n | (1 

Clear a Specific Bit

Clear the k-th bit of a number n:

n  n  ~(1 

Toggle a Specific Bit

Toggle the k-th bit of a number n:

n ^ (1 

Check if a Number is a Power of Two

A number is a power of two if it has exactly one bit set:

is_power_of_two  (num  (-num))  num

Count the Number of Set Bits (Hamming Weight)

Count the number of 1s in a binary representation. Here’s a simple approach:

count  0
while num:
    count   num  1
    num >> 1

Alternatively, use Brian Kernighan’s algorithm, which is more efficient:

count  0
while num:
    count   1
    num  (num - 1)

Reverse Bits

Reverse the bits of a number. Here’s an illustrative function:

def reverse_bits(n):
    result  0
    for i in range(32):
        result  (result > 1
    return result

Find the Maximum of Two Numbers Without Conditional Statements

Determine the maximum of two numbers without using conditional statements:

def max(a, b):
    return a - ((a - b)  ((a - b)  31))

Find the Lowest Set Bit

Find the lowest set bit of a number:

lowest_set_bit  n  (-n)

Rotate Bits

Rotate bits to the left or right:

Left Rotate

def left_rotate(n, d):
    return (n  d) | (n  (32 - d))

Right Rotate

def right_rotate(n, d):
    return (n  d) | (n  (32 - d))

Bitwise AND of All Numbers in a Range

Find the bitwise AND of all numbers from m to n:

while n ! m:
    n  n  (n - 1)

Bit manipulation is a vital skill for enhancing coding efficiency. These tricks can be particularly useful in competitive programming, system programming, and any scenario where performance is crucial. Mastering these techniques will not only make your code more efficient but also more elegant and succinct.