企业官网建设流程全解析

目录

一、基础知识

1.基础位运算

2.给一个数n，确定它的二进制表示中的第x位是0还是1

3.将一个数n的二进制表示的第x位修改成1

4.将一个数n的二进制表示的第n位修改成0

5.位图的思想

6.提取一个数n，二进制表示中最右侧的1

7.将一个数n二进制表示中最右侧的1抹去

8.位运算的优先级

9.异或 ^,运算的运算律

二、基础题目示例

1.位1的个数

2.比特位计数

3.汉明距离

4.只出现一次的数字

5.只出现一次的数字3

三、题目演示

1.判断字符是否唯一

2.丢失的数字

3.两整数之和

4.只出现一次的数字2

5.消失的两个数字

一、基础知识

1.基础位运算

<< 左移操作符 &按位与 有0就是0

>>右移操作符 | 按位或 有1就是1

~按位取反 ^异或 相同为1，相异为0 / 无进位相加

例如 1 0 1 1 0 1 ^

1 1 0 1 1 0

结果为 0 1 1 0 1 1，无进位相加就是1 + 0 = 0，1+1 = 0，但是不会向高位进位

2.给一个数n，确定它的二进制表示中的第x位是0还是1

我们规定从右往左，的位数为第0，1，2，3，4，5.....31位

这样右移动的距离等于它的位数

(n >> x) & 1 -> 0 ------ 0

1 ------ 1

3.将一个数n的二进制表示的第x位修改成1

n = n | (1 << x)

4.将一个数n的二进制表示的第n位修改成0

n = n &(~(1 << x))

5.位图的思想

每个比特位0或者1的数值表示一种状态

6.提取一个数n，二进制表示中最右侧的1

lowbit = n & -n(取反加一即变为负)

7.将一个数n二进制表示中最右侧的1抹去

n = n & (n - 1)

8.位运算的优先级

能加括号就加括号

9.异或 ^,运算的运算律

1.a ^ a = 0

2.a ^ 0 = a

3.a ^ b ^ c = a ^ (b ^ c)

二、基础题目示例

1.位1的个数

. - 力扣（LeetCode）

class Solution { public: int hammingWeight(int i) { int ret = 0; int n = 32; while(n > 0) { if((i & 1) == 1)ret++; i = i >> 1; n--; } return ret; } };

将要判断的数每次按位与1，若为1则此位为1，然后再右移一位

2.比特位计数

. - 力扣（LeetCode）

class Solution { public: int Add(int i) { int ret = 0; int n = 32; while(n > 0) { if((i & 1) == 1)ret++; i = i >> 1; n--; } return ret; } vector<int> countBits(int n) { vector<int>ret(n+1,0); for(int i = 0; i <= n;i++) { ret[i] = Add(i); } return ret; } };

原理同上，只是多了一个循环

3.汉明距离

. - 力扣（LeetCode）

class Solution { public: int hammingDistance(int x, int y) { int n = 32; int ret = 0; while(n>0) { if((x & 1) != (y & 1))ret++; x = x >> 1; y = y >> 1; n--; } return ret; } };

分别用 &1 来判断两个数最低位是0还是1，对两个数进行比较，然后分别不断右移这两个数

4.只出现一次的数字

. - 力扣（LeetCode）

利用异或的性质即可

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

5.只出现一次的数字3

. - 力扣（LeetCode）

class Solution { public: vector<int> singleNumber(vector<int>& nums) { long long n = 0; for(auto ch: nums) { n ^= ch; } long long mask = n &(-n); mask = (int)mask; vector<int>ret(2,0); for(auto ch: nums) { if((ch & mask) == mask)ret[0] ^= ch; else ret[1] ^= ch; } return ret; } };

我们先将所有值异或，这个过程会将相同的数都消去，最后得到两个不同的数a，b异或的结果。

这个数为1的位置，是两个数上值不同的位置。为了方便，我们取出最右侧的1。

a，b两个数中，一个数的该位置为1，一个数为0.

而待分开的数的该位置也一定为1或0.因此我们将全部数分为两组

a，xx yy zz b，mm，nn，oo

这样即可分别取出单独的数

三、题目演示

1.判断字符是否唯一

. - 力扣（LeetCode）

class Solution { public: bool isUnique(string astr) { int size = astr.size(); if(size>26)return false; int bitmap = 0; for(int i = 0; i < size; i++) { int distance = astr[i]-'a'; if(((bitmap >> distance) & 1) == 1)return false; else { bitmap = bitmap | (1 << distance); } } return true; } };

这里我们不使用数据结构，我们使用位图来储存信息，达到减小空间复杂度的效果。每个比特位储存一个字符的存在情况，‘a’的位置是右侧第一位，我们记为0下标。

首先我们记录字符串的长度，来进行遍历操作，如果字符串比26长，那么必定有重复

每次进入循环的时候，我们查看这个字符对应位置是否为1，如果是，我们返回fasle，如果不是，我们将位图的此位改为1.

2.丢失的数字

. - 力扣（LeetCode）

class Solution { public: int missingNumber(vector<int>& nums) { int size = nums.size(); int ret = 0; for(int i = 0; i < size; i++) { ret = ret ^(nums[i]); } for(int i = 0; i <= size; i++) { ret = ret ^ i; } return ret; } };

利用异或的性质，例如

我们选取0-5中的5个数字

1 5 2 3 0

0 1 2 3 4 5

我们用0分别遍历异或上下两组数字，上下两组中相同的数字进过异或都变为0，最后只剩下0-5中剩余的那个数字，也即丢失的数字， 0 ^ 这个数字，仍然为这个数字

3.两整数之和

. - 力扣（LeetCode）

class Solution { public: int getSum(int a, int b) { while(a & b) { int tmp = a; a = a ^ b; b = (tmp & b) << 1; } return a ^ b; } };

我们首先要知道，异或运算是一种无进位相加，那我们如何做到有进位呢？只需要把a按位与b即可，这样我们可以知道哪些位置是要进位的，然后再左移一位，相当于进位操作。

但是进位之后相加还可能再次进位，因此我们循环这个过程，我们不断用a^b,a&b更新a和b的值，直到a&b为0。此时无进位。因为任意数异或0等于它本身，因此我们循环结束统一返回a^b即可

4.只出现一次的数字2

. - 力扣（LeetCode）

class Solution { public: int singleNumber(vector<int>& nums) { int size = nums.size(); int ret = 0; for(int i = 0; i < 32; i++) { int sum = 0; for(auto ch:nums) { sum += (ch >> i)&1; } sum = sum % 3; if(sum)ret = ret | (sum << i); } return ret; } };

原理如上，可以推广，任意重复n次就对n取余

5.消失的两个数字

. - 力扣（LeetCode）

class Solution { public: vector<int> missingTwo(vector<int>& nums) { int size = nums.size()+2; int n = 0; for(int i = 1; i <= size; i++) { n ^= i; } for(auto ch:nums) { n ^= ch; } long long mask = n &(-n); vector<int>ret(2); for(int i = 1; i <= size; i++) { if((i & mask) == mask)ret[0] ^= i; else ret[1] ^= i; } for(auto ch:nums) { if((ch & mask) == mask)ret[0] ^= ch; else ret[1] ^= ch; } return ret; } };

与基础题目示例中的5.只出现一次的数字3相似，只是遍历范围是一个数组加上一串连续的数字