【算法】位运算合集
零：位运算基础公式
69f072b1f40c4f8da1bc5715ce208e54.png
f2ebc62df8b746e4b68259683f3e697d.png
零：五道基础题
1：位1的个数
a57c502ead044c26879b9cb92254cc77.png
class Solution {
public int hammingWeight(int n) {
int count = 0;
while(n != 0){
n &= (n-1); //干掉n最右侧的1
count++;
}
return count;
}
}2：比特位计数
022fe6e95f9c4175a40c026ef8ea5492.png
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n+1];
for(int i = 0 ; i <= n ; i++ ){
int count = 0 , tem = i;
while(tem != 0){
tem &= (tem-1);//干掉最右侧的1
count++;
}
ans[i] = count;
}
return ans;
}
}3：汉明距离
f416f02d674e4ea1a386b3b221539b80.png
class Solution {
public int hammingDistance(int x, int y) {
int tem = x ^ y;
int count = 0;
while(tem != 0){
tem &= (tem-1);
count++;
}
return count;
}
}4：只出现一次的数字|
b14cfd3025944200b422eef05074b9d3.png
class Solution {
public int singleNumber(int[] nums) {
int ret = nums[0];
for(int i = 1 ; i < nums.length ; i++){
ret ^= nums[i];
}
return ret;
}
}5：只出现一次的数字|||
用位上数字不同进行分组
7ff400c936654a1988e560da5ba2cfd9.png
class Solution {
public int[] singleNumber(int[] nums) {
int ret = 0;
for(int x : nums){
ret ^= x;
}
int sign = ret & (-ret);
int firNum = 0;
int secNum = 0;
for(int x : nums){
if((sign & x) == 0){
firNum ^= x;
}else{
secNum ^= x;
}
}
int[] result = new int[2];
result[0] = firNum;
result[1] = secNum;
return result;
}
}一：判定字符是否唯一
1：位图思想总结
9510a6965e064df199f612dcdb349959.png
c217580a605d4f00820c4a085f303bc8.png
2：位图思想和hash表两种方法
709f1da6ac0146a89799edf98757f667.png
class Solution {
public boolean isUnique(String astr) {
//鸽巢原理优化
if(astr.length() > 26){
return false;
}
//位图原理
char[] str = astr.toCharArray();
int bitMap = 0;
for(int x : str){
int move = x - 'a';
if((bitMap & (1 << move)) == 0){
//bitMap&0001000只有非0或者0两个结果
//说明当前bitMap位是0，那就添加进去
bitMap |= (1 << move);
}else{
return false;
}
}
return true;
}
}
//1:把字符串转化为字符数组
// char[] str = astr.toCharArray();
// //2:把字符扔到hash表中
// Map<Character,Integer> hash = new HashMap<>();
// for(char x : str){
// //获取hash表中x的value值
// int num = hash.getOrDefault(x,0);
// if(num == 0){
// hash.put(x,hash.getOrDefault(x,0)+1);
// }else{
// return false;
// }
// }
// return true;二：丢失的数字
02e3fb40948d445b8a6f0ac6e8eb22a3.png
class Solution {
public int missingNumber(int[] nums) {
//高斯求和
int len = nums.length;
int sum1 = 0;
for(int i = 0 ; i < len ; i++){
sum1 += nums[i];
}
int sum2 = (0+len)*(len+1)/2;
int ret = sum2 - sum1;
return ret;
}
}
// hash数组
// int len = nums.length;
// int[] hash = new int[len+1];
// for(int i = 0 ; i < len ; i++){
// hash[nums[i]] = 1;
// }
// int ret = 0;
// for(int i = 0 ; i < len+1 ; i++){
// if(hash[i] == 0){
// ret = i;
// }else{
// }
// }
// return ret;
// 异或运算方法
// int len = nums.length;
// int[] arr = new int[2*len+1];
// for(int i = 0 ; i < len ; i++){
// arr[i] = nums[i];
// }
// int count = 0;
// for(int i = len ; i < (2*len+1) ; i++){//i作为添加元素的下标
// arr[i] = count;
// count++;
// }
// int ret = 0;
// for(int x : arr){
// ret ^= x;
// }
// return ret;三：两整数之和
耍赖：直接return；正规军：异或运算无进位相加
2fa4ca506d5f4ffc8f7d101d67af4ae0.png
class Solution {
public int getSum(int a, int b) {
while(b != 0){
int ret = a ^ b;//结果
int x = (a & b)<<1;
a = ret;
b = x;
}
return a;
}
}
// return a + b;四：只出现一次的数字||
137. 只出现一次的数字 II - 力扣（LeetCode）
2f60314acc204151886f1e4953ee1ae0.png
65f151292718402c96b5c78c540f0de5.png
class Solution {
public int singleNumber(int[] nums) {
//这一层for循环i作为比特位
int ret = 0;
for(int j = 0 ; j < 32 ; j++){
//所有元素的该bit位相加
int sum = 0;
for(int i = 0 ; i < nums.length ; i++){
sum += (nums[i]>>j)&1;
}
int tem = sum % 3;
if(tem == 1){
ret |= (1<<j);
}else{
ret &= ~(1<<j);
}
}
return ret;
}
}五：消失的两个数字
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
b730107c48e64e1590f8c7fc36fac49d.png
class Solution {
public int[] missingTwo(int[] nums) {
//创建tem数组用来存放nums数组中的元素和1~N数字
int len = nums.length;
int n = len + 2;
int[] tem = new int[2*len+2];
//处理nums数组
int ret = 0;
for(int i = 0 ; i < nums.length ; i++){
ret ^= nums[i];
tem[i] = nums[i];
}
//处理1~N
for(int i = 1 ; i <= n ; i++){
ret ^= i;
tem[len-1+i] = i;
}
int sign = 0;
while(ret != 0){
if( ((ret >> sign) & 1) == 1){
break;
}else{
sign++;
}
}
//基于sign把数组分成两组
int[] result = new int[2];
for(int x : tem){
if(((x >> sign) & 1) == 1){
result[0] ^= x;
}else{
result[1] ^= x;
}
}
return result;
}
}class Solution {
//穷举法
public int[] missingTwo(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
int[] ret = new int[2];
int j = 0;
for(int i = 0 ; i < nums.length-1 ; i++){
int tem = nums[i+1] - nums[i];
if(tem == 2){
ret[j++] = nums[i]+1;
}else if(tem == 3){
ret[j++] = nums[i]+1;
ret[j] = nums[i]+2;
}
}
if(nums[0] != 1){
if(ret[0] == 0){
ret[0] = 1;
if(len == 1){
if(nums[0]-1 > 1){
ret[1] = 2;
}else{
ret[1] = 3;
}
}else{
ret[1] = nums[len-1]+1;
}
}else{
if(ret[1] == 0){
ret[1] = 1;
}else{
}
}
}else{
if(ret[0] == 0){
ret[0] = nums[len-1]+1;
ret[1] = nums[len-1]+2;
}else{
if(ret[1] == 0){
ret[1] = nums[len-1]+1;
}else{
}
}
}
return ret;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-12-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
