XOR and Bit Tricks
Common XOR/bit manipulation patterns for interviews
#resource / algorithm
#type / concept
#status / growing
#algo / bitwise
[!info] related notes 算法面试题型 MOC
XOR and Bit Tricks
XOR Basics
- XOR is addition without carry.
- Commutative/associative.
x ^ x = 0,x ^ 0 = x.- If total XOR is
Xand a subset XOR isY, then the rest XOR isX ^ Y.
Patterns
Swap Two Numbers (same variable type)
a = a ^ b
b = a ^ b
a = a ^ bMissing Number (0..n)
int eorAll = 0, eorHas = 0;
for (int i = 0; i < nums.length; i++) {
eorAll ^= i;
eorHas ^= nums[i];
}
eorAll ^= nums.length;
return eorAll ^ eorHas;One Number Appears Odd Times, Others Even
- XOR all numbers.
Two Numbers Appear Odd Times, Others Even
- Let
eor = a ^ b. - Pick a distinguishing bit:
rightOne = eor & -eor(rightmost set bit). - Partition numbers by that bit and XOR within each bucket.
One Number Appears k Times (k < m), Others Appear m Times
- For each bit position
i(0..31), count how many numbers have bitiset. count[i] % mreconstructs the target number.
Bit Tricks
Rightmost Set Bit
n & -norn & (~n + 1)
Power of Two
n > 0 && (n & -n) == n
Power of Three (int range)
- In 32-bit signed int, the largest power of 3 is
3^19 = 1162261467. n > 0 && 1162261467 % n == 0
Smallest Power of Two >= n
static int near2Power(int n) {
if (n <= 1) return 1;
n--;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return n + 1;
}Range Bitwise AND (LeetCode 201)
static int rangeBitwiseAnd(int left, int right) {
while (left < right) {
right -= right & -right;
}
return right;
}Reverse Bits (32-bit)
static int reverseBits(int n) {
n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
return (n >>> 16) | (n << 16);
}Popcount / Hamming Distance
static int popcount(int n) {
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 1) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 1) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >>> 1) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >>> 1) & 0x0000ffff);
return n;
}
static int hammingDistance(int x, int y) {
return popcount(x ^ y);
}