Algorithm Bit Manipulation Techniques Complete Guide

Table of Contents

1. Introduction to Bit Manipulation
2. Basic Bitwise Operators
3. Setting a Bit
4. Clearing a Bit
5. Toggling a Bit
6. Checking if a Bit is Set
7. Counting Set Bits (Hamming Weight)
8. Swapping Bits
9. Bitwise Operations in Different Programming Languages

1. Introduction to Bit Manipulation

Bit manipulation involves the manipulation of individual bits within a binary number. It uses bitwise operations to perform these manipulations. The applications of bit manipulation include optimizing algorithms, handling permissions, and more.

2. Basic Bitwise Operators

Before we dive into specific techniques, let's review the basic bitwise operators:

• AND (&): Performs a binary AND operation bit by bit.
• OR (|): Performs a binary OR operation bit by bit.
• XOR (^): Performs a binary XOR operation bit by bit.
• NOT (~): Performs a binary NOT operation (inverts all bits).
• Left Shift (<<): Shifts the bits of a number to the left.
• Right Shift (>>): Shifts the bits of a number to the right.

Example

int a = 5;    // Binary: 0101
int b = 3;    // Binary: 0011

int and_result = a & b;   // Result: 0001 (Decimal: 1)
int or_result = a | b;    // Result: 0111 (Decimal: 7)
int xor_result = a ^ b;   // Result: 0110 (Decimal: 6)
int not_result = ~a;      // Result: 11111111111111111111111111111010 (Decimal: -6 on 32-bit systems)
int left_shift = a << 1;  // Result: 1010 (Decimal: 10)
int right_shift = a >> 1; // Result: 0010 (Decimal: 2)

3. Setting a Bit

To set (turn on) a specific bit, you can use the OR operator with a mask that has 1 at the bit position you want to set.

Formula: num |= (1 << pos)

Where:

• num is the original number.
• pos is the position of the bit you want to set (0-indexed from the right).

Example

Setting the 2nd bit (0-indexed) of 5 (Binary: 0101).

int num = 5;  // Binary: 0101
int pos = 2;

int result = num | (1 << pos); // Result: 0111 (Decimal: 7)

4. Clearing a Bit

To clear (turn off) a specific bit, you can use the AND operator with a mask that has 0 at the bit position you want to clear and 1 at all other positions.

Formula: num &= ~(1 << pos)

Where:

• num is the original number.
• pos is the position of the bit you want to clear (0-indexed from the right).

Example

Clearing the 2nd bit (0-indexed) of 5 (Binary: 0101).

int num = 5;  // Binary: 0101
int pos = 2;

int result = num & ~(1 << pos); // Result: 0101 (Decimal: 5, no change since the 2nd bit was already 0)

5. Toggling a Bit

To toggle (flip) a specific bit, you can use the XOR operator with a mask that has 1 at the bit position you want to toggle.

Formula: num ^= (1 << pos)

Where:

• num is the original number.
• pos is the position of the bit you want to toggle (0-indexed from the right).

Example

Toggling the 0th bit (0-indexed) of 5 (Binary: 0101).

int num = 5;  // Binary: 0101
int pos = 0;

int result = num ^ (1 << pos); // Result: 0100 (Decimal: 4)

6. Checking if a Bit is Set

To check if a specific bit is set (i.e., if it is 1), you can use the AND operator with a mask that has 1 at the bit position you want to check.

Formula: (num & (1 << pos)) != 0

Where:

• num is the original number.
• pos is the position of the bit you want to check (0-indexed from the right).

Example

Checking if the 2nd bit (0-indexed) of 5 (Binary: 0101) is set.

int num = 5;  // Binary: 0101
int pos = 2;

bool is_set = (num & (1 << pos)) != 0; // Result: true (the 2nd bit is set)

7. Counting Set Bits (Hamming Weight)

Counting the number of bits set to 1 in a number is often referred to as calculating the Hamming Weight. It is commonly used in algorithms that require determining the number of 1s in the binary representation of a number.

Formula (Brian Kernighan's Algorithm): num &= (num - 1)

Where:

• num is the original number.

Example

Counting the number of set bits in 5 (Binary: 0101).

int num = 5;  // Binary: 0101
int count = 0;

while (num != 0) {
    num &= (num - 1);
    count++;
}

// Result: count = 2 (Binary 0101 has two 1s)

8. Swapping Bits

Swapping two bits in a number involves multiple steps: extracting the bits, clearing them, and then setting them in the new positions.

Steps:

1. Extract the bits at positions pos1 and pos2.
2. Clear the bits at positions pos1 and pos2.
3. Set the bit extracted from pos1 to pos2 and vice versa.

Example

Swapping the 0th and 2nd bits (0-indexed) of 5 (Binary: 0101).

int num = 5;  // Binary: 0101
int pos1 = 0;
int pos2 = 2;

// Step 1: Extract bits at pos1 and pos2
int bit1 = (num >> pos1) & 1; // Result: 1 (0th bit)
int bit2 = (num >> pos2) & 1; // Result: 1 (2nd bit)

// Step 2: Clear bits at pos1 and pos2
num &= ~(1 << pos1);
num &= ~(1 << pos2);

// Step 3: Set bits at new positions
num |= (bit2 << pos1); // Set extracted bit from pos2 to pos1
num |= (bit1 << pos2); // Set extracted bit from pos1 to pos2

// Result: num = 0111 (Decimal: 7)

9. Bitwise Operations in Different Programming Languages

Let's see how the same concepts can be applied in different programming languages.

C++

#include <iostream>

int main() {
    int num = 5;  // Binary: 0101
    int pos = 2;

    // Setting a bit
    int set_result = num | (1 << pos);
    std::cout << "Setting bit: " << set_result << std::endl;

    // Clearing a bit
    int clear_result = num & ~(1 << pos);
    std::cout << "Clearing bit: " << clear_result << std::endl;

    // Toggling a bit
    int toggle_result = num ^ (1 << pos);
    std::cout << "Toggling bit: " << toggle_result << std::endl;

    // Checking a bit
    bool is_set = (num & (1 << pos)) != 0;
    std::cout << "Bit is set: " << is_set << std::endl;

    // Counting set bits
    int count = 0;
    int temp = num;
    while (temp != 0) {
        temp &= (temp - 1);
        count++;
    }
    std::cout << "Number of set bits: " << count << std::endl;

    return 0;
}

Python

def set_bit(num, pos):
    return num | (1 << pos)

def clear_bit(num, pos):
    return num & ~(1 << pos)

def toggle_bit(num, pos):
    return num ^ (1 << pos)

def check_bit(num, pos):
    return (num & (1 << pos)) != 0

def count_set_bits(num):
    count = 0
    while num != 0:
        num &= (num - 1)
        count += 1
    return count

num = 5  # Binary: 0101
pos = 2

# Setting a bit
set_result = set_bit(num, pos)
print("Setting bit:", set_result)

# Clearing a bit
clear_result = clear_bit(num, pos)
print("Clearing bit:", clear_result)

# Toggling a bit
toggle_result = toggle_bit(num, pos)
print("Toggling bit:", toggle_result)

# Checking a bit
is_set = check_bit(num, pos)
print("Bit is set:", is_set)

# Counting set bits
count_bits = count_set_bits(num)
print("Number of set bits:", count_bits)

Java

public class BitManipulation {
    public static void main(String[] args) {
        int num = 5;  // Binary: 0101
        int pos = 2;

        // Setting a bit
        int set_result = setBit(num, pos);
        System.out.println("Setting bit: " + set_result);

        // Clearing a bit
        int clear_result = clearBit(num, pos);
        System.out.println("Clearing bit: " + clear_result);

        // Toggling a bit
        int toggle_result = toggleBit(num, pos);
        System.out.println("Toggling bit: " + toggle_result);

        // Checking a bit
        boolean is_set = checkBit(num, pos);
        System.out.println("Bit is set: " + is_set);

        // Counting set bits
        int count_bits = countSetBits(num);
        System.out.println("Number of set bits: " + count_bits);
    }

    public static int setBit(int num, int pos) {
        return num | (1 << pos);
    }

    public static int clearBit(int num, int pos) {
        return num & ~(1 << pos);
    }

    public static int toggleBit(int num, int pos) {
        return num ^ (1 << pos);
    }

    public static boolean checkBit(int num, int pos) {
        return (num & (1 << pos)) != 0;
    }

    public static int countSetBits(int num) {
        int count = 0;
        while (num != 0) {
            num &= (num - 1);
            count++;
        }
        return count;
    }
}

Conclusion

Bit manipulation is a crucial technique that can optimize performance and memory usage in your programs, especially in low-level programming or systems where efficiency matters. By mastering these techniques, you can write more efficient and elegant code.