What are key bit-manipulation tricks, such as checking powers of two, counting set bits, and finding the unique element with XOR?

Short answer

Bitwise operations run in a single CPU cycle. Check for powers of two with (n & (n - 1)) == 0, and find a single unique element by XOR-ing every number.

Explanation

Useful XOR properties are A ^ A = 0 and A ^ 0 = A, and XOR is commutative and associative. If an array contains every number twice except one, cumulative XOR cancels all duplicates, leaving the unique number in O(N) time and O(1) space. The trick n & (n - 1) removes the rightmost set bit and is used in Brian Kernighan's algorithm to count set bits in time proportional to the number of ones.

Code example

// Check whether the number is a power of 2 (Power of Two):
const isPowerOfTwo = (n > 0) && ((n & (n - 1)) === 0);

// Find the single unique element:
const singleNumber = (nums: number[]) => nums.reduce((acc, num) => acc ^ num, 0);

Common mistakes

• Forgetting parentheses in bitwise operations; comparison operators such as == have higher precedence than & in most programming languages.

Follow-up questions

• How does binary search work, and what mathematical trick avoids integer overflow?

Sources

• Bitwise operation - Wikipedia