网站认证金额怎么做分录,成都高端网站制作公司,懒人手机网站模板,美食的网页设计一、位运算符及其优先级
我们知道#xff0c;计算机中的数在内存中都是以二进制形式进行存储的 #xff0c;而位运算就是直接对整数在内存中的二进制位进行操作#xff0c;因此其执行效率非常高#xff0c;在程序中尽量使用位运算进行操作#xff0c;这会大大提高程序的性…一、位运算符及其优先级
我们知道计算机中的数在内存中都是以二进制形式进行存储的 而位运算就是直接对整数在内存中的二进制位进行操作因此其执行效率非常高在程序中尽量使用位运算进行操作这会大大提高程序的性能。
那么涉及位运算的运算符如下表所示 注意参与位运算的对象只能是整型数据(int, unsigned, char)不能为实型 异或运算符的运算律
异或0a^0 a;消消乐a^a 0;交换律和结合律abc acb; abc a(bc);
位运算符的优先级
优先级需要弄清楚如果不太清楚可以加小括号确保是想要的运算顺序这里只是相对优先级即只是和一些常用的算术运算符做比较。 二、位运算的应用
2.1 判断位
给一个数n确定它的二进制表示中的第x位是0还是1
算法(nx)1
原理按位与的运算规则——有0则0遇1不变
举例判断第3位
11001010 //n 00011001 //n3 00000001 //1 00000001 //结果 2.2 打开位
将一个数n二进制表示的第x位修改成1
算法n | (1x)
原理按位或的运算规则——有1则1遇0不变
举例打开第4位
11001010 //目标 00010000 //14 11011010 //| 得结果 2.3 关闭位
将一个数n二进制表示的第x位修改成0
算法n ~(1x)
原理按位与的运算规则——有0则0遇1不变
举例关闭第7位
11001000 //目标 10000000 //17 01111111 //~(17) 01001000 // 得结果 2.4 转置位
将一个数n二进制表示的第x位转置0变11变0
算法n ^ (1x)
原理按位异或的运算规则——0变11变0
举例转置第4位
11011010 //目标 00010000 //14 11001010 //^ 得结果 2.5 位图 定义和特性位图是一种数据结构它由一个二进制位数组或者比特数组组成每个位bit只能存储 0 或 1。位图通常被用来表示大量整数的集合通过位的状态来表示该整数是否出现在集合中。位图支持高效的位操作如按位与、按位或、按位异或等适合用于高效地存储和操作大量的布尔型数据。
实现方式位图可以被实现为一个数组其中每个元素都是一个字节而每个字节又包含8个位。对于很大的位图可以使用多个数组进行分段存储。位图通常不仅仅用于表示整数的集合还可以用于标记某个特定值是否存在。
详细内容请阅读文章【高阶数据结构】哈希的其他应用 {位图的介绍及实现位图的组合应用布隆过滤器的介绍及实现布隆过滤器的应用哈希切分}-CSDN博客 2.6 get lowbit
提取一个数n二进制表示中最低位的1
算法n -n
原理-n按位取反再加1将最低位的1左边的位不包括logbit位全部转置左边转置后按位与得0右边相同位按位与不变。
举例
11011000 //目标 00101000 //-n 00001000 // 得结果 2.7 close lowbit
关闭一个数n二进制表示中最低位的1
算法n (n-1)
原理n-1 将最低位的1右边的位包括logbit位全部转置左边相同位按位与不变右边转置后按位与得0。
举例
11011000 //目标 11010111 //n-1 11010000 // 得结果 2.8 其他 位运算实现乘除法将a左移一位实现*2将a右移一位实现/2。 a n ≡ a ∗ 2^na n ≡ a / 2^n 统计二进制数中有多少个1 int func(int x){int count0;while (x){count;xx(x-1); //将lowbit关闭}return count;
}字符的大小写转换对应大小写字母ASSIC码的二进制数只有第5位不同大写为0小写为1因此可以通过操作第5位实现大小的相互转换 字符小写转大写ch~32; 字符大写转小写ch|32; 字符大小写互换ch^32; 交换两变量的值aa^b; ba^b; aa^b;异或运算符的运算律结合律、消消乐 三、相关编程题
3.1 位1的个数
题目链接
191. 位1的个数 - 力扣LeetCode
题目描述 算法原理
不断的close lowbit每关闭一个1count就直到将所有的1都关闭量的值变为0。
编写代码
class Solution {
public:int hammingWeight(int n) {int count 0;while(n0){n (n-1);count;}return count;}
};3.2 比特位计数
题目链接
338. 比特位计数 - 力扣LeetCode
题目描述 算法原理
同上 close lowbit
编写代码
class Solution {
public:vectorint countBits(int n) {vectorint ans(n1, 0);for(int i 0; i n; i){int count 0;int k i;while(k0){count;k k-1;}ans[i] count;}return ans;}
};3.3 汉明距离
题目链接
461. 汉明距离 - 力扣LeetCode
题目描述 算法原理
异或运算相异为1相同为0。tmp x^y将x和y二进制表示中不同的位置置为1相同的位置置为0。再统计tmp中位1的个数即可原理同上 close lowbit
编写代码
class Solution {
public:int hammingDistance(int x, int y) {int tmp x ^ y;int count 0;while(tmp0){count;tmp tmp-1;}return count;}
};3.4 只出现一次的数字
题目链接
136. 只出现一次的数字 - 力扣LeetCode
题目描述 算法原理
异或运算的运算律消消乐
编写代码
class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for(auto e : nums){ret ^ e;}return ret;}
};3.5 只出现一次的数Ⅲ
题目链接
260. 只出现一次的数字 III - 力扣LeetCode
题目描述 算法原理
将所有的数按位异或到tmp最终其实就是只出现一次的两个数的异或结果即将两个数不同的位置置为1。get lowbit将tmp的最低位1取出还是存入tmp。注意有符号数需要特殊处理INT_MIN符号位为1其他位为0有符号数取反的位操作是符号位不变其他位取反再1。INT_MIN取反会溢出。实际上INT_MIN的lowbit就是它本身。再次遍历数组判断所有数的tmp位异或结果的最低位1将只出现一次的两个数分到不同的组中进行异或最终就能分别得到这两个数了。
编写代码
class Solution {
public:vectorint singleNumber(vectorint nums) {int tmp 0;for(auto e : nums){tmp ^ e;}tmp tmpINT_MIN? tmp:tmp(-tmp); //get lowbitvectorint ret(2, 0);for(auto e : nums){if(e tmp){ret[0] ^ e;}else{ret[1] ^ e;}}return ret;}
};3.6 判定字符是否唯一
题目链接
面试题 01.01. 判定字符是否唯一 - 力扣LeetCode
题目描述 算法原理 编写代码
//用一个int数据充当位图
class Solution {
public:bool isUnique(string astr) {// 利用鸽巢原理进行优化if(astr.size() 26)return false;// 用位图判断一个字符是否在集合中int bitmap 0;for(auto e : astr){int tmp 1 (e-a);if(!(bitmap tmp)){bitmap | tmp;}else{return false;}}return true;}
};//用STL的bitset数据结构
class Solution {
public:bool isUnique(string astr) {if(astr.size() 26)return false;bitset26 bs;for(auto e : astr){int x e - a; //位图的第x位if(!bs.test(x)){bs.set(x);}else{return false;}}return true;}
};3.7 丢失的数字
题目链接
268. 丢失的数字 - 力扣LeetCode
题目描述 算法原理 编写代码
class Solution {
public:int missingNumber(vectorint nums) {int ret 0;int i 0;for(; i nums.size(); i){ret ^ nums[i];ret ^ i;}ret ^ i;return ret;}
};3.8 两整数之和
题目链接
371. 两整数之和 - 力扣LeetCode
题目描述 算法原理 编写代码
class Solution {
public:int getSum(int a, int b) {int bitsum a ^ b; //无进位相加的结果int bitcarry (a b)1; //进位的结果while(bitcarry ! 0) //当不再有进位时退出循环{a bitsum;b bitcarry;bitsum a ^ b;bitcarry (a b)1;}return bitsum;}
};3.9 只出现一次的数字Ⅱ
题目链接
137. 只出现一次的数字 II - 力扣LeetCode
题目描述 算法原理
依次确定每一个二进制位
为了方便叙述我们称「只出现了一次的元素」为「答案」。
由于数组中的元素都在 int即 32 位整数范围内因此我们可以依次计算答案的每一个二进制位是 0 还是 1。
具体地考虑答案的第 i 个二进制位i 从 0 开始编号它可能为 0 或 1。对于数组中非答案的元素每一个元素都出现了 3 次对应着第 i 个二进制位的 3 个 0 或 3 个 1无论是哪一种情况它们的和都是 3 的倍数即和为 0 或 3。因此
答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。
这样一来对于数组中的每一个元素 x我们使用位运算 (x i) 1得到 x 的第 i 个二进制位并将它们相加再对 3 取余得到的结果一定为 0 或 1即为答案的第 i 个二进制位。
编写代码
class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for(size_t i 0; i 32; i){int bitsum 0;for(auto e : nums){bitsum(ei)1;}bitsum % 3;ret | (bitsumi);}return ret;}
};3.10 消失的两个数字
题目链接
面试题 17.19. 消失的两个数字 - 力扣LeetCode
题目描述 算法原理 编写代码
class Solution {
public:vectorint missingTwo(vectorint nums) {int tmp 0;//异或到一起for(auto e : nums) tmp ^ e; //原数组for(int i 1; inums.size()2; i) tmp ^ i; //全数组//此时的tmp种存放的是消失的两个数字的异或结果int lowbit tmpINT_MIN? tmp:tmp(-tmp);vectorint ret(2, 0);//划分成两类异或for(auto e : nums) //原数组if(e lowbit) ret[0] ^ e;else ret[1] ^ e;for(int i 1; inums.size()2; i) //全数组if(i lowbit) ret[0] ^ i;else ret[1] ^ i; return ret;}
};
