Table of Contents

• Introduction
• How does the conversion from Decimal to Binary work? [^1][^2]
• Code - Decimal to Binary and Vice-Versa Conversion
• 1's and 2's complement
• Bitwise Operators
• Shortcuts to Problems using Bit Manipulation
• Swap two numbers without using a temporary variable
• Check if the ith bit (from the right) is set in the binary representation of a number
• Set the ith bit (from the right) in the binary representation of a number
• Clear the ith bit (from the right) in the binary representation of a number
• Toggle the ith bit (from the right) in the binary representation of a number
• Removing the ith bit (from the right) in the binary representation of a number
• Remove the rightmost set bit in the binary representation of a number
• Check if a number is a power of 2
• Count the number of set bits in the binary representation of a number
• References:

Introduction

Bit manipulation is a fundamental technique in computer science, with applications ranging from low-level system programming to high-performance algorithms. As a developer working with data structures and algorithms, understanding how to effectively manipulate bits can be a powerful tool in your arsenal, allowing you to write more efficient, compact, and optimized code. In this comprehensive cheatsheet, we'll dive deep into the world of bit manipulation, exploring the key operations, techniques, and use cases that are essential for any aspiring algorithm engineer or computer scientist.

How does the conversion from Decimal to Binary work? ¹²

All we have to do is, divide the decimal representation of the number by 2 and repeat the process until the quotient is 1. Then we traverse from bottom to up!

Code - Decimal to Binary and Vice-Versa Conversion

def decimal_to_binary(num):
    binary = ''
    while num > 0:
        binary = str(num % 2) + binary ''' Notice how it's `remainder plus existing string`, instead of the other way around, 
        since we are travelling from bottom to top. Alternatively we can perform, `binary + remainder` and reverse the string.'''
        num = num // 2
    return binary

def binary_to_decimal(binary):
    decimal = 0
    for digit in binary:
        decimal = decimal * 2 + int(digit)
    return decimal

1's and 2's complement

1. To find the 1's complement of a number, we flip all the bits.
2. To find the 2's complement of a number, we flip all the bits and add 1. Then we flip the resultant number.

Pro tip: You can find the negative representation of a number by deriving it's 2's complement.

Bitwise Operators

1. AND &

A & B = 1 if both A and B are 1
A & B = 0 if either A or B is 0
example: 101 & 110 = 100

2. OR |

A | B = 1 if either A or B is 1
A | B = 0 if both A and B are 0
example: 101 | 110 = 111

3. XOR ^

A ^ B = 1 if either A or B is 1 but not both
A ^ B = 0 if both A and B are 0
Simple rule: if number of 1's are even then 0 else 1
example: 101 ^ 110 = 011

4. NOT ~

5. Flip the bits of a number. 1.a. Use the 32/64 bit representation of the number. If the number is negative, flip the bits (other than the bit used to represnet the sign) and add 1. 1.b. If the number is positive, stop.

~A = 1 if A is 0
~A = 0 if A is 1
example: ~101 = 010
example: ~010 = 101

5. Left Shift <<

Left shifting is equivalent to multiplying a number by 2^[Number of bits shifted].

A << B = A * 2^B
example: 101 << 2 = 10100

6. Right Shift >>

Right shifting is equivalent to dividing a number by 2^[Number of bits shifted].

A >> B = A / 2^B
example: 101 >> 2 = 001

Shortcuts to Problems using Bit Manipulation

Swap two numbers without using a temporary variable

Use the XOR operator to swap two numbers without using a temporary variable.

A = A ^ B
B = A ^ B
A = A ^ B

Check if the ith bit (from the right) is set in the binary representation of a number

Use the AND operator to check if the ith bit is set in the binary representation of a number.

if (A & (1 << i))!= 0: 
  
# Or (A >> i) & 1 !=0

    print("Bit is set")
else:
    print("Bit is not set")

Set the ith bit (from the right) in the binary representation of a number

Use the OR operator to set the ith bit in the binary representation of a number.

A = A | (1 << i)

Clear the ith bit (from the right) in the binary representation of a number

Use the AND operator to clear the ith bit in the binary representation of a number together with the NOT operator.

A = A & ~(1 << i)

Toggle the ith bit (from the right) in the binary representation of a number

Use the XOR operator to toggle the ith bit in the binary representation of a number.

A = A ^ (1 << i)

Removing the ith bit (from the right) in the binary representation of a number

Use the AND operator to remove the ith bit in the binary representation of a number together with the NOT operator.

A = A & ~(1 << i)

Remove the rightmost set bit in the binary representation of a number

Use the AND operator to remove the rightmost set bit in the binary representation of a number together with the NOT operator.

A = A & (A - 1)

Example:
Let's say A = 52 (binary 110100):
1. A = 52 (110100)
2. A - 1 = 51 (110011)
3. A & (A - 1) = 110100 & 110011 = 110000 (48 in decimal)
As you can see, the rightmost set bit (the 4 in 52) has been removed.

Check if a number is a power of 2

Use the AND operator to check if a number is a power of 2.

if A & (A - 1) == 0:
    print("A is a power of 2")
else:
    print("A is not a power of 2")

Count the number of set bits in the binary representation of a number

count = 0
while A:
    count += A & 1
    A >>= 1
print(count)

Or use the approach of counting and eliminating the righmost bit iteratively.

count = 0
while A:
    A = A & (A - 1)
    count += 1
print(count)

Performing bitwise operations is typically faster than mathematical operations.

Pro tip: Use if (n&1)==0 to check if a number is odd/even, instead of using the modulo operator

Pro tip: Use n>>1 to divide by two instead of using the divison operator

References: