全文目录
☘前言☘
🎁主要知识点
位与运算
📓课后习题
397. 整数替换
1404. 将二进制表示减到 1 的步骤数
201. 数字范围按位与
面试题 05.01. 插入
982. 按位与为零的三元组
📑写在最后
☘前言☘
今天是算法零基础打卡的第43天，题目本身不难，主要是为了理解位运算的。上链接：
《算法零基础100讲》(第43讲) 位运算 (位与) 进阶
全文大约阅读时间： 20min
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
🎁主要知识点
位与运算
基本逻辑就是与或非，与操作就是两个同为1结果为1，否则为0，真值表如下
x y 结果(x&y)
1 1 1
0 1 0
1 0 0
0 0 0
int rangeBitwiseAnd(int left, int right){ unsigned int l = left, r = right; unsigned int len = r - l + 1; // 查看区间长度 unsigned int p2i; // 计算2的i次方 unsigned int ans = 0; int i; p2i = 1; for(i = 0; i < 31; ++i) { if(i) { p2i *= 2; } if(len > p2i) { // 长度大于2的i次方则不需要做计算一定为0 continue; } if( (left & p2i) && (right & p2i) ) { ans += p2i; // 两端点都是1 则所有均为1 所以加上这位的结果 } } return ans; }
📓课后习题
397. 整数替换
1397. 整数替换
给定一个正整数 n ，你可以做如下操作：
如果 n 是偶数，则用 n / 2替换 n 。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
n 变为 1 所需的最小替换次数是多少？
解题思路
这个基于贪心需要很强的数学推理，这个回头再补-.-
int integerReplacement(int n){ int ans = 0; while(n != 1){ if(n % 2 == 0) n /= 2;//奇数 else if(n % 4 == 1){ //对4的余数为1 n /= 2; ans++; } else{ //对4余数为3 if(n == 3) n = 1; else n = n/2 + 1; ans++; } ans++; } return ans; }
1404. 将二进制表示减到 1 的步骤数
1404. 将二进制表示减到 1 的步骤数
给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：
如果当前数字为偶数，则将其除以 2 。
如果当前数字为奇数，则将其加上 1 。
题目保证你总是可以按上述规则将测试用例变为 1 。
解题思路
突然让我觉得学有限自动机是有用的233
除2相当于消去最后一位
加1相当于找到前面第一个的为0的值 加1 后面全部变为0，注意如果前面全为1 那么就是第一位变成1 长度+1 并且最后一位也是0
int numSteps(char * s){ int len = strlen(s),ans= 0; while(len > 1){ if(s[len - 1] == '0') len--;//偶数就减少最后一位 else{ //处理+1 int temp = len - 1; while(temp && s[temp] == '1') s[temp--] = '0';//改变当前位 if(temp != 0) s[temp] = '1';//找到了为0的位 else{ //找不到 就长度增加 s[0] = '1'; s[len] = '0'; len++; } } ans ++; } return ans; }
201. 数字范围按位与
201. 数字范围按位与
给你两个整数 left和 right，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含left 、right 端点）。
解题思路
其实和大哥的思路是一样的，算就好了0.0；
int rangeBitwiseAnd(int left, int right){ unsigned int len = (unsigned int)right - (unsigned int )left + 1, p2i, sum = 0; for(int i = 0; i < 31; ++i){ p2i = (unsigned int )1 << i; if(len > p2i) continue; if((left & p2i) && (right & p2i)) sum += p2i; } return sum; }
面试题 05.01. 插入
面试题 05.01. 插入
给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。
编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。具体插入过程如图所示。
题目保证从 i 位到 j 位足以容纳 M， 例如： M = 10011，则 i～j 区域至少可容纳 5 位。
解题思路
先把相关位置清0，然后插入就好了。
int insertBits(int N, int M, int i, int j){ unsigned int k = 0; int m = i; while(i <= j) k += (unsigned int)1 << i++; N &= (~k); //取反 可以把对应位置全抹掉 while(M){ N |= ((unsigned int)(M&1)<<m++);//插入 M >>= 1; } return N; }
982. 按位与为零的三元组
982. 按位与为零的三元组
给定一个整数数组 A，找出索引为 (i, j, k) 的三元组，使得：
0 <= i < A.length
0 <= j < A.length
0 <= k < A.length
A[i] & A[j] & A[k] == 0，其中 & 表示按位与（AND）操作符。
解题思路
为了加速开一个hash表保存二元组
为了加速枚举所有的可能相与为0的元素
int countTriplets(int* nums, int numsSize){ int hash[1<<16],ans = 0; memset(hash,0,sizeof(hash)); for(int i = 0;i < numsSize;++i) for(int j = 0;j < numsSize;++j) ++hash[nums[i] & nums[j]];//插入二元hash表 for(int i = 0;i < numsSize;i++){ int full = (1 << 16) - 1 - nums[i]; for(int j = full ; j > 0; j = ((j-1)&full))//枚举所有可能元素 ans += hash[j]; ans += hash[0];//记录0元 } return ans; }
