☘前言☘
今天是算法零基础打卡的第44天，题目本身不难，主要是为了理解位运算的。上链接：
《算法零基础100讲》(第44讲) 位运算 (位或) 入门
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
🎁主要知识点
位或运算
位或的应用
设置标记位
置空标记位
📓课后习题
1356. 根据数字二进制下 1 的数目排序
231. 2 的幂
2044. 统计按位或能得到最大值的子集数目
📑写在最后
🎁主要知识点
位或运算
位或运算是计算机内的一个二元运算符，表示为x | y，其真值表如下(可以理解为并联的开关0.0)
x y x | y
0 0 0
1 0 1
0 1 1
1 1 1
位或的应用
设置标记位
给定一个数字 将其第五位标记为1。(0b表示二进制数0.0)
printf("%d\n", x | 0b10000);
置空标记位
结合上面的标记为的方法，我们先把这位变成1 然后再减去就好了。
printf("%d\n", (x | a) - a );
📓课后习题
1356. 根据数字二进制下 1 的数目排序
1356. 根据数字二进制下 1 的数目排序
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
解题思路
感觉这道题还是与运算方便些。
int cmp(int *a,int *b){ int lena = 0,lenb = 0; for(int i = 0; i < 32;i++){//统计1 个数 if((*a)>>i&1) lena++; if((*b)>>i&1) lenb++; } if(lena == lenb) return *a > *b; //相同按大小排 return lena > lenb; //不同1多在后面 } int* sortByBits(int* arr, int arrSize, int* returnSize){ qsort(arr,arrSize,sizeof(int),cmp); *returnSize = arrSize; return arr; }
231. 2 的幂
231. 2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
解题思路
感觉这道题也还是与运算方便些。2333
一行代码解决 仔细看看
bool isPowerOfTwo(int n){ return n <=0 ? false : !(n &(n-1)); }
2044. 统计按位或能得到最大值的子集数目
2044. 统计按位或能得到最大值的子集数目
给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。
如果数组 a可以由数组b 删除一些元素（或不删除）得到，则认为数组 a是数组b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。
对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR … OR a[a.length - 1]（下标从 0 开始）。
解题思路1
我总觉得暴力过不了 ，但是还是试了试。
我们应该明白越多数按位或结果会越来越大，所以最大值一定是数组内的所有值位或
表示子集的方式可以用二进制来表示 二进制的0和1表示对应元素有还是没有，遍历所有子数组就是从1 到
2numsSize−1
来进行表示的
int countMaxOrSubsets(int* nums, int numsSize){ int temp = 0,ans = 0; for(int i = 0;i < numsSize;i++) //找出最大值 temp |= nums[i]; for(int i = 0;i < 1 << numsSize;i++){//遍历所有子集 int tempans = 0; for(int j = 0; j < numsSize;j++){ if(i & (1 << j)) tempans |= nums[j]; } if(tempans == temp) ans++; } return ans; }
结果1
能过，对，没错 仅仅是能过-.-109ms 可怕0.0
解题思路2
上面的方法有个很大的问题就是造成了很大的重复计算，比如计算{1,2,3,4} 和{1,2,3}这两个子集的时候。第一个的结果就是第二个的结果再与4或就好了？
我们能思考的就是空间换时间，将所有子集的或的结果保存下来。然后计算新子集的时候运用之前的结果。
初始条件是将所有元素插入到的对应的位置。
然后我们知道i和-i的特点从低到高的第一个1之前的元素是完全相同的，我们可以利用这个特性来判断是否是只有一个元素，用于跳过
3.当不是只有一个元素的时候 我们可以用低位的结果和高位的结果相与来得到最终的结果。高位的元素一定比当前的元素小所以也进行过了计算。
int countMaxOrSubsets(int* nums, int numsSize){ int temp = 0,ans = 0,n = 1 <<numsSize; int hash[1 << numsSize]; for(int i = 0;i < numsSize;++i) hash[1<<i] = nums[i];//插入位置元素 for(int i = 1;i < n;++i){ int lowBit = i & (-i); if((i ^ lowBit) == 0) continue;//只有一个元素已经插入 hash[i] = hash[i ^ lowBit] | hash[lowBit];//状态转移方程 } for(int i = 0;i < n;i++) if(hash[i] == hash[n -1]) ans++;//统计 return ans; }
结果2
8ms0.0 哇 太强了
