Common Algorithm Tricks: Bit Manipulation, Two‑Pointer Techniques, and XOR Applications

This article supplements previous posts on algorithm tricks by presenting common interview problems and showing how bit‑manipulation, two‑pointer, and XOR techniques can simplify their solutions.

1. Using n & (n - 1) to clear the lowest set bit

Applying n = n & (n - 1) removes the rightmost 1 in the binary representation of n . This operation is useful in several classic problems.

(1) Determine whether an integer n is a power of two

If n is a power of two, its binary form contains exactly one ‘1’. The following O(1) method checks this:

boolean judge(int n) {
    return n & (n - 1) == 0;
}

(2) Count the number of 1 bits in n

Repeatedly apply n = n & (n - 1) and count the iterations until n becomes zero:

public int numberOfOnes(int n) {
    int count = 0;
    while (n != 0) {
        count++;
        n = n & (n - 1);
    }
    return count;
}

(3) Find how many bits differ between integers n and m

Compute t = n ^ m and then count the 1 bits in t using the method above.

2. Double‑pointer applications

Double pointers are especially handy for linked‑list problems and sorted‑array problems.

(1) Linked‑list examples

Detect a cycle by moving a slow pointer one step and a fast pointer two steps.

Find the middle node by advancing fast pointer twice as fast as the slow pointer.

Locate the k‑th node from the end by first advancing one pointer k steps, then moving both pointers together until the leading pointer reaches the end.

(2) Sorted array two‑sum using double pointers

Given a sorted array and a target sum, move pointers from both ends toward the center:

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    int start = 0;
    int end = nums.length - 1;
    while (end > start) {
        if (nums[start] + nums[end] > target) {
            end--;
        } else if (nums[start] + nums[end] < target) {
            start++;
        } else {
            res[0] = start;
            res[1] = end;
            return res;
        }
    }
    return res;
}

3. Using the property a ^ b ^ b = a

Because a number XORed with itself yields 0 and any number XORed with 0 yields the number itself, XOR can be used to find the unique element in an array where every other element appears twice.

int findSingle(int[] arr) {
    int tmp = arr[0];
    for (int i = 1; i < arr.length; i++) {
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

Summary

The presented tricks—bit manipulation with n&(n‑1), double‑pointer strategies for linked lists and arrays, and XOR properties—provide concise, O(1) or O(n) solutions that are easy to understand and implement for common interview questions.