Skip to content

Latest commit

 

History

History
1218 lines (928 loc) · 34.3 KB

23. Bit-Manipulation.md

File metadata and controls

1218 lines (928 loc) · 34.3 KB

🏠 Home
🛠️ DSA Home

Bit-Manipulation

Index

What is Bit Manipulation?

Bit manipulation refers to the act of algorithmically altering or operating on individual bits of a binary number. Since computers internally represent all data in binary, performing operations at the bit level can be highly efficient, both in terms of speed and memory. Bit manipulation is often used in low-level programming tasks, such as:

  • Optimizing performance by using fewer operations.
  • Efficiently managing resources (memory and storage).
  • Working with data formats, encodings, and protocols that require precise control over individual bits.

Bit manipulation is common in fields like cryptography, network programming, game development, and systems programming.

⬆️ Back to TOP ⬆️

Common Use Cases for Bit Manipulation

  • Checking if a number is odd or even (using n & 1).
  • Toggling a bit (changing a 1 to 0 or vice versa).
  • Setting or clearing specific bits.
  • Checking or flipping flags in a program.

⬆️ Back to TOP ⬆️

Bit-wise Operators in Java, Python, and C++

Operator Symbol Meaning Description
& AND Performs a bit-wise AND. Each bit in the result is 1 only if the corresponding bits of both operands are 1. Otherwise, it's 0.
` ` OR
^ XOR Performs a bit-wise XOR (exclusive OR). Each bit in the result is 1 if the corresponding bits of the operands are different, i.e., one is 1 and the other is 0.
~ NOT Performs a bit-wise NOT (complement). Flips all the bits in the operand, turning 1s to 0s and 0s to 1s.
<< Left Shift Shifts all bits in the left operand to the left by the number of positions specified by the right operand. New bits on the right are filled with 0.
>> Right Shift Shifts all bits in the left operand to the right by the number of positions specified by the right operand. In Java and C++, it performs an Arithmetic Shift, preserving the sign bit (for signed numbers).
>>> Unsigned Right Shift (Java only) Shifts all bits to the right. New bits on the left are filled with 0. Unlike >>, it does not preserve the sign bit. This operator exists only in Java. Python and C++ do not differentiate between signed and unsigned right shifts.

⬆️ Back to TOP ⬆️

Truth Table for Bit-wise Operators

1. AND (&)

A B A & B
0 0 0
0 1 0
1 0 0
1 1 1

⬆️ Back to TOP ⬆️

2. OR (|)

A B A | B
0 0 0
0 1 1
1 0 1
1 1 1

⬆️ Back to TOP ⬆️

3. XOR (^)

A B A ^ B
0 0 0
0 1 1
1 0 1
1 1 0

⬆️ Back to TOP ⬆️

4. NOT (~)

A ~A
0 1
1 0

⬆️ Back to TOP ⬆️

5. Left Shift (<<)

A B (shift by) A << B
0010 1 0100
0010 2 1000

⬆️ Back to TOP ⬆️

6. Right Shift (>>)

A B (shift by) A >> B
1000 1 0100
1000 2 0010

⬆️ Back to TOP ⬆️

7. Unsigned Right Shift (>>>) (Java only)

A B (shift by) A >>> B
11111111 1 01111111
10000000 1 01000000

⬆️ Back to TOP ⬆️

Detailed Explanation of Operators

  1. AND (&):

    • Operation: a & b
    • Example:
      • 5 & 3:
      • Binary: 101 & 011 = 001
      • Result: 1
    • Usage: Commonly used for bit-masking.

  2. OR (|):

    • Operation: a | b
    • Example:
      • 5 | 3:
      • Binary: 101 | 011 = 111
      • Result: 7
    • Usage: Often used to set specific bits.

  3. XOR (^):

    • Operation: a ^ b
    • Example:
      • 5 ^ 3:
      • Binary: 101 ^ 011 = 110
      • Result: 6
    • Usage: Used to toggle bits or find differences between two values.

  4. NOT (~):

    • Operation: ~a
    • Example:
      • ~5:
      • Binary: ~00000101 = 11111010 (for an 8-bit number)
      • Result: -6 (in 2's complement representation)
    • Usage: Used to invert bits.

  5. Left Shift (<<):

    • Operation: a << b
    • Example:
      • 5 << 1:
      • Binary: 00000101 << 1 = 00001010
      • Result: 10
    • Usage: Multiplies the number by 2^b.

  6. Right Shift (>>):

    • Operation: a >> b
    • Example:
      • 5 >> 1:
      • Binary: 00000101 >> 1 = 00000010
      • Result: 2
    • Usage: Divides the number by 2^b (preserving sign for signed numbers).

  7. Unsigned Right Shift (>>>) (Java Only):

    • Operation: a >>> b
    • Example:
      • -5 >>> 1:
      • Binary: 11111111...11111011 >>> 1 = 01111111...11111101
      • Result: A large positive number.
    • Usage: Ensures no sign extension when shifting right for unsigned operations.

💡NOTE💡

  • In Java, all integer types (int, long, etc.) are signed by default, but >>> provides a way to perform unsigned shifts.
  • In C++, right shifts of signed integers (>>) perform arithmetic shifts, preserving the sign.
  • In Python, there is no unsigned right shift, but Python integers are of arbitrary precision, so operations behave differently from fixed-width integer types in C++ or Java.

⬆️ Back to TOP ⬆️

Number System Conversion

Converting Binary, Deciaml, Octal and Hexadecimal amon each other.

Code without using inbuilt method

Decimal to Other Bases:

  • Binary: Continuously divide the number by 2, prepending the remainder (0 or 1) to the binary string until the number becomes zero.
  • Octal: Similar to binary, but divide by 8 and prepend the remainders (0 to 7).
  • Hexadecimal: Divide by 16, prepending the appropriate character from the hexadecimal character set (0-9, A-F).

Other Bases to Decimal:

  • Binary to Decimal: Iterate through each bit, multiplying the current decimal value by 2 and adding the value of the current bit (0 or 1).
  • Octal to Decimal: Multiply the current decimal value by 8 and add the value of the current octal digit (0 to 7).
  • Hexadecimal to Decimal: For each character, convert it to its decimal equivalent (0-9 or 10-15 for A-F) and accumulate the total by multiplying the current value by 16.

⬆️ Back to TOP ⬆️

In Java

import java.util.Scanner;

public class NumberSystemConversions {

    // Convert decimal to binary
    public static String decimalToBinary(int n) {
        StringBuilder binary = new StringBuilder();
        do {
            binary.insert(0, n % 2);
            n /= 2;
        } while (n > 0);
        return binary.toString();
    }

    // Convert decimal to octal
    public static String decimalToOctal(int n) {
        StringBuilder octal = new StringBuilder();
        do {
            octal.insert(0, n % 8);
            n /= 8;
        } while (n > 0);
        return octal.toString();
    }

    // Convert decimal to hexadecimal
    public static String decimalToHexadecimal(int n) {
        StringBuilder hexadecimal = new StringBuilder();
        char[] hexChars = "0123456789ABCDEF".toCharArray();
        do {
            int remainder = n % 16;
            hexadecimal.insert(0, hexChars[remainder]);
            n /= 16;
        } while (n > 0);
        return hexadecimal.toString();
    }

    // Convert binary to decimal
    public static int binaryToDecimal(String binary) {
        int decimal = 0;
        for (int i = 0; i < binary.length(); i++) {
            decimal = decimal * 2 + (binary.charAt(i) - '0');
        }
        return decimal;
    }

    // Convert octal to decimal
    public static int octalToDecimal(String octal) {
        int decimal = 0;
        for (int i = 0; i < octal.length(); i++) {
            decimal = decimal * 8 + (octal.charAt(i) - '0');
        }
        return decimal;
    }

    // Convert hexadecimal to decimal
    public static int hexadecimalToDecimal(String hex) {
        int decimal = 0;
        for (int i = 0; i < hex.length(); i++) {
            char ch = hex.charAt(i);
            int value;
            if (ch >= '0' && ch <= '9') {
                value = ch - '0';
            } else {
                value = ch - 'A' + 10; // For 'A' to 'F'
            }
            decimal = decimal * 16 + value;
        }
        return decimal;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter a decimal number:");
        int decimal = scanner.nextInt();
        System.out.println("Binary: " + decimalToBinary(decimal));
        System.out.println("Octal: " + decimalToOctal(decimal));
        System.out.println("Hexadecimal: " + decimalToHexadecimal(decimal));

        System.out.println("\nEnter a binary number:");
        String binary = scanner.next();
        System.out.println("Decimal: " + binaryToDecimal(binary));

        System.out.println("\nEnter an octal number:");
        String octal = scanner.next();
        System.out.println("Decimal: " + octalToDecimal(octal));

        System.out.println("\nEnter a hexadecimal number:");
        String hex = scanner.next();
        System.out.println("Decimal: " + hexadecimalToDecimal(hex));

        scanner.close();
    }
}

⬆️ Back to TOP ⬆️

In Python

def decimal_to_binary(n):
    binary = ''
    while n > 0:
        binary = str(n % 2) + binary
        n //= 2
    return binary

def decimal_to_octal(n):
    octal = ''
    while n > 0:
        octal = str(n % 8) + octal
        n //= 8
    return octal

def decimal_to_hexadecimal(n):
    hex_chars = "0123456789ABCDEF"
    hexadecimal = ''
    while n > 0:
        remainder = n % 16
        hexadecimal = hex_chars[remainder] + hexadecimal
        n //= 16
    return hexadecimal

def binary_to_decimal(binary):
    decimal = 0
    for i in range(len(binary)):
        decimal = decimal * 2 + (ord(binary[i]) - ord('0'))
    return decimal

def octal_to_decimal(octal):
    decimal = 0
    for i in range(len(octal)):
        decimal = decimal * 8 + (ord(octal[i]) - ord('0'))
    return decimal

def hexadecimal_to_decimal(hexadecimal):
    decimal = 0
    for i in range(len(hexadecimal)):
        ch = hexadecimal[i]
        if '0' <= ch <= '9':
            value = ord(ch) - ord('0')
        else:
            value = ord(ch) - ord('A') + 10  # For 'A' to 'F'
        decimal = decimal * 16 + value
    return decimal

# Example usage
if __name__ == "__main__":
    decimal = int(input("Enter a decimal number: "))
    print("Binary:", decimal_to_binary(decimal))
    print("Octal:", decimal_to_octal(decimal))
    print("Hexadecimal:", decimal_to_hexadecimal(decimal))

    binary = input("\nEnter a binary number: ")
    print("Decimal:", binary_to_decimal(binary))

    octal = input("\nEnter an octal number: ")
    print("Decimal:", octal_to_decimal(octal))

    hexadecimal = input("\nEnter a hexadecimal number: ")
    print("Decimal:", hexadecimal_to_decimal(hexadecimal))

⬆️ Back to TOP ⬆️

In C++

#include <iostream>
#include <string>
using namespace std;

// Convert decimal to binary
string decimalToBinary(int n) {
    string binary = "";
    do {
        binary = to_string(n % 2) + binary;
        n /= 2;
    } while (n > 0);
    return binary;
}

// Convert decimal to octal
string decimalToOctal(int n) {
    string octal = "";
    do {
        octal = to_string(n % 8) + octal;
        n /= 8;
    } while (n > 0);
    return octal;
}

// Convert decimal to hexadecimal
string decimalToHexadecimal(int n) {
    char hexChars[] = "0123456789ABCDEF";
    string hexadecimal = "";
    do {
        int remainder = n % 16;
        hexadecimal = hexChars[remainder] + hexadecimal;
        n /= 16;
    } while (n > 0);
    return hexadecimal;
}

// Convert binary to decimal
int binaryToDecimal(string binary) {
    int decimal = 0;
    for (int i = 0; i < binary.length(); i++) {
        decimal = decimal * 2 + (binary[i] - '0');
    }
    return decimal;
}

// Convert octal to decimal
int octalToDecimal(string octal) {
    int decimal = 0;
    for (int i = 0; i < octal.length(); i++) {
        decimal = decimal * 8 + (octal[i] - '0');
    }
    return decimal;
}

// Convert hexadecimal to decimal
int hexadecimalToDecimal(string hex) {
    int decimal = 0;
    for (int i = 0; i < hex.length(); i++) {
        char ch = hex[i];
        int value;
        if (ch >= '0' && ch <= '9') {
            value = ch - '0';
        } else {
            value = ch - 'A' + 10; // For 'A' to 'F'
        }
        decimal = decimal * 16 + value;
    }
    return decimal;
}

int main() {
    int decimal;
    cout << "Enter a decimal number: ";
    cin >> decimal;
    cout << "Binary: " << decimalToBinary(decimal) << endl;
    cout << "Octal: " << decimalToOctal(decimal) << endl;
    cout << "Hexadecimal: " << decimalToHexadecimal(decimal) << endl;

    string binary;
    cout << "\nEnter a binary number: ";
    cin >> binary;
    cout << "Decimal: " << binaryToDecimal(binary) << endl;

    string octal;
    cout << "\nEnter an octal number: ";
    cin >> octal;
    cout << "Decimal: " << octalToDecimal(octal) << endl;

    string hex;
    cout << "\nEnter a hexadecimal number: ";
    cin >> hex;
    cout << "Decimal: " << hexadecimalToDecimal(hex) << endl;

    return 0;
}

⬆️ Back to TOP ⬆️

Code with using inbuilt method

Decimal to Other Bases:

  • Binary: Use bin() in Python, Integer.toBinaryString() in Java, or std::bitset in C++ to convert decimal to binary.
  • Octal: Use oct() in Python, Integer.toOctalString() in Java, or std::oct in C++ to convert decimal to octal.
  • Hexadecimal: Use hex() in Python, Integer.toHexString() in Java, or std::hex in C++ to convert decimal to hexadecimal.

Other Bases to Decimal:

  • Binary to Decimal: Use int(binary, 2) in Python, Integer.parseInt(binary, 2) in Java, and stoi(binary, nullptr, 2) in C++ to convert binary to decimal.
  • Octal to Decimal: Use int(octal, 8) in Python, Integer.parseInt(octal, 8) in Java, and stoi(octal, nullptr, 8) in C++ to convert octal to decimal.
  • Hexadecimal to Decimal: Use int(hex, 16) in Python, Integer.parseInt(hex, 16) in Java, and stoi(hex, nullptr, 16) in C++ to convert hexadecimal to decimal.

⬆️ Back to TOP ⬆️

In Java

import java.util.Scanner;

public class NumberSystemConversions {

    // Convert decimal to binary
    public static String decimalToBinary(int n) {
        return Integer.toBinaryString(n);
    }

    // Convert decimal to octal
    public static String decimalToOctal(int n) {
        return Integer.toOctalString(n);
    }

    // Convert decimal to hexadecimal
    public static String decimalToHexadecimal(int n) {
        return Integer.toHexString(n);
    }

    // Convert binary to decimal
    public static int binaryToDecimal(String binary) {
        return Integer.parseInt(binary, 2);
    }

    // Convert octal to decimal
    public static int octalToDecimal(String octal) {
        return Integer.parseInt(octal, 8);
    }

    // Convert hexadecimal to decimal
    public static int hexadecimalToDecimal(String hex) {
        return Integer.parseInt(hex, 16);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter a decimal number:");
        int decimal = scanner.nextInt();
        System.out.println("Binary: " + decimalToBinary(decimal));
        System.out.println("Octal: " + decimalToOctal(decimal));
        System.out.println("Hexadecimal: " + decimalToHexadecimal(decimal));

        System.out.println("\nEnter a binary number:");
        String binary = scanner.next();
        System.out.println("Decimal: " + binaryToDecimal(binary));

        System.out.println("\nEnter an octal number:");
        String octal = scanner.next();
        System.out.println("Decimal: " + octalToDecimal(octal));

        System.out.println("\nEnter a hexadecimal number:");
        String hex = scanner.next();
        System.out.println("Decimal: " + hexadecimalToDecimal(hex));

        scanner.close();
    }
}

⬆️ Back to TOP ⬆️

In Python

def decimal_to_binary(n):
    return bin(n)[2:]

def decimal_to_octal(n):
    return oct(n)[2:]

def decimal_to_hexadecimal(n):
    return hex(n)[2:]

def binary_to_decimal(binary):
    return int(binary, 2)

def octal_to_decimal(octal):
    return int(octal, 8)

def hexadecimal_to_decimal(hexadecimal):
    return int(hexadecimal, 16)

# Example usage
if __name__ == "__main__":
    decimal = int(input("Enter a decimal number: "))
    print("Binary:", decimal_to_binary(decimal))
    print("Octal:", decimal_to_octal(decimal))
    print("Hexadecimal:", decimal_to_hexadecimal(decimal))

    binary = input("\nEnter a binary number: ")
    print("Decimal:", binary_to_decimal(binary))

    octal = input("\nEnter an octal number: ")
    print("Decimal:", octal_to_decimal(octal))

    hexadecimal = input("\nEnter a hexadecimal number: ")
    print("Decimal:", hexadecimal_to_decimal(hexadecimal))

⬆️ Back to TOP ⬆️

In C++

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
using namespace std;

// Convert decimal to binary
string decimalToBinary(int n) {
    stringstream ss;
    ss << std::bitset<32>(n); // Adjust the bitset size as needed
    return ss.str();
}

// Convert decimal to octal
string decimalToOctal(int n) {
    stringstream ss;
    ss << oct << n;
    return ss.str();
}

// Convert decimal to hexadecimal
string decimalToHexadecimal(int n) {
    stringstream ss;
    ss << hex << n;
    return ss.str();
}

// Convert binary to decimal
int binaryToDecimal(string binary) {
    return stoi(binary, nullptr, 2);
}

// Convert octal to decimal
int octalToDecimal(string octal) {
    return stoi(octal, nullptr, 8);
}

// Convert hexadecimal to decimal
int hexadecimalToDecimal(string hex) {
    return stoi(hex, nullptr, 16);
}

int main() {
    int decimal;
    cout << "Enter a decimal number: ";
    cin >> decimal;
    cout << "Binary: " << decimalToBinary(decimal) << endl;
    cout << "Octal: " << decimalToOctal(decimal) << endl;
    cout << "Hexadecimal: " << decimalToHexadecimal(decimal) << endl;

    string binary;
    cout << "\nEnter a binary number: ";
    cin >> binary;
    cout << "Decimal: " << binaryToDecimal(binary) << endl;

    string octal;
    cout << "\nEnter an octal number: ";
    cin >> octal;
    cout << "Decimal: " << octalToDecimal(octal) << endl;

    string hex;
    cout << "\nEnter a hexadecimal number: ";
    cin >> hex;
    cout << "Decimal: " << hexadecimalToDecimal(hex) << endl;

    return 0;
}

⬆️ Back to TOP ⬆️

Bit-Manipulation Operations

There are 4 bit operations:

  1. Get a bit
  2. Set a bit
  3. Clear a bit
  4. UUpdate a bit
  • Get Bit: Check if the ith bit is 0 or 1.
    • Logic: Shift the bits of the number n to the right by i positions. The least significant bit will be the ith bit, and we can isolate it by using a bitwise AND with 1.

💡NOTE💡

  • If bits are read from left to right, then use right shift operator.
  • If bits are read from right to left, then use left shift operator.

For this notes, i m considering the 2nd case.

  • Set Bit: Set the ith bit to 1.
    • Logic: Use bitwise OR between n and (1 << i) to ensure the ith bit is 1.
  • Clear Bit: Set the ith bit to 0.
    • Logic: Use bitwise AND between n and the negation of (1 << i) to ensure the ith bit is cleared (set to 0).
  • Update Bit: Update the ith bit to a specific value (0 or 1).
    • Logic:
      • First clear the ith bit, then set it to the desired value.
      • In other words, or in short, if the ith position bit is to be updated to 0, then use the Clear bit operation, and if the ith position bit is to be updated to 1, then use Set bit operation.

⬆️ Back to TOP ⬆️

In Java

public class BitManipulation {

    // Get the ith bit
    public static int getBit(int n, int i) {
        return (n << i) & 1;
    }

    // Set the ith bit
    public static int setBit(int n, int i) {
        return n | (1 << i);
    }

    // Clear the ith bit
    public static int clearBit(int n, int i) {
        return n & ~(1 << i);
    }

    // Update the ith bit to a specific value (0 or 1)
    public static int updateBit(int n, int i, int value) {
        // First clear the ith bit
        n = clearBit(n, i); 
        // Then set it to the new value
        return n | (value << i); 
    }

    public static void main(String[] args) {
        int n = 13; // Binary: 1101

        System.out.println("Get 2nd bit: " + getBit(n, 2));   
        // Output: 0
        System.out.println("Set 1st bit: " + setBit(n, 1));   
        // Output: 15 (Binary: 1111)
        System.out.println("Clear 3rd bit: " + clearBit(n, 3)); 
        // Output: 5 (Binary: 0101)
        System.out.println("Update 1st bit to 0: " + updateBit(n, 1, 0)); 
        // Output: 13 (Binary: 1101)
    }
}

⬆️ Back to TOP ⬆️

In Python

def get_bit(n, i):
    return (n >> i) & 1

def set_bit(n, i):
    return n | (1 << i)

def clear_bit(n, i):
    return n & ~(1 << i)

def update_bit(n, i, value):
    n = clear_bit(n, i)
    return n | (value << i)

# Example usage
n = 13  # Binary: 1101

print("Get 2nd bit:", get_bit(n, 2))  
# Output: 1
print("Set 1st bit:", set_bit(n, 1))  
# Output: 15 (Binary: 1111)
print("Clear 3rd bit:", clear_bit(n, 3))  
# Output: 5 (Binary: 0101)
print("Update 1st bit to 0:", update_bit(n, 1, 0))  
# Output: 13 (Binary: 1101)

⬆️ Back to TOP ⬆️

In C++

#include <iostream>
using namespace std;

// Get the ith bit
int getBit(int n, int i) {
    return (n >> i) & 1;
}

// Set the ith bit
int setBit(int n, int i) {
    return n | (1 << i);
}

// Clear the ith bit
int clearBit(int n, int i) {
    return n & ~(1 << i);
}

// Update the ith bit to a specific value (0 or 1)
int updateBit(int n, int i, int value) {
    // First clear the ith bit
    n = clearBit(n, i); 
    // Then set it to the new value
    return n | (value << i); 
}

int main() {
    int n = 13; // Binary: 1101

    cout << "Get 2nd bit: " << getBit(n, 2) << endl;
    // Output: 1
    cout << "Set 1st bit: " << setBit(n, 1) << endl;
    // Output: 15 (Binary: 1111)
    cout << "Clear 3rd bit: " << clearBit(n, 3) << endl;
    // Output: 5 (Binary: 0101)
    cout << "Update 1st bit to 0: " << updateBit(n, 1, 0) << endl;
    // Output: 13 (Binary: 1101)

    return 0;
}

⬆️ Back to TOP ⬆️

Questions on Bit-Manipulation

Basic

1. Check if a number is even or odd using bit manipulation.

  • Problem: Given an integer n, determine if it is even or odd using bit manipulation.
  • Solution: Use n & 1. If the result is 1, the number is odd; otherwise, it is even.
def is_odd(n):
    return n & 1 == 1

# Example
print(is_odd(4))  
# Output: False (even)
print(is_odd(7))
# Output: True (odd)

⬆️ Back to TOP ⬆️

2. Swap two numbers without using a temporary variable.

  • Problem: Given two integers a and b, swap them using bit manipulation.
  • Solution: Use XOR (^) to swap the values.
def swap(a, b):
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return a, b

# Example
print(swap(5, 3))  
# Output: (3, 5)

⬆️ Back to TOP ⬆️

3. Find the ith bit of a number.

  • Problem: Given a number n and index i, find the value of the ith bit (0-based from the right).
  • Solution: Use Set bit operations ie. (n << i) & 1 to extract the ith bit.
def get_ith_bit(n, i):
    return (n << i) & 1

# Example
print(get_ith_bit(5, 0))  
# Output: 1 (binary: 101)
print(get_ith_bit(5, 1))
# Output: 0

⬆️ Back to TOP ⬆️

4. Set the ith bit of a number

  • Problem: Given a number n and index i, set the ith bit to 1.
  • Solution: Use n | (1 << i) to set the ith bit.
def set_ith_bit(n, i):
    return n | (1 << i)

# Example
print(set_ith_bit(5, 1))  
# Output: 7 (binary: 101 -> 111)

⬆️ Back to TOP ⬆️

5. Clear the ith bit of a number

  • Problem: Given a number n and index i, clear the ith bit (set it to 0).
  • Solution: Use n & ~(1 << i) to clear the ith bit.
def clear_ith_bit(n, i):
    return n & ~(1 << i)

# Example
print(clear_ith_bit(7, 1))  
# Output: 5 (binary: 111 -> 101)

Intermediate

1. Count the number of set bits in an integer

  • Problem: Given an integer n, count the number of 1s in its binary representation.
  • Solution: Use n & (n - 1) to turn off the rightmost set bit.
def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

# Example
print(count_set_bits(7))  # Output: 3 (binary: 111)

⬆️ Back to TOP ⬆️

2. Reverse the bits of an integer

  • Problem: Given an integer n, reverse its bits.
  • Solution: Shift bits from the original number to a new number.
def reverse_bits(n, num_bits=32):
    result = 0
    for i in range(num_bits):
        result <<= 1
        result |= (n >> i) & 1
    return result

# Example
print(reverse_bits(5))  
# Output: (binary: 101 -> 10100000000000000000000000000000)

⬆️ Back to TOP ⬆️

3. Determine if a number is a power of 2

  • Problem: Given an integer n, check if it is a power of 2.
  • Solution: A number n is a power of 2 if n & (n - 1) == 0 and n > 0.
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

# Example
is_power_of_two(8)  
# Output: True

⬆️ Back to TOP ⬆️

4. Find the single number in an array where every other number appears twice

  • Problem: Given an array where every number appears twice except one, find the unique number.
  • Solution: XOR all the numbers together. The result will be the unique number.
def single_number(arr):
    result = 0
    for num in arr:
        result ^= num
    return result

# Example
print(single_number([2, 2, 1]))  
# Output: 1

⬆️ Back to TOP ⬆️

5. Swap even and odd bits in an integer

  • Problem: Swap even and odd bits in a 32-bit integer.
  • Solution: Use bit masks to isolate and shift even and odd bits.
def swap_even_odd_bits(n):
    # Mask for even bits
    even_bits = n & 0xAAAAAAAA  
    # Mask for odd bits
    odd_bits = n & 0x55555555   
    return (even_bits >> 1) | (odd_bits << 1)

# Example
print(swap_even_odd_bits(23))  
# Output: 43 (binary: 10111 -> 101011)

⬆️ Back to TOP ⬆️

Advanced

1. Find the two non-repeating numbers in an array where every other number repeats twice

  • Problem: Given an array where every number repeats twice except two, find the two unique numbers.
  • Solution: XOR all numbers to find the XOR of the two unique numbers. Use this to separate them into two groups.
def find_two_unique(arr):
    xor_all = 0
    for num in arr:
        xor_all ^= num

    rightmost_set_bit = xor_all & -xor_all
    num1, num2 = 0, 0
    for num in arr:
        if num & rightmost_set_bit:
            num1 ^= num
        else:
            num2 ^= num
    return num1, num2

# Example
find_two_unique([1, 2, 3, 2, 1, 4])  
# Output: (3, 4)

⬆️ Back to TOP ⬆️

2. Find the missing number in an array of size n containing numbers from 0 to n

  • Problem: Given an array of size n containing numbers from 0 to n with one number missing, find the missing number.
  • Solution: XOR all the indices and the numbers in the array to find the missing number.
def missing_number(arr):
    n = len(arr)
    result = n
    for i in range(n):
        result ^= i
        result ^= arr[i]
    return result

# Example
print(missing_number([0, 1, 3]))  
# Output: 2

⬆️ Back to TOP ⬆️

3. Find the smallest power of 2 greater than or equal to n

  • Problem: Given an integer n, find the smallest power of 2 greater than or equal to n.
  • Solution: Use bit shifting to find the smallest power of 2.
def smallest_power_of_two(n):
    n -= 1
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    return n + 1

# Example
print(smallest_power_of_two(17))
# Output: 32

⬆️ Back to TOP ⬆️

4. Find the number of bits required to convert a to b

  • Problem: Given two integers a and b, find the number of bits required to convert a to b.
  • Solution: XOR a and b, then count the number of set bits in the result.
def bits_to_convert(a, b):
    return bin(a ^ b).count('1')

# Example
bits_to_convert(29, 15)  
# Output: 2 (binary: 11101 -> 01111)

⬆️ Back to TOP ⬆️

5. Find the longest sequence of 1s you can create by flipping one 0

  • Problem: Given an integer, find the longest sequence of consecutive 1s that can be created by flipping one 0 to 1.
  • Solution: Use a sliding window technique with bit manipulation.
def longest_sequence_of_ones(n):
    prev_len, curr_len, max_len = 0, 0, 0
    while n:
        if n & 1:
            curr_len += 1
        else:
            prev_len = curr_len if n & 2 else 0
            curr_len = 0
        max_len = max(max_len, curr_len + prev_len + 1)
        n >>= 1
    return max_len

# Example
print(longest_sequence_of_ones(1775))
# Output: 8 (binary: 11011101111)

🏠 Home
🛠️ DSA Home