基础
1.基础知识
以下都是针对数字的二进制进行操作
- >> 右移操作符
- << 左移操作符
- ~ 取反操作符
- & 有0就是0，全一才一
- | 有一才一 ，全0才0
- ^ 相同为0，相异为1
异或( ^ )运算的规律
- a ^ 0 = a
- a ^ a = 0
- a ^ b ^ c =a ^ (b ^ c)
2.基础操作
1.给一个数n， 判断它的二进制表示中的第x位是0 还是 1
( n >> x ) & 1
2.给一个数n， 将它的二进制表示中的第x位是修改为1
n = n | (1<<x)
3.给一个数n， 将它的二进制表示中的第x位是修改为0
n = n & (~ (1<<x) )
4.提取一个数（ n )二进制表示最右侧的 1
这个意思：将这个数二进制形式，其中从右往左出现的第一个数字1，给保留下来，其它的位的数统统赋值给 0
n & (-n) 得到的就是
-n 表示的就是：从右往左出现的第一个数字1，它的左边区域全部变成相反的
5.干掉一个数（ n )二进制表示最右侧的 1
n & （ n-1 ）
n-1 表示的是：从右往左出现的第一个数字1，它的右边(包括它本身)全部变成相反
Leetcode刷题
题一：位1的个数
1. 链接
191. 位1的个数 - 力扣（LeetCode）
2.思路
直接将这个数（二进制表示形式）从右往左每次干掉一个1，然后在更新这个数，同时去统计一下总共进行了几次
3. 代码
int hammingWeight(uint32_t n) {
int count=0;
while(n)
{
n=n&(n-1);
count++;
}
return count;
}题二：比特位计数
1. 链接
338. 比特位计数 - 力扣（LeetCode）
2.思路
暴力方法
遍历 n 个数，每次统计此次所对应的数二进制里有几个1（这个就是题目一），然后再放到数组里去
动态规划
arr为我们最终返回的那个数组名
规律
- 我们让 arr [0] = 0
- 当数字为偶数时，此时该数字（n）所含一的个数与 n / 2这个数相等
- 当数字为奇数时，此时这个数（n）所含一的个数等于 n-1这个所对应的再加上1
3.代码
//暴力
class Solution {
public:
vector<int> countBits(int n) {
vector<int> arr(n+1);
for(int i=1;i<=n;i++)
{
int ret=0;
while(i>0)
{
i=i&(i-1);
ret++;
}
arr[i]=ret;
}
return arr;
}
};//动态规划
class Solution {
public:
vector<int> countBits(int n) {
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) {
if (i % 2 != 0) {
arr[i] = arr[i - 1] + 1;
} else {
arr[i] = arr[i / 2];
}
}
return arr;
}
};题三：汉明距离
1. 链接
461. 汉明距离 - 力扣（LeetCode）
2. 思路
- 首先找到二个数中最大的数，在对最大的数，进行除二，求出其二进制的位数
- 定义一个变量count，当 ((x >> i) & 1) ! = ((y >> i) & 1) 成立时，就让count++
((x >> i) & 1) != ((y >> i) & 1) 这个是基础操作里的如何判断一个数第i位是否为 1
3.代码
class Solution {
public:
int hammingDistance(int x, int y) {
int _max = max(x, y);
int count = 0;
while (_max) {
_max = _max / 2;
count++;
}
int lenSum = 0;
for (int i = 0; i < count; i++) {
if (((x >> i) & 1) != ((y >> i) & 1)) {
lenSum++;
}
}
return lenSum;
}
};题四：判断字符是否唯一
1.链接
面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
2.思路
鸽巢原理：有n个巢，和n+1个鸽子，那么至少会有一个巢鸟的数量>1
astr 是字符串数组名
用数组来模拟哈希表
- 由于只含有小写字母，那么只要开辟一个数组长度为26的就可以
- 如果字符串的长度大于26，那么则就返回 false（鸽巢原理）
- 当字符串的长度小于26，这里的映射关系是 astr[i] - 'a'
- 先让此刻的字符进入哈希表，再去判断该字符在哈希表中位置的值是否大于1
- 若大于1，则返回 false，否则，就继续循环
用一个整数来模拟位图
- 一个整数是4个字节，一个字节是8个比特位，那么就是有36位比特位
- 由于只含有小写字母，那么一个整数就够用
- 如果字符串的长度大于26，那么则就返回 false（鸽巢原理）
- 定义一个整数biteMap，并初始化为0（保证此刻biteMap的二进制位都为0，为了方便后面判断 ）
- 再去遍历这个 astr 字符串，先判断该字符在位图所在位置是否为1，
- 若为1，则返回false
- 若不为1，则将该字符在位图所在位置修改为1，在继续循环。
- 若能将这个循环结束，那么则就返回true
3.代码
法一 哈希表：
//哈希表
class Solution {
public:
bool isUnique(string astr) {
int hash[26] = {0};
for (int i = 0; i < astr.size(); i++) {
hash[astr[i] - 'a']++;
if(hash[astr[i] - 'a']>1)
return false;
}
return true;
}
};法二 位图：
//位图
class Solution {
public:
bool isUnique(string astr) {
if (astr.size() > 26)
return false;
int biteMap = 0;
for (auto ch : astr) {
int i = ch - 'a';
if (((biteMap >> i) & 1) == 1)
return false;
biteMap = biteMap | (1 << i);
}
return true;
}
};
