位运算：从基础到进阶

位运算是一种在计算机中非常高效的运算方式，它直接对整数的二进制位进行操作。在很多算法问题中，巧妙运用位运算可以大幅提升代码的执行效率。

今天我来分享一些经典的位运算问题，展示如何从基础到进阶运用位运算解决问题。

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解法一：异或运算（基础）

这是位运算最经典的应用。异或的性质：两个相同的数异或结果为0，0和任何数异或结果为那个数。

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

解法二：数学方法（非位运算）

虽然不符合主题，但提供了另一种思路：

public int singleNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int sum = 0;
    for (int num : nums) {
        if (!set.contains(num)) {
            sum += num;
            set.add(num);
        } else {
            sum -= num;
        }
    }
    return sum;
}

解法三：排序后查找（非位运算）

同样不符合主题，但展示不同解法：

public int singleNumber(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i += 2) {
        if (nums[i] != nums[i + 1]) {
            return nums[i];
        }
    }
    return nums[nums.length - 1];
}

只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

解法一：位统计（进阶）

我们统计每个二进制位上1出现的次数，如果某个位上1的次数不是3的倍数，那么说明只出现一次的数字在这个位上是1。

public int singleNumber(int[] nums) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        int sum = 0;
        for (int num : nums) {
            sum += (num >> i) & 1;
        }
        if (sum % 3 != 0) {
            result |= (1 << i);
        }
    }
    return result;
}

解法二：有限状态自动机（高级）

我们可以设计一个状态机，用两个变量来表示当前的状态，ones表示出现1次，twos表示出现2次。

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) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }
    return -1;
}

位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

解法一：循环检查（基础）

最直观的方法是循环32次，每次检查最低位是否为1。

public int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if (((n >> i) & 1) == 1) {
            count++;
        }
    }
    return count;
}

解法二：Brian Kernighan算法（优化）

这种算法利用了一个特性：n & (n-1) 可以消除n中最右边的一个1。

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

解法三：查表法（空间换时间）

我们可以预计算8位数的二进制中1的个数，然后将32位数分成4个8位数查表。

public int hammingWeight(int n) {
    int[] table = new int[256];
    for (int i = 0; i < 256; i++) {
        table[i] = table[i >> 1] + (i & 1);
    }

    return table[n & 0xFF] + table[(n >> 8) & 0xFF] + 
           table[(n >> 16) & 0xFF] + table[(n >> 24) & 0xFF];
}

2的幂

给定一个整数，编写一个函数来判断它是否是2的幂。

解法一：位运算特性（基础）

2的幂在二进制表示中只有一个1，且这个1不在符号位上。

public boolean isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    return (n & (n - 1)) == 0;
}

解法二：统计位1个数

public boolean isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }

    int count = 0;
    while (n != 0) {
        n = n & (n - 1);
        count++;
        if (count > 1) {
            return false;
        }
    }
    return true;
}

解法三：数学方法（非位运算）

public boolean isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }

    while (n % 2 == 0) {
        n /= 2;
    }
    return n == 1;
}

位运算技巧总结

通过以上例题，我想分享一些位运算的解题技巧：

异或特性：
- 任何数和自身异或结果为0
- 任何数和0异或结果为自身
- 异或满足交换律和结合律
与运算技巧：
- n & (n-1) 可以消除n中最右边的一个1
- n & -n 可以获取n中最右边的一个1
- 可以用来判断一个数是否为2的幂
移位操作：
- 左移相当于乘以2
- 右移相当于除以2
- 可以用来检查特定位是否为1
位统计：
- 可以统计每个二进制位上1的个数
- 适用于"其他数字出现k次，只有一个数字出现一次"的问题
位运算替代数学运算：
- n * 2 可以用 n << 1 替代
- n / 2 可以用 n >> 1 替代
- n % 2 可以用 n & 1 替代