首页 > 其他分享 >位运算总结

位运算总结

时间:2022-11-22 14:07:37浏览次数:52  
标签:总结 return 运算 nums int res 整数 二进制


常用的位运算有6个:
​​​&​​​​|​​​​~​​​​^​​ 相当于不进位的加法
​<<​​ << 1 相当于x2 上取整 << 3相当于x8
​>>​​ >> 1 相当于/2 下取整

技巧篇

  1. lowbit运算1:​​n & -n​​​ 表示 n的二进制表示里最右边的1,所以 ​​n & -n == n​​​ 表示n为2的整数次幂,​​n & -n < n​​则n不为2的整数次方
  2. lowbit运算2:​​n & (n -1)​​就会把该整数二进制的最后一位1置零
  3. 异或运算^: ​​a ^ a = 0​​​ , ​​0 ^ a = a​​而且异或满足交换律结合律

实战篇:剑指offer15题——二进制中的1的个数

本题思考方式可以将数字的最后一位和1进行与运算,然后右移来统计二进制中的1.但是如果整数为负数的时候,就会出现补1的情况从而造成死循环。

解决办法1

将输入的数字强制转换成​​unsigned int​​类型即可。

class Solution {
public:
int NumberOf1(int n) {
int res = 0;
unsigned int un = n;
while (un) res += un & 1, un >>= 1;
return res;
}
};

解决办法2

设置一个unsigned int flag = 1 每次与输入整数进行与运算后判断是否为1尔后左移统计1的个数,从而负数高位补零造成死循环。

class Solution {
public:
int NumberOf1(int n) {
int res = 0;
unsigned int flag = 1;
while (flag) {
if (flag & n) res++;
flag <<= 1;
}
return res;
}
};

解决办法3

n & (n -1)就会把该整数二进制的最后一位1置零。那么二进制数有多少个1就会进行多少次这样的操作。

class Solution {
public:
int NumberOf1(int n) {
int res = 0;
while (n){
n &= (n + 1);
res++;
}
return res;
}
};

LeetCode231:2的幂

​给定一个整数,编写一个函数来判断它是否是 2 的幂次方。​​ 利用lowbit运算即可判断:

class Solution {
public:
bool isPowerOfTwo(int n) {
//return n > 0 && (n & -n) == n;
return (n > 0) ? ((n & -n) == n) : false;
}
};

LeetCode762:二进制表示中质数个计算置位

​给定两个整数 L 和 R ,找到闭区间 [L, R] 范围内,计算置位位数为质数的整数个数。​​ 注意:

  • 计算置位代表二进制表示中1的个数。
  • L, R 是 L <= R 且在 [1, 位运算总结_位运算] 中的整数。
  • R - L 的最大值为 10000。

解题思路

  • 根据R的上限可以判断R <= 位运算总结_数据_02,因为位运算总结_位运算_03是1024,1024的平方大于位运算总结_位运算,所以判断正确,可以定义位运算总结_数组_05存储枚举的素数。
  • 在循环前设置结果变量res,初始化为0;
  • 外循环遍历数据范围,内循环遍历当前数据二进制的每一位进行lowbit操作,将数据最右侧1置零,同时统计1的个数。若统计个数在枚举的容器中,则结果加1;最后返回res就是最终答案。
class Solution {
public:
int countPrimeSetBits(int L, int R) {
unordered_set<int> prime({2, 3,5,7,11,13,17,19});
int res = 0;
for (int n = L; n <= R; n++){
int sum = 0;
for (int k = n; k; k &= (k - 1))
sum++;
if (prime.count(sum))
res++;
}
return res;
}
};

LeetCode136:只出现1次的数字

​给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。​​ 运用异或的性质即可,相同数字异或相当于消消乐,即为0,而0与任何数字异或都等于当前数字。

class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (auto x : nums)
res ^= x;
return res;
}
};

LeetCode137:只出现1次的数字II

​给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。​​ 要求:不使用额外的空间

class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (int bit = 0; bit < 32; bit++){
int counter = 0;
for (int i = 0; i < nums.size(); i++)
counter += (nums[i] >> bit) & 1;
res += (counter % 3) << bit;
}
return res;
}
};

LeetCode137:只出现1次的数字III

​给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。​

class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int s = 0;
for (auto x : nums) s ^= x; // 消除了相同数字,只剩下只出现一次的两个数字异或
//假设 s = a ^ b

int k = 0;
while (!(s >> k & 1)) // 求一个整数s的第k位是0还是1,比较常用的技巧
k++;

int s2 = 0;
for (auto x : nums)
if (x >> k &1)
s2 ^= x; // s2 = a
// 所以 s ^ s2 = a ^ b ^ a = b;
return vector<int>({s2, s ^ s2});

}
};

LeetCode476: 数字的补数

​给定一个正整数,输出它的补数。补数是对该数的二进制表示取反。​

  1. 输入两个数m和n,计算需要改变m的二进制表示的多少位才能得到n。


标签:总结,return,运算,nums,int,res,整数,二进制
From: https://blog.51cto.com/u_13875041/5877887

相关文章

  • 查找算法总结
    顺序查找基本思想intsearch(inta[],intn,intkey){for(inti=0;i<n;i++)if(a[i]==key)returni+1;return0;}经典查找——设......
  • 【Mybatis学习总结九】Spring中集成Mybatis
    学习了Mybatis的基本内容后,现在最重要的内容莫过于是在Spring中集成Mybatis了。好处之一就是不用再单独配置Mybatis-config.xml文件了(含有数据库连接池和配置类名以及注册......
  • 【Mybatis学习总结八】Mybatis缓存
    这节内容了解下即可。如多数持久层框架一样,Mybatis同样提供了一级缓存和二级缓存。(*)一级缓存:(1)一级缓存也就是Session级的缓存,默认是开启的,查询操作是使用缓存的;(2)必须是......
  • 【Mybatis学习总结七】调用存储过程
    今天这节课本来可以一小时结束的,我却从三点半搞到了九点。我觉得我是世界上最S13的人!!!没有之一!!!!一个小错害我花了一个晚上的时间去寻找,真是够无语的。好了,言归正传,还是先总结......
  • 【Mybatis学习总结六】动态SQL与模糊查询
    六、动态SQL与模糊查询学数据库的时候有学过模糊查询。如:根据姓名模糊匹配和指定年龄区间来查询用户信息:SQL语句可以这样来写:SELECT*FROMd_userWHEREnamelike'%m%'......
  • 【Mybatis学习总结五】实现关联表查询----一对多关联(collection)
    实现关联表查询----一对多关联(collection)一对多需求:即一张表class中又含有多张表(teacher,student)内容。现根据class_id来获取对应的班级信息(包括学生和老师信息)。1......
  • 【Mybatis学习总结四】实现关联表查询----一对一关联(association)
    一、一对一关联建立的数据表class(班级)含有班级信息和teacher(教师)信息,而教师信息在零一张表Teacher中;即class表与Teacher相互关联的;现在需要根据class表的id查询class信息......
  • 【Mybatis学习总结三】Mybatis种解决字段名与实体类属性名不相同的冲突
    Mybatis种解决字段名与实体类属性名不相同的冲突    在开发中,先创建一个数据表,数据表中包含字段名如(order_id,order_no)..而在创建实体类的时候,对象的属性名可能为(i......
  • 【Mybatis学习总结二】Mybatis操作数据表的CRUD实现
    本节内容学习了如何通过Mybatis实现对数据库的增删改查操作。一共有两种实现方式,一是基于XML的实现;第二种是基于注解的实现。下面来具体介绍两种方法的具体实现:一、基于XML......
  • 用户背包优化分析与总结
    用户背包拉取列表接口数量变更推送旧每次点击用户背包,都拉取列表,每次道具消耗,都删除道具列表缓存保证一致性。缺点,单个道具的变更,会影响到整个列表缓存的生命周期,在道具量比......