网站内容页设计,出版社类网站模板,广州注册公司地址,教务处教务网络管理系统目录 前言
一.常见的小问题
1.给定一个数n,确定它的二进制表示中的第x位是0还是1
2.给定一个数n#xff0c;将它的二进制表示中的第x位修改成1
3.给定一个数n#xff0c;将它的二进制表示中的第x位修改成0
4.给定一个数n#xff0c;提取它的二进制表示中最右侧的1…目录 前言
一.常见的小问题
1.给定一个数n,确定它的二进制表示中的第x位是0还是1
2.给定一个数n将它的二进制表示中的第x位修改成1
3.给定一个数n将它的二进制表示中的第x位修改成0
4.给定一个数n提取它的二进制表示中最右侧的1即将其它位置位0
5.给定一个数n去掉它的二进制表示中最右侧的1 6.异或运算的规则
二.典型例题 前言
位运算是一类常考的题型关于位运算的操作符有以下几种: 按位取反~ 左移操作符 右移操作符 按位与 按位或 | 按位异或^ 重点要区分|和^这几个操作符按位与是有0则0按位或是有1则1
按位异或相同为0相异为1。也可以记成“无进位相加”例如112 因为是二进制所以变成0但是不进位。
接下来介绍怎么利用这些操作符来解决常见的问题
一.常见的小问题
1.给定一个数n,确定它的二进制表示中的第x位是0还是1
首先声明默认最低位是第0位。 方法将n右移x位与1做按位与操作若结果为1则n的第x位是1若结果是0则第x位是0 说明右移操作是为了将第x位移到最低位方便与1的最低位按位与而1的其它位全是0有0则0故其它位的结果肯定是0而最低位的结果则取决于x位是0还是1 代码操作(n x) 1
2.给定一个数n将它的二进制表示中的第x位修改成1 方法将1左移x位再与n按位或 说明将1左移x位是为了对n的第x位进行“定向打击”1的第x位是1其余位是0。按位或的特点是有1则1故结果的第x位肯定是1其它位取决于n的其它位是0还是1,和原来相比不会变化 代码操作n (1 x) | n
3.给定一个数n将它的二进制表示中的第x位修改成0 方法将1左移x位按位取反再与n按位与 说明按位与的特点是有0则0故结果的第x位肯定是0其它位取决于n的其它位是0还是1和原来相比不会发生变化 代码操作n (~(1 x) ) n
4.给定一个数n提取它的二进制表示中最右侧的1即将其它位置位0 方法n -n 说明由n向-n转变先将n按位取反然后加1这样使得n最右侧的1左边区域全变成相反右边区域全变成0而按位与的特点是有0则0故只有最右侧的1异或的结果是1其余全是0。 5.给定一个数n去掉它的二进制表示中最右侧的1 方法n (n - 1) 说明由n到n-1最右侧1的左边区域不变右边区域包括1全部变成相反按位与的特点是有0则0故最右侧的1肯定会变成0其余位不变 6.异或运算的规则 a ^ 0 a a ^ a 0 a ^ b ^ c a ^ c ^ b 二.典型例题
接下来有几道例题大家可以先尝试做一做答案放在下面了
位1的个数
class Solution {
public:int hammingWeight(uint32_t n) {int ret 0;for (int i 0; i 31; i){if (((n i) 1) 1){ret;}}return ret;}
}; 比特位计数
class Solution {
public:vectorint countBits(int n) {//x(x-1)将x的最右侧的1变成0vectorint v(n 1);for (int i 0; i n; i){int x i;int count 0;while (x){count;x x (x - 1);}v[i] count;}return v;}
}; 汉明距离
class Solution {
public:int hammingDistance(int x, int y) {int n x ^ y;//统计有多少个1int ret 0;while (n){ret;n n (n - 1);}return ret;}
}; 只出现一次的数字
class Solution {
public:int singleNumber(vectorint nums) {int ret 0;for (int i 0; i nums.size(); i){ret ^ nums[i];}return ret;}
}; 只出现一次的数字iii
class Solution {
public:vectorint singleNumber(vectorint nums) {//目标将两个单身狗分开相同的数不拆散再将两组分别异或//方法根据两个单身狗任意一个不同的比特位来进行分组int n 0;for (auto e : nums){n ^ e;}//找到比特位是1的位置--两个单身狗这一位不同int pos 0;for (int i 0; i 31; i){if (((n i) 1) 1) {pos i;break;}}//根据这一位置的值将所有数分成两组异或int ret1 0, ret2 0;for (auto e : nums){if (((e pos) 1) 0){ret1 ^ e;}else{ret2 ^ e;}}return {ret1, ret2};//隐式类型转换}
};
