目录
力扣 剑指 Offer 56 - I. 数组中数字出现的次数（寻找仅出现一次的2个数）
力扣 2917. 找出数组中的 K-or 值（且，或，左移）
一，一元运算
1，一元运算模板
//二进制运算，n>0
class Bits {
public:
//二进制最低位
static inline long long getLowBit(long long n) {
return n & (-n);
}
//二进制最高位
static inline long long getHighBit(long long n) {
while (n != getLowBit(n)) n ^= getLowBit(n);
return n;
}
//是否是2的幂
static inline bool isPowerOf2(long long n) {
return n == getLowBit(n);
}
//二进制总位数
static inline int getBitLength(long long n) {
int ans = 0;
while (n)
{
n >>= 1;
ans++;
}
return ans;
}
//二进制中1的个数
static inline int getNum1(long long n) {
int ans = 0;
while (n)
{
n ^= getLowBit(n);
ans++;
}
return ans;
}
//二进制中0的个数，只算最高位1后面的0
static inline int getNum0(long long n) {
return getBitLength(n) - getNum1(n);
}
//二进制反转，01互换，仅限最高位1后面的位
static inline long long getReverseNum(long long n) {
long long a = 1, len = getBitLength(n);
return (a << len) - 1 ^ n;
}
};力扣 1356. 根据数字二进制下 1 的数目排序
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
请你返回排序后的数组。
示例 1：
输入：arr = [0,1,2,3,4,5,6,7,8] 输出：[0,1,2,4,8,3,5,6,7] 解释：[0] 是唯一一个有 0 个 1 的数。 [1,2,4,8] 都有 1 个 1 。 [3,5,6] 有 2 个 1 。 [7] 有 3 个 1 。 按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
示例 2：
输入：arr = [1024,512,256,128,64,32,16,8,4,2,1] 输出：[1,2,4,8,16,32,64,128,256,512,1024] 解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。
示例 3：
输入：arr = [10000,10000] 输出：[10000,10000]
示例 4：
输入：arr = [2,3,5,7,11,13,17,19] 输出：[2,3,5,17,7,11,13,19]
示例 5：
输入：arr = [10,100,1000,10000] 输出：[10,100,10000,1000]
提示：
1 <= arr.length <= 5000 <= arr[i] <= 10^4
bool cmp(int a,int b){
int x=FgetNum1(a),y=FgetNum1(b);
return x==y?a<b:x<y;
}
class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
sort(arr.begin(),arr.end(),cmp);
return arr;
}
};力扣 2749. 得到整数零需要执行的最少操作数
给你两个整数：num1 和 num2 。
在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2i + num2 。
请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。
如果无法使 num1 等于 0 ，返回 -1 。
示例 1：
输入：num1 = 3, num2 = -2 输出：3 解释：可以执行下述步骤使 3 等于 0 ： - 选择 i = 2 ，并从 3 减去 22 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。 - 选择 i = 2 ，并从 1 减去 22 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。 - 选择 i = 0 ，并从 -1 减去 20 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。 可以证明 3 是需要执行的最少操作数。
示例 2：
输入：num1 = 5, num2 = 7 输出：-1 解释：可以证明，执行操作无法使 5 等于 0 。
提示：
1 <= num1 <= 109-109 <= num2 <= 109
class Solution {
public:
int makeTheIntegerZero(int x, int y) {
for (long long k = 1; k < 33; k++) {
long long x2 = x - k * y;
if (k <= x2 && FgetNum1(x2) <= k )return k;
}
return -1;
}
};力扣 2859. 计算 K 置位下标对应元素的和
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
请你用整数形式返回 nums 中的特定元素之 和 ，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。
整数的二进制表示中的 1 就是这个整数的 置位 。
例如，21 的二进制表示为 10101 ，其中有 3 个置位。
示例 1：
输入：nums = [5,10,1,5,2], k = 1 输出：13 解释：下标的二进制表示是： 0 = 0002 1 = 0012 2 = 0102 3 = 0112 4 = 1002 下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。 因此，答案为 nums[1] + nums[2] + nums[4] = 13 。
示例 2：
输入：nums = [4,3,2,1], k = 2 输出：1 解释：下标的二进制表示是： 0 = 002 1 = 012 2 = 102 3 = 112 只有下标 3 的二进制表示中存在 k = 2 个置位。 因此，答案为 nums[3] = 1 。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 1050 <= k <= 10
class Solution {
public:
int sumIndicesWithKSetBits(vector<int>& nums, int k) {
int ans=0;
for(int i=0;i<nums.size();i++){
if(FgetNum1(i)==k)ans+=nums[i];
}
return ans;
}
};2，左移右移
CSU 1318 Small change
题目：
Description
打完网赛，就到了晚饭的时间，但CSU_ACM的同学们都已经没力气出去了，这时CX建议大伙一起点餐吧，因为正是饭点，CX为了不让大家等太久，找了一个承诺20分钟送到超时要打折的外卖。但CX的RP都在网赛上用光了，果然送餐的迟到了，按规定咱们是要少给钱的。可是那些送餐员十分的狡猾，他们没有带零钱，于是乎，原价为N元的饭，由于他们的迟到可能需要降价，这些狡猾的送餐员会随机报一个数∈（1，N），如果CSU_ACM的小基友没有恰好这么多钱的话，送餐员还是按原价收取饭钱。为了CSU_ACM的最大利益，想知道最少由多少张钞票可以应对送餐员的任意要求(每张钞票的价值可为任意正整数)，不论送餐员报的数字为多少总能给出相应的零钱。
Input
多组数据(不超过20组)，输入到文件结束。
输入为CSU_ACM的小基友们点餐的总价N.(1<=N<=100000)
Output
输出为CSU_ACM的小基友们准备的零钱的最少张数。每个测试数据一行。
Sample Input
1
2
5
Sample Output
1
2
3
代码：
#include<iostream>
using namespace std;
int main()
{
int n, a;
while (cin >> n)
{
a = 1;
while ((1 << a) < n + 1)a++;
cout << a << endl;
}
return 0;
}CSU 1530 Gold Rush
题目：
Input
Output
Sample Input
3
2 2 2
2 1 3
10 1000 24
Sample Output
1
2
7
代码：
#include<iostream>
using namespace std;
int main()
{
int t, n;
long long a, b;
cin >> t;
while (t--)
{
cin >> n >> a >> b;
while (a % 2 == 0)n--, a /= 2;
cout << n << endl;
}
return 0;
}
力扣 190. 颠倒二进制位
题目：
颠倒给定的 32 位无符号整数的二进制位。
示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
进阶:
如果多次调用这个函数，你将如何优化你的算法？
代码：
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
for (int i = 0; i < 32; i++)
{
ans = ans * 2 + n % 2, n /= 2;
}
return ans;
}
};力扣 476. 数字的补数
对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。
- 例如，整数
5的二进制表示是"101"，取反后得到"010"，再转回十进制表示得到补数2。
给你一个整数 num ，输出它的补数。
示例 1：
输入：num = 5 输出：2 解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。
示例 2：
输入：num = 1 输出：0 解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。
提示：
1 <= num < 231
class Solution {
public:
int findComplement(int num) {
return Bits::getReverseNum(num);
}
};力扣 1009. 十进制整数的反码
每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。
二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。
给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。
示例 1：
输入：5 输出：2 解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。
示例 2：
输入：7 输出：0 解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。
示例 3：
输入：10 输出：5 解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。
提示：
0 <= N < 10^9
class Solution {
public:
int bitwiseComplement(int num) {
return num?Bits::getReverseNum(num):1;
}
};力扣 3064. 使用按位查询猜测数字 I
你需要找到一个数字 n。
这里有一个预定义的 API int commonSetBits(int num)，它返回 n 和 num 在二进制表示的同一位置上都是 1 的位数。换句话说，它返回 n & num 的
设置位
数量，其中 & 是按位 AND 运算符。
返回数字 n。
示例 1：
输入：n = 31 输出：31 解释：能够证明使用给定的 API 找到 31 是可能的。
示例 2：
输入：n = 33 输出：33 解释：能够证明使用给定的 API 找到 33 是可能的。
提示：
1 <= n <= 230 - 10 <= num <= 230 - 1- 如果你查询的
num超出了给定的范围，输出就不可靠。
class Solution {
public:
int findNumber() {
int x = 1, s = 0;
while (x != (1 << 30)) {
if (commonSetBits(x))s += x;
x <<= 1;
}
return s;
}
};二，二元运算
与运算、或运算是环非域，异或运算是域。
1，异或
CSU 1217 奇数个的那个数
Description
给定些数字，这些数中只有一个数出现了奇数次，找出这个数。
Input
每组数据第一行n表示数字个数，1 <= n <= 2 ^ 18 且 n % 2 == 1。
接下来n行每行一个32位有符号整数。
Output
出现奇数次那个数，每组数据对应一行。
Sample Input
5
1
1
2
2
3
7
1
2
1
2
2
3
3
Sample Output
3
2
事实证明，异或的计算往往与二进制有关。
本题就是用二进制解决的。
代码：
#include<stdio.h>
int main()
{
int n;
int m;
int r;
while(scanf("%d",&n)==1)
{
r=0;
while(n--)
{
scanf("%d",&m);
r^=m;
}
printf("%d\n",r);
}
return 0;
}
如果本题改成，有1个数出现了3k+1次，其他的数都出现了3的某个倍数次，要找这个数。
那么解法就是，把所有的数表示成三进制，然后把所有的数加起来，最后把每一位模3，即可得到结果。
把题目如此修改的创意，以及三进制的解法，来自我的朋友http://my.csdn.net/good_night_sion_
更一般的，如果是除了某个数之外，所有的数都出现了n的倍数次，那么用k进制就可以求解，其中k是不小于n的任何整数
力扣 1375. 二进制字符串前缀一致的次数
给你一个长度为 n 、下标从 1 开始的二进制字符串，所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位（即，将 0 变为 1）。
给你一个下标从 1 开始的整数数组 flips ，其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。
二进制字符串 前缀一致 需满足：在第 i 步之后，在 闭 区间 [1, i] 内的所有位都是 1 ，而其他位都是 0 。
返回二进制字符串在翻转过程中 前缀一致 的次数。
示例 1：
输入：flips = [3,2,4,1,5]
输出：2
解释：二进制字符串最开始是 "00000" 。
执行第 1 步：字符串变为 "00100" ，不属于前缀一致的情况。
执行第 2 步：字符串变为 "01100" ，不属于前缀一致的情况。
执行第 3 步：字符串变为 "01110" ，不属于前缀一致的情况。
执行第 4 步：字符串变为 "11110" ，属于前缀一致的情况。
执行第 5 步：字符串变为 "11111" ，属于前缀一致的情况。
在翻转过程中，前缀一致的次数为 2 ，所以返回 2 。
示例 2：
输入：flips = [4,1,2,3]
输出：1
解释：二进制字符串最开始是 "0000" 。
执行第 1 步：字符串变为 "0001" ，不属于前缀一致的情况。
执行第 2 步：字符串变为 "1001" ，不属于前缀一致的情况。
执行第 3 步：字符串变为 "1101" ，不属于前缀一致的情况。
执行第 4 步：字符串变为 "1111" ，属于前缀一致的情况。
在翻转过程中，前缀一致的次数为 1 ，所以返回 1 。
提示：
n == flips.length
1 <= n <= 5 * 104
flips 是范围 [1, n] 中所有整数构成的一个排列
class Solution {
public:
int numTimesAllBlue(vector<int>& flips) {
map<int, int>m;
int num = 0, ans = 0;
for (int i = 0; i < flips.size(); i++) {
if (flips[i] == i + 1) {
ans += (num == 0);
continue;
}
m[i + 1] ^= 1;
m[flips[i]] ^= 1;
if (m[i + 1])num++; else num--;
if(m[flips[i]])num++; else num--;
ans += (num == 0);
}
return ans;
}
};力扣 1177. 构建回文串检测
给你一个字符串 s，请你对 s 的子串进行检测。
每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。
如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。
返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。
注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。（另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）
示例：
输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出：[true,false,false,true,true]
解释：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。
queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。
queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。
提示：
1 <= s.length, queries.length <= 10^5
0 <= queries[i][0] <= queries[i][1] < s.length
0 <= queries[i][2] <= s.length
s 中只有小写英文字母
class Solution {
public:
vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
vector<int>vsum(s.length()+1);
vsum[0] = 0;
for (int i = 0; i < s.length(); i++) {
vsum[i + 1] = (1 << s[i] - 'a')^ vsum[i];
}
vector<bool>ans(queries.size());
for (int i = 0; i < ans.size(); i++) {
int dif = vsum[queries[i][1] + 1] ^ vsum[queries[i][0]];
int num = FgetNum1(dif);
ans[i] = num / 2 <= queries[i][2];
}
return ans;
}
};力扣 2425. 所有数对的异或和
给你两个下标从 0 开始的数组 nums1 和 nums2 ，两个数组都只包含非负整数。请你求出另外一个数组 nums3 ，包含 nums1 和 nums2 中 所有数对 的异或和（nums1 中每个整数都跟 nums2 中每个整数 恰好 匹配一次）。
请你返回 nums3 中所有整数的 异或和 。
示例 1：
输入：nums1 = [2,1,3], nums2 = [10,2,5,0] 输出：13 解释： 一个可能的 nums3 数组是 [8,0,7,2,11,3,4,1,9,1,6,3] 。 所有这些数字的异或和是 13 ，所以我们返回 13 。
示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：0 解释： 所有数对异或和的结果分别为 nums1[0] ^ nums2[0] ，nums1[0] ^ nums2[1] ，nums1[1] ^ nums2[0] 和 nums1[1] ^ nums2[1] 。 所以，一个可能的 nums3 数组是 [2,5,1,6] 。 2 ^ 5 ^ 1 ^ 6 = 0 ，所以我们返回 0 。
提示：
1 <= nums1.length, nums2.length <= 1050 <= nums1[i], nums2[j] <= 109
思路：利用异或和的交换性即可。
class Solution {
public:
int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
int ans=0;
if(nums1.size()%2)for(auto x:nums2)ans^=x;
if(nums2.size()%2)for(auto x:nums1)ans^=x;
return ans;
}
};力扣 剑指 Offer 56 - I. 数组中数字出现的次数（寻找仅出现一次的2个数）
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
2 <= nums.length <= 10000
int func(int x)
{
return x;
}
int xorr;
int func2(int x)
{
return (x&xorr)?x:0;
}
int xorSum(vector<int>v,int(*f)(int))
{
int ans=0;
for(int i=0;i<v.size();i++)ans^=f(v[i]);
return ans;
}
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int xo=xorSum(nums,func);
xorr=xo&-xo;
vector<int>ans(2);
ans[0]=xorSum(nums,func2);
ans[1]=ans[0]^xo;
return ans;
}
};力扣 面试题 05.06. 整数转换
整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
示例1:
输入：A = 29 （或者0b11101）, B = 15（或者0b01111） 输出：2
示例2:
输入：A = 1，B = 2 输出：2
提示:
- A，B范围在[-2147483648, 2147483647]之间
class Solution {
public:
int convertInteger(unsigned A, unsigned B) {
if(A==0&&B==0)return 0;
return convertInteger(A/2,B/2)+((A&1)^(B&1));
}
};2，异或else
3，与、或
CSU 2055 Wells‘s Lottery
题目：
Description
As is known to all, Wells is impoverished.
When God heard that, God decide to help the poor Wells from terrible condition.
One day Wells met God in dream, God gave Wells a secret number which will bought Wells a great fortune and gifted Wells an ablility of transforming two lottery tickets x, y into a lottery ticket z (meet the condition that z==x or y).
Wells realized that the number must be the result of lottery, which would be worth ¥5,000,000! Wells was very excited, and can't help sharing this thought. The secret number is X, and Wells has purchase N lottery tickets but has not received them yet. And if lucky enough, Wells could pick some numbers of them satisfy that , k is the amount of picked numbers.
How ever the owner of the lottery shop called SDJ, who decided to modify the lottery tickets and made Wells lost his fortune. In order to save energy to modify the lottery tickets, SDJ want to know the minimum amount of modification of lottery tickets.
Input
The input only contains one line.
First line contains two positive integers N ，X ，N means as described above Second line contains N number means the number on i-th lottery tickets.
Output
Output a line only contains minimum amount of modification of lottery tickets.
Sample Input
3 7
4 2 1
Sample Output
1
题意：
有n个数，问需要删掉多少个数才能使得剩下的数无论怎么选，都不能使得或运算的总结果为x
思路：
对于(a|x) != x来说，a是肯定不会被选的，所以不用管，
剩下的数，每一个对x的某些位都有贡献，
计算x的不为0的每一位，看哪一位的数最少，这个数量就是答案了。
代码：
#include<iostream>
using namespace std;
int main()
{
int n, x, a, num[32];
cin >> n >> x;
int ans = n;
for (int i = 0; i < 32; i++)num[i] = 0;
while (n--)
{
cin >> a;
if ((a|x) != x)continue;
for (int i = 0; i < 32; i++)num[i] += a % 2, a /= 2;
}
for (int i = 0; i < 32; i++)
{
if (x % 2 && ans>num[i])ans = num[i];
x /= 2;
}
cout << ans;
return 0;
}力扣 2568. 最小无法得到的或值
给你一个下标从 0 开始的整数数组 nums 。
如果存在一些整数满足 0 <= index1 < index2 < ... < indexk < nums.length ，得到 nums[index1] | nums[index2] | ... | nums[indexk] = x ，那么我们说 x 是 可表达的 。换言之，如果一个整数能由 nums 的某个子序列的或运算得到，那么它就是可表达的。
请你返回 nums 不可表达的 最小非零整数 。
示例 1：
输入：nums = [2,1] 输出：4 解释：1 和 2 已经在数组中，因为 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表达的。由于 4 是不可表达的，所以我们返回 4 。
示例 2：
输入：nums = [5,3,2] 输出：1 解释：1 是最小不可表达的数字。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109
思路：
显然答案一定是2的幂
class Solution {
public:
int minImpossibleOR(vector<int>& nums) {
map<int, int>m;
for (auto x : nums)m[x]++;
for (int i = 1;; i <<= 1) {
if (m[i] == 0)return i;
}
return 0;
}
};
力扣 2397. 被列覆盖的最多行数
给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect，表示你必须从 matrix 中选择的 不同 列的数量。
如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被 覆盖 了。
形式上，假设 s = {c1, c2, ...., cnumSelect} 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：
- 对于满足
matrix[row][col] == 1的每个单元格matrix[row][col]（0 <= col <= n - 1），col均存在于s中，或者 row中 不存在 值为1的单元格。
你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。
返回一个整数，表示可以由 numSelect 列构成的集合 覆盖 的 最大行数 。
示例 1：
输入：matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
输出：3
解释：
图示中显示了一种覆盖 3 行的可行办法。
选择 s = {0, 2} 。
- 第 0 行被覆盖，因为其中没有出现 1 。
- 第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。
- 第 2 行未被覆盖，因为 matrix[2][1] == 1 但是 1 未存在于 s 中。
- 第 3 行被覆盖，因为 matrix[2][2] == 1 且 2 存在于 s 中。
因此，可以覆盖 3 行。
另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。
示例 2：
输入：matrix = [[1],[0]], numSelect = 1 输出：2 解释： 选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。 所以我们返回 2 。
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 12matrix[i][j]要么是0要么是11 <= numSelect <= n
class Solution {
public:
int maximumRows(vector<vector<int>>& matrix, int numSelect) {
vector<int>v;
for(auto vi:matrix){
int s=0;
for(auto x:vi)s=(s<<1)+x;
v.push_back(s);
}
int ans=0;
for(int x=0;x<(1<<matrix[0].size());x++){
int a=x,s=0;
while(a)s+=a&1,a>>=1;
if(s!=numSelect)continue;
s=0;
for(auto vi:v)if((vi&x)==vi)s++;
ans=max(ans,s);
}
return ans;
}
};三，综合运用
力扣 191. 位1的个数（补码、位与、异或）
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
思路：
最简单的思路是除2，最搞效的是位运算
代码：
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while (n)
{
n ^= (n&(-n));
ans++;
}
return ans;
}
};力扣 2317. 操作后的最大异或和（异或，位与，位或）
给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择 任意 非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。
注意，AND 是逐位与运算，XOR 是逐位异或运算。
请你执行 任意次 更新操作，并返回 nums 中所有元素 最大 逐位异或和。
示例 1：
输入：nums = [3,2,4,6] 输出：7 解释：选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。 现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。 可知 7 是能得到的最大逐位异或和。 注意，其他操作可能也能得到逐位异或和 7 。
示例 2：
输入：nums = [1,2,3,9,2] 输出：11 解释：执行 0 次操作。 所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。 可知 11 是能得到的最大逐位异或和。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 108
class Solution {
public:
int maximumXOR(vector<int>& nums) {
int ans = 0;
for (auto x : nums)ans |= x;
return ans;
}
};力扣 371. 两整数之和（异或、左移）
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
示例 1：
输入：a = 1, b = 2 输出：3
示例 2：
输入：a = 2, b = 3 输出：5
提示：
-1000 <= a, b <= 1000
class Solution {
public:
int getSum(int a, int b) {
if(a<b)a^=b^=a^=b;
while (b) {
int c=1;
while (!(b & c))c <<= 1;
b^=c;
while (a & c)a ^= c, c <<= 1;
a ^= c;
}
return a;
}
};2802. 找出第 K 个幸运数字（位与、左移、右移）
我们知道 4 和 7 是 幸运 数字。同时，如果一个数字只包含幸运数字，那么它被称为幸运数字。
给定一个整数 k，返回第 k 个幸运数字，并将其表示为一个 字符串 。
示例 1：
输入：k = 4 输出："47" 解释：第一个幸运数字是 4，第二个是 7，第三个是 44，第四个是 47。
示例 2：
输入：k = 10 输出："477" 解释：按递增顺序列出的幸运数字为： 4, 7, 44, 47, 74, 77, 444, 447, 474, 477。 因此第10个幸运数字是477。
示例 3：
输入：k = 1000 输出："777747447" 解释：第 1000 个幸运数字是 777747447。
提示：
1 <= k <= 109
class Solution {
public:
string kthLuckyNumber(int k) {
int mi=2;
while(k>mi)k-=mi,mi<<=1;
mi>>=1;
k--;
string ans;
while(mi)ans+=k&mi?'7':'4',mi>>=1;
return ans;
}
};力扣 2917. 找出数组中的 K-or 值（且，或，左移）
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
nums 中的 K-or 是一个满足以下条件的非负整数：
- 只有在
nums中，至少存在k个元素的第i位值为 1 ，那么 K-or 中的第i位的值才是 1 。
返回 nums 的 K-or 值。
注意 ：对于整数 x ，如果 (2i AND x) == 2i ，则 x 中的第 i 位值为 1 ，其中 AND 为按位与运算符。
示例 1：
输入：nums = [7,12,9,8,9,15], k = 4 输出：9 解释：nums[0]、nums[2]、nums[4] 和 nums[5] 的第 0 位的值为 1 。 nums[0] 和 nums[5] 的第 1 位的值为 1 。 nums[0]、nums[1] 和 nums[5] 的第 2 位的值为 1 。 nums[1]、nums[2]、nums[3]、nums[4] 和 nums[5] 的第 3 位的值为 1 。 只有第 0 位和第 3 位满足数组中至少存在 k 个元素在对应位上的值为 1 。因此，答案为 2^0 + 2^3 = 9 。
示例 2：
输入：nums = [2,12,1,11,4,5], k = 6 输出：0 解释：因为 k == 6 == nums.length ，所以数组的 6-or 等于其中所有元素按位与运算的结果。因此，答案为 2 AND 12 AND 1 AND 11 AND 4 AND 5 = 0 。
示例 3：
输入：nums = [10,8,5,9,11,6,8], k = 1 输出：15 解释：因为 k == 1 ，数组的 1-or 等于其中所有元素按位或运算的结果。因此，答案为 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15 。
提示：
1 <= nums.length <= 500 <= nums[i] < 2311 <= k <= nums.length
class Solution {
public:
int findKOr(vector<int>& nums, int k) {
int mi=1,ans=0;
for(int i=0;i<31;i++){
int s=0;
for(auto x:nums)if(mi&x)s++;
if(s>=k)ans|=mi;
mi<<=1;
}
return ans;
}
};力扣 面试题 08.05. 递归乘法（且，左移，右移）
递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
示例1:
输入：A = 1, B = 10 输出：10
示例2:
输入：A = 3, B = 4 输出：12
提示:
- 保证乘法范围不会溢出
class Solution {
public:
int multiply(int A, int B) {
int x = 1, ans = 0;
while (B) {
if (B & 1)ans += A;
B >>= 1;
A <<= 1;
}
return ans;
}
};四，位运算相关的贡献法
五，状态压缩
状态压缩是一种编程技巧，或者说运算技巧。
传说高斯小时候做了一个题目1+2+3...+100，巧妙的用乘法快速算出来，惊呆了老师同学。这就是运算技巧，本质上不变，但是如果数学大厦中缺少运算技巧这个基础，简直难以想象。
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/113072863 状态压缩DP
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/122152703 自我指涉的选择题
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/132224953 点亮所有的灯
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/126005334
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/81571011
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/53045757
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/113136863
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/114178913
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/126653782
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/115913678
状态压缩 in https://blog.csdn.net/nameofcsdn/article/details/128625325
力扣 1542. 找出最长的超赞子字符串
给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需满足满足下述两个条件：
- 该字符串是
s的一个非空子字符串 - 进行任意次数的字符交换后，该字符串可以变成一个回文字符串
示例 1：
输入：s = "3242415" 输出：5 解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"
示例 2：
输入：s = "12345678" 输出：1
示例 3：
输入：s = "213123" 输出：6 解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"
示例 4：
输入：s = "00" 输出：2
提示：
1 <= s.length <= 10^5s仅由数字组成
class Solution {
public:
int longestAwesome(string s) {
map<int, int>m;
m[0] = 0;
vector<int>v(1, 0);
for (int i = 0; i < 10; i++)v.push_back(1 << i);
int sx = 0, ans = 0;
for (int i = 1; i <= s.length();i++) {
int x = s[i-1] - '0';
sx ^= (1 << x);
if (m.find(sx)==m.end())m[sx] = i;
for (auto x : v) {
if (m.find(sx ^x) != m.end())ans = max(ans, i-m[sx ^ x]);
}
}
return ans;
}
};力扣 3023. 在无限流中寻找模式 I
给定一个二进制数组 pattern 和一个类 InfiniteStream 的对象 stream 表示一个下标从 0 开始的二进制位无限流。
类 InfiniteStream 包含下列函数：
int next()：从流中读取 一个 二进制位 （是0或1）并返回。
返回 第一个使得模式匹配流中读取的二进制位的 开始下标。例如，如果模式是 [1, 0]，第一个匹配是流中的高亮部分 [0, 1, 0, 1, ...]。
示例 1：
输入: stream = [1,1,1,0,1,1,1,...], pattern = [0,1] 输出: 3 解释: 模式 [0,1] 的第一次出现在流中高亮 [1,1,1,0,1,...]，从下标 3 开始。
示例 2：
输入: stream = [0,0,0,0,...], pattern = [0] 输出: 0 解释: 模式 [0] 的第一次出现在流中高亮 [0,...]，从下标 0 开始。
示例 3：
输入: stream = [1,0,1,1,0,1,1,0,1,...], pattern = [1,1,0,1] 输出: 2 解释: 模式 [1,1,0,1] 的第一次出现在流中高亮 [1,0,1,1,0,1,...]，从下标 2 开始。
提示：
1 <= pattern.length <= 100pattern只包含0或1。stream只包含0或1。- 生成的输入使模式的开始下标在流的前
105个二进制位中。
/**
* Definition for an infinite stream.
* class InfiniteStream {
* public:
* InfiniteStream(vector<int> bits);
* int next();
* };
*/
class Solution {
public:
int findPattern(InfiniteStream* stream, vector<int>& pattern) {
int ans = 0;
if (pattern.size() == 1) {
while (stream->next() != pattern[0])ans++;
return ans;
}
int n = pattern.size() / 2, m = pattern.size() - n;
long long p1 = 0, p2 = 0, x1 = 0, x2 = 0;
for (int i = 0; i < n; i++)
{
p1 = (p1 << 1) | pattern[i];
x1 = (x1 << 1) | stream->next();
}
for (int i = n; i < m+n; i++)
{
p2 = (p2 << 1) | pattern[i];
x2 = (x2 << 1) | stream->next();
}
long long nn = (long long)(1) << n - 1;
long long mm = (long long)(1) << m - 1;
while (true)
{
if (p1 == x1 && p2 == x2)return ans;
ans++;
x1 = ((nn - 1 & x1) << 1) | (x2 >> m - 1);
x2 = ((mm - 1 & x2) << 1) | stream->next();
}
return 0;
}
};
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
