Bit Manipulation

Bit manipulation involves directly manipulating bits (binary digits) to perform operations efficiently. It is a powerful technique used in competitive programming and Leetcode problems to optimize solutions.

Table of Contents

1. Bit Manipulation Basics
2. Common Bit Operations
3. Common Bit Manipulation Patterns
4. Time and Space Complexity
5. Related Leetcode Questions

Bit Manipulation Basics

• Definition: Bit manipulation involves performing operations directly on binary representations of numbers.
• Key Concepts:
  • Bitwise AND (&): Sets each bit to 1 if both bits are 1.
  • Bitwise OR (|): Sets each bit to 1 if at least one of the bits is 1.
  • Bitwise XOR (^): Sets each bit to 1 if only one of the bits is 1.
  • Bitwise NOT (~): Flips all the bits.
  • Left Shift (<<): Shifts bits to the left, filling with 0s.
  • Right Shift (>>): Shifts bits to the right, filling with the sign bit (arithmetic shift).
  • Unsigned Right Shift (>>>): Shifts bits to the right, filling with 0s.

Common Bit Operations

1. Check if a Number is Even or Odd

• Example:

  public boolean isEven(int n) {
      return (n & 1) == 0;
  }

• Time Complexity: O(1)
• Space Complexity: O(1)

2. Count the Number of Set Bits (1s)

• Example:

  public int countSetBits(int n) {
      int count = 0;
      while (n > 0) {
          count += n & 1;
          n >>= 1;
      }
      return count;
  }

• Time Complexity: O(log n)
• Space Complexity: O(1)

3. Toggle the k-th Bit

• Example:

  public int toggleKthBit(int n, int k) {
      return n ^ (1 << k);
  }

• Time Complexity: O(1)
• Space Complexity: O(1)

4. Check if the k-th Bit is Set

• Example:

  public boolean isKthBitSet(int n, int k) {
      return (n & (1 << k)) != 0;
  }

• Time Complexity: O(1)
• Space Complexity: O(1)

5. Swap Two Numbers Without a Temporary Variable

• Example:

  public void swap(int a, int b) {
      a = a ^ b;
      b = a ^ b;
      a = a ^ b;
  }

• Time Complexity: O(1)
• Space Complexity: O(1)

Common Bit Manipulation Patterns

1. Single Number

• Problem: Find the single number in an array where every other number appears twice.
• Example:

  public int singleNumber(int[] nums) {
      int result = 0;
      for (int num : nums) {
          result ^= num;
      }
      return result;
  }

• Time Complexity: O(n)
• Space Complexity: O(1)

2. Power of Two

• Problem: Check if a number is a power of two.
• Example:

  public boolean isPowerOfTwo(int n) {
      return n > 0 && (n & (n - 1)) == 0;
  }

• Time Complexity: O(1)
• Space Complexity: O(1)

3. Count Total Set Bits in All Numbers from 1 to n

• Problem: Count the total number of set bits in all numbers from 1 to n.
• Example:

  public int countTotalSetBits(int n) {
      int count = 0;
      for (int i = 1; i <= n; i++) {
          count += countSetBits(i);
      }
      return count;
  }

• Time Complexity: O(n log n)
• Space Complexity: O(1)

4. Reverse Bits

• Problem: Reverse the bits of a given 32-bit unsigned integer.
• Example:

  public int reverseBits(int n) {
      int result = 0;
      for (int i = 0; i < 32; i++) {
          result <<= 1;
          result |= (n & 1);
          n >>= 1;
      }
      return result;
  }

• Time Complexity: O(1) (since it’s always 32 bits)
• Space Complexity: O(1)

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Check if a Number is Even or Odd	O(1)	O(1)
Count the Number of Set Bits	O(log n)	O(1)
Toggle the k-th Bit	O(1)	O(1)
Check if the k-th Bit is Set	O(1)	O(1)
Swap Two Numbers	O(1)	O(1)
Single Number	O(n)	O(1)
Power of Two	O(1)	O(1)
Count Total Set Bits	O(n log n)	O(1)
Reverse Bits	O(1)	O(1)

Related Leetcode Questions

Easy

1. Single Number
2. Power of Two
3. Number of 1 Bits

Medium

1. Reverse Bits
2. Single Number II
3. Divide Two Integers

Hard

1. Maximum XOR of Two Numbers in an Array
2. Count of Range Sum
3. Bitwise AND of Numbers Range