Examples of Bit Manipulation

How to check if a number is power of 2 ?

• Naive way is to keep dividing it by $2$ if it is even and if we end up with $1$ it is power of $2$ otherwise it's not.

boolean isPowerOfTwo(int n) {
    if(n == 0)
        return false;
    else {
        while(n % 2 == 0) n /= 2;
        return (n == 1);
    }
}

Time complexity of the above code is $O(log_2n)$.

• Here is a clever trick to solve it in constant time $O(1)$.
  
  • Consider a number $n$ which is power of $2$ which means $n = 2 ^ j$ for some $j$
    It is obvious that $n$ will have only $j^{\text{th}}$ bit equal to $1$, all the remaining bits will be $0$
    
  • Now think about $(n - 1)$, it will be have $k^{\text{th}}$ bit equal to $1$ if $k < j$.
    
  • In simpler words $(n - 1)$ will have all the bits as 1 after $j^{\text{th}}$ bit.
  • Consider $n = 32$
    $32 = 00100000_2$
    $31 = 00011111_2$
    $32 \, \& \, 31 = 00000000_2$
    
  • This can be generalized to any $n$ which is power of $2$ i.e $n = 2 ^ j$
  • $\boxed{ n \text{ is a power of 2 iff : \, } n \, \& \, (n - 1) = 0 \, \text{and} \, n\,!= 0}$

boolean isPowerOfTwo(int n) {
    if(n == 0)
        return false;
    return (n & (n - 1)) == 0
}

How to check if certain bit at position is set in a number

We can use combination of Logical AND and Left shift operator <<

Notice that $2 ^ i$ can be written as $1 << i$ and if $i^{\text{th}}$ bit of $n$ is $0$ then $n * (1 << i) = 0$

Note: This is widely used in modern SDLC for feature toggle in deployments to check if certain feature is enabled or not

boolean checkIfIthBitIsSet(int n, int i) {
    return ((n & (1 << i)) != 0);
}

Generate all possible subsets of a set

We can use bitmasking to solve this problem.
Consider a set $\{ x, y, z \}$ of three elements. We can iterate over all possible binary masks of length $3$
We will be picking $i^{\text{th}}$ element from original set if current bit mask has $i^{\text{th}}$ bit set.

• $000_2 = \{\}$
• $001_2 = \{z\}$
• $010_2 = \{y\}$
• $011_2 = \{y,z\}$
• $100_2 = \{x\}$
• $101_2 = \{x,z\}$
• $110_2 = \{x,y\}$
• $111_2 = \{x,y,z\}$

// Function to generate all possible subsets using bit manipulation
public static List<List<Integer>> generateSubsets(int[] set) {
    List<List<Integer>> result = new ArrayList<>();
    int n = set.length;
    // There are 2^n subsets for a set of size n
    for (int i = 0; i < (1 << n); i++) {  // Loop through all 2^n possible subsets
        List<Integer> subset = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            // Check if the j-th bit of i is set (1)
            if ((i & (1 << j)) != 0) {
                subset.add(set[j]);
            }
        }
        result.add(subset);
    }
    return result;
}

Few more tricks with bit manipulation

• Return rightmost $1$ bit or $MSB$ in $n$
  $$n \, \& \, (n - 1)$$
• Set $i^{\text{th}}$ bit to $1$ in $n$
  $$n \mid (1 << i)$$
• Toggle $i^{\text{th}}$ bit in $n$
  $$n \oplus (1 << i)$$
• Count set bits in a integer $(Keringham \,Algorithm)$

// Number of iterations in this loop is equal to number of set bits
public static int countSetBits(int x) {
    int count = 0;
    while (x > 0) {
        count += 1;
        x &= (x - 1);
    }
    return count;
}

• Swapping two numbers without temporary variable

  $$a = a \oplus b \\ b = a \oplus b \\ a = a \oplus b$$

• Rotate bits by $k$ number of bit positions

  • Left Rotate $$(num << k) \,|\, (num >> (n - k))$$
  • Right Rotate $$(num >> k) \,|\, (num << (n - k))$$

• Unique element in the array : If all the integers appear twice except for one integer, we can XOR all the integers to get unique integer

Practical Applications

1. Efficient Storage:
   • Use bits to represent flags or states compactly (e.g., feature toggles, permissions).
2. Boolean Matrix Operations
   • Represent rows/columns as bitmasks for fast bitwise operations.
3. Dynamic Programming with BitMasking
   • Solve combinatorial problems efficiently, such as traveling salesman, subset-sum, etc.
4. Optimize Arithmetic Operations
   • Use shifts for multiplication/division by powers of two.
5. Hashing
   • Use XOR to mix bits effectively in hash functions