位运算
- 概念
- 库函数
  - bitset
    - 例子
  - 易错
- 公式
- 例题
  - 状态压缩

位运算¶

概念¶

运算¶

& 符号，x & y ，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。
| 符号，x | y ，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。
^ 符号，x ^ y ，会将两个十进制数在二进制下进行异或运算，然后返回其十进制下的值。
<< 符号，x << y 左移操作，将 x 在二进制下的每一位向左移动 y 位，最右边用 0 填充。 -等价于乘法
>> 符号，x >> y 右移操作，将 x 在二进制下的每一位向右移动 y 位，最左边用 0 填充（逻辑右移)，高位填充（算数右移）（对于正数是相同的）有符号类型使用算数右移，无符号类型使用逻辑右移。
- 对于正数等价于出发，但对于负数，右移是向下取整，而除法是向零取整。50>>2=13,50/4=12
~ 符号，~x ，按位取反操作，将 x 在二进制下的每一位取反，返回其十进制下的值。
__builtin_popcount()统计1的数目

进制¶

进制即进位计数制，是利用固定的数字符号和统一的规则的带进位的计数方法。任何一种进位计数制都有一个基数，基数为X的进位计数制称为X进制，表示每一个数位上的数运算时都是逢X进一。
对于一个X进制的数，其具体数值由其中的每个数码和数码所在的数位决定。整数部分从右往左的第m个数位表示的权重是\(X^m\)，其中m最小为0；小数部分从左往右的第n个数位表示的权重是\(X^{-n}\)，其中n最小为1。
将非十进制数转成十进制数，只要将每个数位的加权和即可。
将非十进制数转成十进制数，只要将每个数位的加权和即可。
- 对于整数部分，转换方式是将十进制数的整数部分每次除以X直到变成0，并记录每次的余数，反向遍历每次的余数即可得到X进制表示。
- 50->110010
- 对于小数部分，转换方式是将十进制数的小数部分每次乘以X直到变成0（小数部分为0）,并记录每次的整数部分，正序遍历每次的整数部分即可得到X进制表示。
- 0.6875->0.1011
其他进制的转化：如果需要在两个不同的非十进制之间转换，常规的思路是先转成十进制数，再转成目标进制数。在一些特殊情况下，也可以不经过十进制，直接进行转换。
- 比如二进制->八进制->十六进制可以直接对二进制数分组实现
- 如101110010按照3位分组101｜110｜010得到八进制562，4位分组1｜0111｜0010得到十六进制172

计算机中表示¶

一个字节表示8位二进制数
- 有符号整数中第一位表示符号，以一个字节整数为例，最高位是0时表示0～\(2^7\)-1,最高位为1时表示-\(2^7\)_{-1,即为-\(2^7\)}\(2^7\)-1
- 无符号整数为0~\(2^8\)-1
一个数在计算机中的二进制表示形式称为这个数的机器数，是有符号数。由于符号为的存在，机器数的值不一定是这个数真正的值如-10表示为10001010其形式值为138，而实际值为-10，10001010就是机器数，-10就是真值
原码：符号位加真值的绝对值
反码：0和正数的反码与原码相同，负数的原码是原码除了符号位以外的其他位取反
补码：负数的补码是在原码的基础上加一
- +10 的原码是00001010，反码是00001010，补码是00001010；
- −10 的原码是10001010，反码是11110101，补码是11110110。
补码解决了减法的为题，去除了+0和-0的重复可以多表示一位小数。（10000000不是-0而是-128）

库函数¶

__lg()和log2()都是计算对数，区别是前者是int后者float
__builtin_popcount()统计1的数目

bitset¶

bitset支持集合间的位运算（&|^~），比使用vector/set在内存和时间上都更为高效
初始化 ：
std::bitset<N> 创建一个包含 N 位的位集，初始值为 0。
也可以使用字符串或数字进行初始化。

std::bitset<8> b1; // 默认初始化为 00000000
std::bitset<8> b2(42); // 用数字初始化，00010101
std::bitset<8> b3("1100"); // 用字符串初始化，00001100

设置和重置位 ：
set() 方法将所有位设置为 1。
set(pos, value) 设置特定位置的位。
reset() 方法将所有位重置为 0。
reset(pos) 重置特定位置的位。
flip() 翻转所有位。
flip(pos) 翻转特定位置的位。

b1.set(); // 将所有位设置为 1
b1.reset(2); // 将位置 2 的位重置为 0
b1.flip(); // 翻转所有位

访问位和测试位 ：
使用 [] 运算符访问特定位。
test(pos) 检查特定位置的位是否为 1。

bool isSet = b1[3]; // 访问位置 3 的位
bool isOne = b1.test(3); // 检查位置 3 的位是否为 1

查询和操作 ：
count() 返回设置为 1 的位的数量。
size() 返回位集的大小。
all() 检查是否所有位都设置为 1。
any() 检查是否至少有一位设置为 1。
none() 检查是否没有位设置为 1。

std::size_t numOnes = b1.count(); // 计算设置为 1 的位数

转换：
to_ulong() 或 to_ullong() 将位集转换为无符号长整数。
to_string() 将位集转换为字符串。

unsigned long n = b2.to_ulong(); // 将位集转换为无符号长整数
std::string s = b3.to_string(); // 将位集转换为字符串

例子¶

CSP-LDAP
使用bitset维护集合并进行集合运算

```cpp #include using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=2505; int main(){ int n; cin>>n; unordered_map>,bitset\>>mp; vectoruser(n); for(int i=0;i>id; user[i]=id; int t; cin>>t; for(int j=0;j>a>>b; mp[a].first[b].set(i); mp[a].second.set(i); } } function(string&s,int,int)>parse; parse=&->bitset{ if(s[l]'|'||s[l]'&'){ stackst; st.push(1); int i=l+2; for(;i>m; for(int i=0;i>s; vectorres; auto res_b=parse(s,0,s.size()); for(int i=0;i<n;i++){ if(res_b.test(i)) res.push_back(user[i]); } sort(res.begin(),res.end()); for(int i=0;i<res.size();i++) cout<<res[i]<<" "; cout<<endl; } return 0; }

```

易错¶

公式¶

取反性质（与补码的性质有关）：-1=～0，-a=~(a-1),（-1为11111111）
a&(a-1)把最后一个1变为0
a&(-a)只保留最后一个1，其余变成0（记为lowbit）
c++ for(subset = (A - 1) & A; subset != A; subset = (subset - 1) & A) { ... }
枚举A的子集
对于有\(n\)个元素的集合，枚举所有子集，之后再枚举每一个子集的所有子集的时间复杂度为\(3^n\)（由二项式定理可以证明）

例题¶

405. 数字转换为十六进制数

371. 两整数之和

class Solution {
    public int getSum(int a, int b) {
        return a == 0 ? b : getSum((a&b) << 1, a^b);
    }//(a&b)<<1表示进位项，a^b表示非进位加法结果
};

201. 数字范围按位与
89. 格雷编码

342. 4的幂

return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
//即n>0，只有一位为1，1在偶数位置上。(aaaaaa->101010101010)

137. 只出现一次的数字 II
260. 只出现一次的数字 III
- 982. 按位与为零的三元组
- ```c++ int countTriplets(vector& nums) { unordered_mapcheck; for(int i=0;i<nums.size();i++)//先求两项 { for(int j=0;j<nums.size();j++) { check[nums[i]&nums[j]]++; } } int ans=0; for(int i=0;i<nums.size();i++) { for(auto &a:check) { if(!(nums[i]&a.first)) ans+=a.second; } } return ans; } //1 <= nums.length <= 1000 //0 <= nums[i] < 2^16
为什么先算两项再算一项比直接算三项要快：这是有数据决定的，两项一共会运算n²次（最大10⁶）而两两与运算约为2¹⁶(6*10⁵)并且通常还会更小，因此可以起到一定的优化
6289. 查询数组 Xor 美丽值

状态压缩¶

1542. 找出最长的超赞子字符串

class Solution {
public:
    int longestAwesome(string s) {
        int n = s.size();
        unordered_map<int, int> prefix = {{0, -1}};//最前面（0之前，即所有元素数目都为零）
        int ans = 0;
        int sequence = 0;//维护当前奇偶状态的压缩
        for (int j = 0; j < n; ++j) {
            int digit = s[j] - '0';
            sequence ^= (1 << digit);//更新
            if (prefix.count(sequence)) {
                ans = max(ans, j - prefix[sequence]);//两次出现相同状态（所有元素均有偶数个）
            } else {
                prefix[sequence] = j;//仅仅保留最早的，从而得到最大值
            }
            for (int k = 0; k < 10; ++k) {
                if (prefix.count(sequence ^ (1 << k))) {//有一个元素为奇数个
                    ans = max(ans, j - prefix[sequence ^ (1 << k)]);
                }
            }
        }
        return ans;
    }
};

1815. 得到新鲜甜甜圈的最多组数
复杂状态压缩