【算法专题】位运算

位运算

位运算的基本操作

typedef struct Bitset {
    int setsize; // 16 32 ... int 是32位的
    int arraysize;  // 相当于有几行
    unsigned short *v; // 之后会分配一片连续的空间
}Bitset; //还非要大写才行 ..

// SetInit(size) 集合大小
Bitset SetInit(int size) {
    Bitset s;
    s.setsize = size;
    s.arraysize = (size + 15) >> 4; // 右移4位 除以16
    //我之前好像智障了 sizeof后面的是不需要看的 肯定是要带上的 所以这行就是相当于 创建一个sizes长度的v 类型是unsigned short型
    s.v = (unsigned short*) malloc( size * sizeof(unsigned short));
    for (int i = 0; i < size; i++) {
        s.v[i] = 0; // 初始化
    }
    return s;
}

// SetAssign(A, B) 将集合B 复制 到集合A
void SetAssign(Bitset A, Bitset B) {
    if(A.setsize!=B.setsize) exit(-1);
    for(int i = 0; i < A.arraysize; i++) A.v[i] = B.v[i]; //定义是按照n定，赋值是按照层d赋值
}

// SetMember(x, A) 判断是否是相同类型
/*
 首先明确一点 就是集合A的元素{1,3,5} 它代表的是 第1、3、5位的数字为1 也就是 101010
 而元素x ： 若 x=2 则表示判断 第x位是否为1。 现在假设传入的x=28 说明我要找的是第28位的数字
 x >> 4 = 1 说明我应该去v[1]找
 x & 15 = 12 相当于mod 16 = 12 ， 再将 1 右移 12位 ，就是相当于 把v中第13个数 和 1 相与
 */
int findIndex(int x) {
    return x >> 4; // 找下标
}

int bitIndex(int x) {
    return 1 << (x & 15);
}

int SetMember(int x, Bitset A)
{
    if (x<0 || x > A.setsize) exit(-1);
    return A.v[findIndex(x)] & bitIndex(x);
}

// SetEqual(A, B) 两集合是否相等
int SetEqual(Bitset A, Bitset B) {
    if(A.setsize!=B.setsize) exit(-1);
    for(int i = 0; i < A.arraysize; i++) {
        if(A.v[i]!=B.v[i])
            return 0;
    }
    return 1;
}

// SetUnion(A, B) U 并集合
Bitset SetUnion(Bitset A, Bitset B) {
    Bitset C = SetInit(A.setsize);
    if(A.setsize!=B.setsize) exit(-1);
    for(int i = 0; i < A.arraysize; i++) {
        C.v[i] = A.v[i] | B.v[i];
    }
    return C;
}

// SetInterSection(A, B) 交集  ->  C.v[i] = A.v[i] | B.v[i];
// SetDifference(A, B) 差集 属于A而不属于B的
Bitset setDifference(Bitset A, Bitset B) {
    Bitset C = SetInit(A.setsize);
    if(A.setsize!=B.setsize) exit(-1);
    for(int i = 0; i < A.arraysize; i++) {
        C.v[i] = A.v[i] ^ (A.v[i] & B.v[i]); // 这步骤就是把，A B都有的元素取出，再异或一下，不同取1，就可以拿出差集了。
    }
    return C;
}

// SetInsert(x, S) 在x位插入元素
Bitset SetInsert(int x, Bitset S) {
    if(x<0 || x > S.setsize) exit(-1);
    S.v[findIndex(x)] |= bitIndex(x);// 妈耶 我怎么会把它想那么复杂呢
    return S;
}

// SetDelete(x,S) 在x位删除元素
Bitset SetDelete(int x, Bitset S) {
    if(x<0 || x > S.setsize) exit(-1);
    S.v[findIndex(x)] &= ~bitIndex(x); // x位为0，其余都是1，&上之后，可以成功删除
    return S;
}

---

一般操作

// 求n的第k位数字: 
n >> k & 1
//返回n的最后一位1：
lowbit(n) = n & -n

逆转二进制数

int rever(int num) {
    int m_1  = 0x55555555; // 0101 8对
    int m_2  = 0x33333333;  // 0011 8对
    int m_4  = 0x0f0f0f0f; // 00001111 4对
    int m_8  = 0x00ff00ff;
    int m_16 = 0x0000ffff;
    
    int b = ((num & m_16) << 16) + ((num >> 16) & m_16); // 右挪左，左侧右移16位
    int c = ((b & m_8) << 8) + ((b >> 8) & m_8);
    int d = ((c & m_4) << 4) + ((c >> 4) & m_4);
    int e = ((d & m_2) << 2) + ((d >> 2) & m_2);
    int f = ((e & m_1) << 1) + ((e >> 1) & m_1);
    return f;
}
int main() {
    int a = 67;
    int b = rever(a);
    int c = rever(b);
    printf("%d %d", a, c);
    return 0;
}

---

leetcode.762 二进制表示中质数个计算置位

题目：给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）

int countPrimeSetBits(int L, int R) {
  int res = 0;
  unordered_set<int> primes({2, 3, 5, 7, 11, 13, 17, 19});
  for (int i = L; i <= R; i ++ )
  {
    int s = 0;
    for (int j = i; j; j >>= 1) s += j & 1;
    if (primes.count(s)) res ++;
  }
  return res;
}

leetcode.231 2的整次幂

题目：给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

bool isPowerOfTwo(int n) {
  return n > 0 && ( n & -n ) == n;
}

leetcode.136 只出现一次的数字

题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

// 输入 [1,2,3,1,2,3,4]
int singleNumber(vector<int>& nums) {
  int res = 0;
  for(auto x : nums) res ^= x;
  return res;
}

leetcode.136 只出现一次的数字II

题目：除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
题解：统计每一列1的个数，是3的倍数，表明 贡献了该位的数字是3的整数； 反之，如果一个数字只出现了一次，那么其贡献过的相应位置的1的总个数绝对不可能是三的倍数。最后将该列模3得到1后，右移相应位，可以转变成2进制上的相应位置为1。

int singleNumber(vector<int>& nums) {
  int bit = 32, res = 0, count; // int型为32位整数
  for(int i = 0; i < bit; i ++) {
    count = 0;
    for(int j = 0; j < nums.size(); j ++) {
      count += ( nums[j] >> i ) & 1; // 上一次的移位本次是不会记录的 因此 每次都是移动i位
      /* 我之前是count+=(nums[j]&1);
      	 nums[j] >> 1; 这样显示是不行的。nums[j]的移动不可能保存到下一轮。所以是用i记录遍历到的位数
      	 真的是太牛逼了- -。
      */
    }
    if(count % 3 == 1) res += (1 << i);
  }
  return res;
}

leetcode.476 数字的补数

题目：给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

int findComplement(int num) {
  int res = 0, bit = 0;
  while(num) {
    res += (!(num & 1) << bit);
    num >>= 1;
    bit++;
  }
  return res;
}

知识点和代码均学习于Acwing: https://www.acwing.com/activity/