一、位运算简介及常用操作
基础位运算：
位运算符的优先级：
给一个数n确定他的二进制表示的第x位（二进制表示从右向左从第一位是0）是0还是1:
将一个数n的二进制表示的第×位修改成1：
将一个数的二进制表示的第×位修改成0：
位图的思想：
提取一个数(n)二进制表示中最右侧的1：
干掉一个数()二进制表示中最右侧的1：
异或(^)运算的运算律
二、191.位1的个数
题目链接：191.位1的个数
题目描述：
题目解析：
- 就是返回一个正数的二进制表示中1的个数。
解题思路：
- 直接该数第0位按位与上1，判断是不是1。
- 然后该数向右移动一位。循环到数变为0即可。
解题代码：
//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
public int hammingWeight(int n) {
int ret = 0;
while(n != 0) {
ret += n & 1;
n = n >> 1;
}
return ret;
}
}
三、338.比特位计数
题目链接：338.比特位计数
题目描述：
题目解析：
- 返回0到n中每个数二进制表示的1的个数，记录在对应下标数组中。
解题思路：
- 直接循环遍历0到n，再调用第二题的方法即可。
解题代码：
//时间复杂度:O(n^2)
//空间复杂度:O(n)
class Solution {
public int[] countBits(int n) {
int[] ret = new int[n+1];
for(int i = 0; i <= n; i++) {
ret[i] = hammingWeight(i);
}
return ret;
}
//一个数二进制表示，位1的个数
public int hammingWeight(int n) {
int ret = 0;
while(n != 0) {
ret += n & 1;
n = n >> 1;
}
return ret;
}
}
四、461.汉明距离
题目链接：461.汉明距离
题目描述：
题目解析：
- 就是求两个正数，二进制表示的对应位不相同的个数。
解题思路：
- 先将两数异或，不同的位就是1了。
- 调用题目二中的求1的个数的方法即可。
解题代码：
//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
public int hammingDistance(int x, int y) {
int n = x ^ y;
return hammingWeight(n);
}
//一个数二进制表示，位1的个数
public int hammingWeight(int n) {
int ret = 0;
while(n != 0) {
ret += n & 1;
n = n >> 1;
}
return ret;
}
}
五、136.只出现一次的数字
题目链接：136.只出现一次的数字
题目描述：
题目解析：
- 给你一个数组，数组中元素只有一个出现一次，其余全是两次。找到这个只出现一次的数组元素并返回。
解题思路：
- 直接将数组中所有元素一一异或，到最后出现两次的元素都变为0，只剩下要找的元素了。
解题代码：
//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
public int singleNumber(int[] nums) {
int ret = nums[0];
for(int i = 1; i < nums.length; i++)
ret ^= nums[i];
return ret;
}
}
六、260.只出现一次的数字 III
题目链接：260.只出现一次的数字 III
题目描述：
题目解析：
- 一个数组，数组中元素只有两个元素只出现一次，其余全是两次。找到这两个只出现一次的数组元素并返回。
解题思路：
- 先将所有的元素全部异或在一起，就相当于两个只出现一次的元素异或在一起。
- 在去出上诉异或结果，最右边的1。这位上两个数字是不相同的。
- 所以再次遍历数组与结果数组异或，如果该位上与第二步结果相同放一个下标，不同放另一个下标。最后得到的就是结果了
解题代码：
//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
public int[] singleNumber(int[] nums) {
int[] ret = new int[2];
int n = nums[0];
for(int i = 1; i < nums.length; i++)
n ^= nums[i];
int last = n & -n;
for(int i = 0; i < nums.length; i++) {
if((nums[i] & last) == 0)
ret[0] ^= nums[i];
else
ret[1] ^= nums[i];
}
return ret;
}
}