位运算：从底层到面试

// n & 1 == 0 → 偶数；n & 1 == 1 → 奇数
boolean isOdd = (n & 1) == 1;

int doubled = n << 1;    // n * 2
int halved  = n >> 1;    // n / 2（向下取整）
int times8  = n << 3;    // n * 8

int lowbit = n & (-n);   // 等价于 n & (~n + 1)

n = n & (n - 1);   // 清除最右边的 1

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

boolean isPowerOfTwo = n > 0 && (n & (n - 1)) == 0;

a ^= b;
b ^= a;
a ^= b;

public int singleNumber(int[] nums) {
    int xor = 0;
    for (int num : nums) xor ^= num;
    return xor;
}

public int singleNumber(int[] nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
        ones = (ones ^ num) & ~twos;
        twos = (twos ^ num) & ~ones;
    }
    return ones;
}

public int[] singleNumber(int[] nums) {
    int xorAll = 0;
    for (int num : nums) xorAll ^= num;
    // 取最低位的 1，将数组分成两组
    int diff = xorAll & (-xorAll);
    int a = 0, b = 0;
    for (int num : nums) {
        if ((num & diff) == 0) a ^= num;
        else b ^= num;
    }
    return new int[]{a, b};
}

public int missingNumber(int[] nums) {
    int xor = nums.length;
    for (int i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    return xor;
}

// 方法一：Brian Kernighan
public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) { n &= (n - 1); count++; }
    return count;
}

// 方法二：逐位检查
public int hammingWeight2(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += (n >> i) & 1;
    }
    return count;
}

int mask = 0;
mask |= (1 << i);       // 加入第 i 个元素
mask &= ~(1 << i);      // 移除第 i 个元素
boolean has = (mask & (1 << i)) != 0;  // 检查第 i 个
mask ^= (1 << i);       // 切换第 i 个元素