二进制运算
a=0^a=a^0
0=a^a
由上面两个推导出：a=a^b^b
a=a^b
b=a^b
a=a^b
a=n&(n-1)
diff=(n&(n-1))^n
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
public int singleNumber(int[] nums) {
// 10 ^ 10 == 00
// 两个相同的数异或变成0
int result = 0;
for (int n : nums) {
result = result ^ n;
}
return result;
}
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
public int singleNumber(int[] nums) {
int result = 0;
// 统计每位1的个数
for (int i = 0; i < 64; i++) {
int sum = 0;
for (int n : nums) {
// 统计1的个数
sum += ((n >> i) & 1);
}
// 还原
result |= ((sum % 3) << i);
}
return result;
}
给定一个整数数组nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
public int[] singleNumber(int[] nums) {
// 关键点怎么把a^b分成两部分,方案：可以通过diff最后一个1区分
int diff = 0;
for (int n : nums) {
diff ^= n;
}
int[] result = new int[]{diff, diff};
// 去掉末尾的1后异或diff就得到最后一个1的位置
diff = (diff & (diff - 1)) ^ diff;
for (int n : nums) {
if ((diff & n) == 0) {
result[0] ^= n;
} else {
result[1] ^= n;
}
}
return result;
}
public int hammingWeight(int n) {
int result = 0;
while (n != 0) {
if ((n & 1) == 1) result++;
n = n >>> 1;
}
return result;
}
颠倒给定的 32 位无符号整数的二进制位。
思路：依次颠倒即可
public int reverseBits(int n) {
int result = 0;
int p = 31;
while (n != 0) {
result += ((n & 1) << p);
n >>>= 1;
p--;
}
return result;
}
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
问题转化为求两个给定数字二进制状态下的最长公共前缀，可以用移位判断的思想来做，这里使用另一种
Brian Kernighan算法：number和 number−1之间进行按位与运算后，number中最右边的1会被抹去变成0。public int rangeBitwiseAnd(int m, int n) {
while (m < n) {
// 抹去最右边的 1
n = n & (n - 1);
}
return n;
}
- Java中区分右移运算和无符号右移运算
- 注意运算顺序，不确定时尽量加上括号
最近更新 2yr ago