Mastering Bit Manipulation

Problem: Check if a number is a power of 4

Problem: Given a 32-bit signed integer, write a function to determine if it is a power of four.

Approach 1 (Mathematical Property): A number n is a power of 4 if it meets three conditions:

1. It must be positive (n > 0).
2. It must be a power of two. We can check this with (n & (n - 1)) == 0. This works because a power of two has only one bit set (e.g., 8 is 1000), and subtracting one flips all bits to the right of it (e.g., 7 is 0111). ANDing them gives zero.
3. The single set bit must be in an "odd" position (0th, 2nd, 4th, etc. from the right). An interesting property of powers of 4 is that (n-1) is always divisible by 3. For example, 4-1=3, 16-1=15, 64-1=63.

class PowerOfFourSolution {
    public boolean isPowerOfFour(int n) {
        // Condition 1: Must be positive
        // Condition 2: Must be a power of two
        // Condition 3: (n-1) must be divisible by 3
        return n > 0 && (n & (n - 1)) == 0 && (n - 1) % 3 == 0;
    }

    public static void main(String[] args) {
        PowerOfFourSolution solution = new PowerOfFourSolution();
        System.out.println("Is 16 a power of four? " + solution.isPowerOfFour(16)); // true
        System.out.println("Is 8 a power of four? " + solution.isPowerOfFour(8));   // false
        System.out.println("Is 1 a power of four? " + solution.isPowerOfFour(1));   // true
    }
}
                

Approach 2 (Bitmask)

This approach also first verifies that the number is a power of two, which ensures only one bit is set. Then, it uses a bitmask to check if that single bit is in one of the positions that a power of four can occupy (0, 2, 4, 6, ...).

1. Check if n is a power of two: n > 0 && (n & (n-1)) == 0.
2. Create a mask that has 1s only at the even bit positions. For a 32-bit integer, this mask is 01010101010101010101010101010101 in binary, which is 0x55555555 in hexadecimal. (Because 0101 is 5 in hex).
3. Use the AND operator (&) between the number n and the mask. If the result is not zero, it means the single set bit in n coincided with a set bit in the mask, proving it's at an even position.

class PowerOfFourSolutionAlt {
    public boolean isPowerOfFour(int n) {
        // First, check if it's a power of two (only one bit is set).
        if (n <= 0 || (n & (n - 1)) != 0) {
            return false;
        }
        
        // Now, check if the single set bit is at an even position.
        // The mask 0x55555555 has 1s at all even positions (0, 2, 4,...).
        // For a power of 4, its single bit MUST be at an even position.
        // ANDing n with the mask will be non-zero if the bit is at an even position.
        return (n & 0x55555555) != 0;
    }

    public static void main(String[] args) {
        PowerOfFourSolutionAlt solution = new PowerOfFourSolutionAlt();
        System.out.println("Is 16 a power of four? " + solution.isPowerOfFour(16)); // true
        System.out.println("Is 8 a power of four? " + solution.isPowerOfFour(8));   // false
        System.out.println("Is 1 a power of four? " + solution.isPowerOfFour(1));   // true
    }
}
                

Application: Generating All Subsets (LeetCode 78)

Problem: Given an array of unique elements, return all possible subsets (the power set).

Approach: An array of size n has 2^n subsets. We can loop from 0 to 2^n - 1. Each number i in this range is a bitmask that represents one unique subset. This is a highly efficient and standard bit manipulation technique for this problem.

import java.util.ArrayList;
import java.util.List;

class SubsetsSolution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        int numSubsets = 1 << n; // 2^n
        List<List<Integer>> powerSet = new ArrayList<>();

        // Loop from 0 to 2^n - 1
        for (int i = 0; i < numSubsets; i++) {
            List<Integer> currentSubset = new ArrayList<>();
            // Check each bit of the mask 'i'
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    currentSubset.add(nums[j]);
                }
            }
            powerSet.add(currentSubset);
        }
        return powerSet;
    }

    public static void main(String[] args) {
        SubsetsSolution solution = new SubsetsSolution();
        int[] arr = {1, 2, 3};
        List<List<Integer>> result = solution.subsets(arr);

        System.out.println("All subsets of {1, 2, 3}:");
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}