• 位运算相关笔记


    位运算

    Part 1:基础

    1. 左移:左移一位,相当于某数乘以 2 2 2。左移 x x x 位,相当于该数乘以 2 x 2^x 2x

    2. 右移:右移一位,相当于某数除以 2 2 2。右移 x x x 位,相当于该数除以 2 x 2^x 2x

    3. 与运算:按位进行“与”运算,两数同一位都为 1 1 1 时结果为 1 1 1,否则为 0 0 0 0 0 0 与任何数都为 0 0 0

    4. 或运算:按位进行“或”运算,两数同一位都为 0 0 0 时结果为 0 0 0,否则为 1 1 1

    5. 非运算:按位取反

    Part 2:异或

    简介

    异或操作,是指两个数或者多个数之间进行的一种相同为 0 0 0、不同为 1 1 1 的位运算。

    异或操作通常用 ⊕ \oplus ^ 表示。

    运算律
    • 0 ⊕ n = n , n ⊕ n = 0 0\oplus n=n,n\oplus n=0 0n=n,nn=0

    • 结合律、交换律

    应用
    • 交换两个数:a=a^b,b=a^b,a=a^b;

    • 找到某个数

      一个数组中只有一个数出现了奇数次,其余数都出现了偶数次,如何找到这个出现奇数次的数?

      根据异或运算的性质,一个数与自己异或等于零,一个数与 0 0 0异或等于本身可知,只需将数组中的所有数进行异或操作即可将出现偶数次的数消掉,得到出现奇数次的。

    • i ⊕ 1 i\oplus 1 i1 表示 i i i 的反向边。

      证明:对于一个数 n n n,如果它是奇数,那么它异或 1 1 1 等于 n − 1 n-1 n1;如果它是偶数,那么它异或 1 1 1 等于 n + 1 n+1 n+1

      对于 Tarjan 求边双连通分量,有一段标记是 isb[i]=isb[i^1]=1(标记该边和它的反向边是桥 bridge),插入的时候是成对插入的( ( 0 , 1 ) 、 ( 1 , 2 ) 、 ⋯ 、 ( 2 k , 2 k + 1 ) (0,1)、(1,2)、\cdots、(2k,2k+1) (0,1)(1,2)(2k,2k+1))。

    Part 3:lowbit

    定义

    lowbit ( n ) \text{lowbit}(n) lowbit(n) 定义为非负整数 n n n 在二进制表示下“最低位的 1 1 1 及其后面的所有 0 0 0”构成的数值。

    举个栗子, n = 10 n=10 n=10 的二进制表示为 ( 1010 ) 2 (1010)_2 (1010)2,则 lowbit ( n ) = 2 = ( 10 ) 2 \text{lowbit}(n)=2=(10)_2 lowbit(n)=2=(10)2

    公式

    lowbit ( n ) = n & ( ∼ n + 1 ) = n & ( − n ) \text{lowbit}(n)=n\&(\sim n+1)=n\&(-n) lowbit(n)=n&(n+1)=n&(n)

    应用

    lowbit \text{lowbit} lowbit 运算配合 Hash,可以找出整数二进制表示下所有是 1 1 1 的位,时间复杂度与 1 1 1 的个数同级。

    实现:不断把 n n n 赋值为 n − lowbit ( n ) n-\text{lowbit}(n) nlowbit(n),直至 n = 0 n=0 n=0

    举个栗子: n = 9 = ( 1001 ) 2 n=9=(1001)_2 n=9=(1001)2 lowbit ( 9 ) = 1 \text{lowbit}(9)=1 lowbit(9)=1。把 n n n 赋值为 9 − lowbit ( n ) = 8 = ( 1000 ) 2 9-\text{lowbit}(n)=8=(1000)_2 9lowbit(n)=8=(1000)2 8 − lowbit ( 8 ) = 0 8-\text{lowbit}(8)=0 8lowbit(8)=0,停止循环。在这个过程中减掉了 1 1 1 8 8 8,即 n n n 每一位上的 1 1 1 后补 0 0 0 后的数值。取 log ⁡ 2 1 \log_21 log21 log ⁡ 2 8 \log_28 log28,就可以知道 n n n 的第 1 1 1 位和第 3 3 3 位是 1 1 1

    C++中的 log2 函数效率不够高,所以我们要预处理一个数组,用 Hash 代替 log ⁡ \log log 运算。

    n n n较小时,可以建立一个数组 h,令 h [ 2 k ] = k h[2^k]=k h[2k]=k

    const int maxn=1<<20;
    int h[maxn+5];
    for(int i=1;i<=20;i++) h[1<<i]=i;
    while(cin>>n)
    {
        while(n>0) cout<<h[n&-n]<<' ',n-=n&-n;
        cout<<endl;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    还有一种方法,建立一个长度为 37 37 37 的数组 h,令 h [ 2 k   m o d   37 ] = k h[2^k\bmod 37]=k h[2kmod37]=k ∀ k ∈ [ 0 , 35 ] \forall k\in[0,35] k[0,35] 2 k   m o d   37 2^k\bmod 37 2kmod37 互不相等,可以取遍 1 ∼ 36 1\sim36 136)。

    int h[37];
    for(int i=0;i<36;i++) h[(1ll<<i)%37]=i;
    while(cin>>n)
    {
        while(n>0) cout<<h[(n&-n)%37]<<' ',n-=n&-n;
        cout<<endl;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    lowbit 运算还可用于树状数组

    更多函数
    • int __builtin_ctz(unsigned int x)

      int __builtin_ctzll(unsigned long long x)

      返回 x x x 的二进制表示下最低位的 1 1 1 后边有多少个 0 0 0

    • int __builtin_popcount(unsigned int x)

      int __builtin_popcountll(unsigned long long x)

      返回 x x x 的二进制表示下有多少位为 1 1 1

    常见操作

    • 查询一个数二进制下的第 i i i 为是不是 1 1 1

      x>>i&1,如果第 i i i 位是 1 1 1 这个值是 1 1 1,否则是 0 0 0

      常见用途: 01 01 01 字典树线性基

    • 枚举子集

      常用于状压。

      for(int S1=S;S1;S1=(S1-1)&S) S2=S^S1;
      
      • 1

      其中 S S S 是全集, S 1 S_1 S1 是子集, S 2 S_2 S2 S 1 S_1 S1 的补集。

    • 改变 x x x 的第 i i i

      x|=1<<(i-1);//将x第i位变成1
      x&=~(1<<(i-1));//将x第i位变成0
      
      • 1
      • 2
    • 查询 1 1 1 的个数

      int popcount(int n)
      {
          int cnt=0;
          while(n) n&=(n-1),cnt++;
          return cnt;
      }
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
  • 相关阅读:
    C语言天花板——指针(进阶1)
    K_A07_002 基于 STM32等单片机驱动ULN2003模块按键控制步进电机正反转
    ElasticSearch 爬坑记录
    elementUI中form表单校验异常,开始就处罚了
    MySQL 三大日志(bin log、redo log、undo log)
    Spring AOP 实现方式与应用
    Redis学习记录------Redis6概述和安装(二)
    uniapp 设置重写uni-body-page样式,输入字母转大写
    一文带你弄懂 JVM 三色标记算法
    1236288-25-7,DSPE-PEG-FA,Folic acid PEG DSPE,磷脂-聚乙二醇-叶酸脂质体形成材料
  • 原文地址:https://blog.csdn.net/ncwzdlsd/article/details/133957633