位运算算法题
- 缺失的数字
public int missingNumber(int[] nums) {
int ret = 0;
for (int x : nums)
ret ^= x;
for (int i = 0; i <= nums.length; i++)
ret ^= i;
return ret;
}
- 两整数之和
public int getSum(int a, int b) {
while (b != 0) {
int x = a ^ b; // 先算出⽆进位相加的结果
int carry = (a & b) << 1; // 计算进位
a = x;
b = carry;
}
return a;
}
- 只出现一次的数字2
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
输入：nums = [2,2,3,2]
输出：3
public int singleNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < 32; i++) // 依次修改 ret 中的每⼀个⽐特位
{
int sum = 0;
for (int x : nums) // 统计 nums 中所有的数的第 i 位的和
if (((x >> i) & 1) == 1)
sum++;
if (sum%3 == 1)
ret |= 1 << i;
}
return ret;
}
- 消失的两个数字
public int[] missingTwo(int[] nums) {
// 1. 先把所有的数异或在⼀起
int tmp = 0;
for (int x : nums)
tmp ^= x;
for (int i = 1; i <= nums.length + 2; i++)
tmp ^= i;
// 2. 找出 a，b 两个数⽐特位不同的那⼀位
int diff = 0;
for(;diff<32;diff++){
if (((tmp >> diff) & 1) == 1){
break;
}
}
// 3. 将所有的数按照 diff 位不同，分两类异或
int[] ret = new int[2];
for (int x : nums)
if (((x >> diff) & 1) == 1)
ret[1] ^= x;
else
ret[0] ^= x;
for (int i = 1; i <= nums.length + 2; i++)
if (((i >> diff) & 1) == 1)
ret[1] ^= i;
else
ret[0] ^= i;
return ret;
}