Skip to main content

Bit Manipulation

Premium

Bit manipulation involves directly working with the binary representations of integers. It allows for efficient operations, especially in scenarios requiring speed and optimization, as these operations are often faster than their arithmetic counterparts.

When to use it

You can identify problems that can be solved with bit manipulation if they meet one or more of these conditions:

  1. You need to work with individual bits of numbers.
  2. The problem involves binary operations, such as AND, OR, XOR, NOT, or bit shifts.
  3. You’re trying to optimize space or time complexity for problems involving integers.

Why use it

Bit manipulation can reduce time complexity and improve performance by allowing low-level operations on bits. This is particularly useful for tasks such as toggling bits, counting bits, or checking specific bit positions, which can be done in constant time (O(1)O(1)).

How it works

Bit manipulation typically involves using operators on binary representations. Common operators include:

  • AND (&): Compares each bit and returns 1 if both bits are 1.
  • OR (|): Compares each bit and returns 1 if at least one bit is 1.
  • XOR (^): Compares each bit and returns 1 if bits are different.
  • NOT (~): Inverts all the bits.
  • Left Shift (<<): Shifts bits to the left, effectively multiplying the number by 2.
  • Right Shift (>>): Shifts bits to the right, effectively dividing the number by 2.

Bitwise operations are widely supported in languages like C, C++, Java, Python, JavaScript, Go, C#, Rust, Swift, Kotlin, and PHP.

Watch out for overflow and truncation: In languages like JavaScript and C, bitwise operations are often limited to 32-bit or 64-bit integers, which can cause unexpected results. For example, shifting 1 left by 33 bits in JavaScript:

JavaScript
let n = 1 << 33;
console.log(n);  // Output: 2 (due to 32-bit truncation)

Any shift count larger than 31 is wrapped around for a 32-bit integer, leading to potential unexpected results like truncation or overflow.

Example 1: Checking if a number is even or odd

You can use bit manipulation to check if a number is even or odd by examining its least significant bit (LSB):

Python
def is_even(num):
    return (num & 1) == 0  # Check if LSB is 0 (even)

Check Odd or Even

Example 2: Counting the number of set bits

To count the number of 1s (set bits) in the binary representation of a number:

Python
def count_set_bits(n):
    count = 0
    while n:
        count += n & 1  # Increment count if LSB is 1
        n >>= 1         # Right shift to check the next bit
    return count

Count Number of Set Bits

You can optimize set bit counting using Brian Kernighan’s Algorithm, which runs in O(k) time, where k is the number of set bits. The idea is to repeatedly turn off the rightmost 1 in the binary representation of a number with n & (n - 1) until n becomes zero. Each operation removes one set bit, making it more efficient than checking every bit.

Python
def count_set_bits(n):
  count = 0
  while n:
      n &= (n - 1)  # Turn off the rightmost set bit
      count += 1
  return count

Examples

  1. Power of Two
    • Problem: Determine if a number is a power of two.
    • Approach: Use n & (n - 1) == 0 to check if only one bit is set in its binary representation.
  2. Finding the single number
    • Problem: In an array where every element appears twice except for one, find that single number.
    • Approach: Use the XOR operator since x ^ x = 0 for any integer x, which allows you to isolate the unique number.
  3. Swap two numbers without a temporary variable
    • Problem: Swap two integers without using additional space.
    • Approach: Use XOR: a = a ^ b; b = a ^ b; a = a ^ b.
  4. Reverse bits
    • Problem: Reverse the bits of a given 32-bit unsigned integer.
    • Approach: Use a loop to shift bits and build the reversed integer incrementally.
Next Lesson