首页 > 其他分享 >位运算基础

位运算基础

时间:2023-09-04 15:58:55浏览次数:40  
标签:return 运算 int 基础 取反 二进制 汉明

目录

位运算

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据,位运算是相当快的。

基本的位运算共 6 种,分别为:按位与、按位或、按位异或、按位取反、左移和右移。

与、或、异或

这三者都是两数间的运算,因此在这里一起讲解。

它们都是将两个整数作为二进制数,对二进制表示中的每一位逐一运算。

运算 运算符 数学符号表示 解释
\(\&\) \(\&\)、\(\operatorname{and}\) 只有两个对应位都为 1 时才为 1
| \(\mid\)、\(\operatorname{or}\) 只要两个对应位中有一个 1 时就为 1
异或 ^ \(\oplus\)、\(\operatorname{xor}\) 只有两个对应位不同时才为 1

注意,逻辑与(对应的数学符号为 \(\wedge\))和按位与、逻辑或(\(\vee\))和按位或的区别。

异或运算的逆运算是它本身,也就是说两次异或同一个数最后结果不变,即 \(a \oplus b \oplus b = a\) 。
举例:

\[\begin{aligned} 5 &=(101)_2\\ 6 &=(110)_2\\ 5\operatorname\&6 &=(100)_2 =\ 4\\ 5\operatorname|6 &=(111)_2 =\ 7\\ 5\oplus6 &=(011)_2 =\ 3\\ \end{aligned} \]

取反

取反是对一个数 \(num\) 进行的位运算,即单目运算。

取反暂无默认的数学符号表示,其对应的运算符为 ~。它的作用是把 \(num\) 的二进制补码中的 \(0\) 和 \(1\) 全部取反(\(0\) 变为 \(1\),\(1\) 变为 \(0\))。有符号整数的符号位在 ~ 运算中同样会取反。

补码:在二进制表示下,正数和 \(0\) 的补码为其本身,负数的补码是将其对应正数按位取反后加一。

举例(有符号整数):

\[\begin{aligned} 5&=(00000101)_2\\ \sim5&=(11111010)_2=-6\\ -5\text{的补码}&=(11111011)_2\\ \sim(-5)&=(00000100)_2=4 \end{aligned} \]

左移和右移

num << i 表示将 \(num\) 的二进制表示向左移动 \(i\) 位所得的值。

num >> i 表示将 \(num\) 的二进制表示向右移动 \(i\) 位所得的值。

举例:

\[\begin{aligned} 11&=(00001011)_2\\ 11<<3&=(01011000)_2=88\\ 11>>2&=(00000010)_2=2 \end{aligned} \]

移位运算中如果出现如下情况,则其行为未定义:

  • 右操作数(即移位数)为负值;

  • 右操作数大于等于左操作数的位数。

例如,对于 \(int\) 类型的变量 \(a\)、\(a<<-1\) 和 \(a<<32\) 都是未定义的。

对于左移操作,需要确保移位后的结果能被原数的类型容纳,否则行为也是未定义的。对一个负数执行左移操作也未定义。

对于右移操作,右侧多余的位将会被舍弃,而左侧较为复杂:

  • 对于无符号数,会在左侧补 \(0\)

  • 对于有符号数,则会用最高位的数(其实就是符号位,非负数为 \(0\),负数为 \(1\))补齐。

复合赋值位运算符

+=-= 等运算符类似,位运算也有复合赋值运算符: &= , |= , ^= , <<= , >>=

取反是单目运算,所以没有复合赋值运算符。

关于优先级

位运算的优先级低于算术运算符(除了取反),而按位与、按位或及异或低于比较运算符,所以使用时需多加注意,在必要时添加括号。

位运算的应用

位运算一般有三种作用:

  • 高效地进行某些运算,代替其它低效的方式;

  • 表示集合(常用于 状态压缩 DP);

  • 题目本来就要求进行位运算。

需要注意的是,用位运算代替其它运算方式(即第一种应用)在很多时候并不能带来太大的优化,反而会使代码变得复杂,使用时需要斟酌。

但像「乘 2 的非负整数次幂」和「除以 2 的非负整数次幂」就最好使用位运算,因为此时使用位运算可以优化复杂度。

有关 2 的幂的应用

由于位运算针对的是变量的二进制位,因此可以推广出许多与 2 的整数次幂有关的应用。

例如,将一个数乘(除) 2 的非负整数次幂:

  • 计算 \(n * 2^m\) 的代码实现:

    int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
      return n << m;
    }
    
  • 计算 \(n / 2^m\) 的代码实现:

    int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
      return n >> m;
    }
    

注意,我们平常写的除法是向 0 取整,而这里的右移是向下取整(注意这里的区别),即当数大于等于 0 时两种方法等价,当数小于 0 时会有区别,如: -1 / 2 的值为 0 ,而 -1 >> 1 的值为 -1 。

取绝对值

对整数 n 取绝对值的代码实现:

int abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
}

首先,n >> 31 可以取得 n 的符号:

  • 若 n 为正数,n >> 31 等于 0,此时,上述表达式等价于 n ^ 0 - 0 = n

    即正数的绝对值还是它本身;

  • 若 n 为负数,n >> 31 等于 -1,此时,上述表达式等价于 n ^ (-1) - (-1) = n

    其中,n ^ (-1) 需要计算 n 和 -1 的补码,然后进行异或运算,结果就是 n 变号并且为 n 的绝对值减 1,再减去 -1,就是其绝对值。

这种算法,在某些机器上,效率比 n > 0 ? n : -n 高。

取两个数的最大/最小值

在某些机器上,效率比 a > b ? a : b 高。

// 如果 a >= b, (a - b) >> 31 为 0,否则为 -1
int max(int a, int b) {
    return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31));
}

int min(int a, int b) {
    return (a & ((a - b) >> 31)) | (b & (~(a - b) >> 31));
}

判断两非零数符号是否相同

bool isSameSign(int x, int y) {  // 有 0 的情况例外
  return (x ^ y) >= 0;
}

交换两个数

该方法具有局限性:这种方式只能用来交换两个整数,使用范围有限。

对于一般情况下的交换操作,推荐直接调用 algorithm 库中的 std::swap 函数。

void swap(int &a, int &b) {
    a ^= b ^= a ^= b;
}

操作一个数的二进制位

  • 获取一个数二进制的某一位:

    // 获取 a 的第 b 位,最低位编号为 0
    int getBit(int a, int b) {
        return (a >> b) & 1;
    }
    
  • 将一个数二进制的某一位设置为 0:

    // 将 a 的第 b 位设置为 0 ,最低位编号为 0
    int unsetBit(int a, int b) {
        return a & ~(1 << b);
    }
    
  • 将一个数二进制的某一位设置为 1:

    // 将 a 的第 b 位设置为 1 ,最低位编号为 0
    int setBit(int a, int b) {
        return a | (1 << b);
    }
    
  • 将一个数二进制的某一位取反:

    // 将 a 的第 b 位取反 ,最低位编号为 0
    int flapBit(int a, int b) {
        return a ^ (1 << b);
    }
    

这些操作相当于将一个 32 位整型变量当作一个长度为 32 的布尔数组。

汉明权重

汉明权重 是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中,它是 1 的个数。

对于一个二进制数,它的汉明权重就等于它 1 的个数(即 popcount)。

位移实现

求一个数的汉明权重可以循环求解:我们不断地去掉这个数在二进制下的最后一位(即右移 1 位),维护一个答案变量,在除的过程中根据最低位是否为 1 更新答案。

代码如下:

// 求 x 的汉明权重
int popcount(int x) {
    int cnt = 0;
    while (x) {
        cnt += x & 1;
        x >>= 1;
    }
    return cnt;
}

LSB 置零操作

x & -x 实现

求一个数的汉明权重还可以使用 lowbit 操作:我们将这个数不断地减去它的 lowbit,直到这个数变为 0。

代码如下:

// 求 x 的汉明权重
int popcount(int x) {
    int cnt = 0;
    while (x) {
        cnt++;
        x -= x & -x;
    }
    return cnt;
}

n & (n - 1) 实现

减 1 操作将 n 最右边的符号从 0 变到 1,从 1 变到 0,与操作将会移除最右端的 1。如果最初 n 有 X 个 1,那么经过 X 次这样的迭代运算,n 将变为 0。

int popcount(int n) {
    int cnt = 0;
    for(;  n != 0; n = n & (n - 1)) {
        cnt++;
    }
    return cnt;
}

n & (n-1) 实现在大多数比特为 0 的情况下是效率最高的。

注意,上面的 x -= x & -x 操作与 n = n & (n - 1) 操作是等价的,都是将最低有效位(Least Significant Bit,LSB)置为零

构造汉明权重递增的排列

在状态压缩 DP 中,按照 popcount 递增的顺序枚举有时可以避免重复枚举状态。这是构造汉明权重递增的排列的一大作用。下面我们来具体探究如何在 \(O(n)\) 时间内构造汉明权重递增的排列。

我们知道,一个汉明权重为 n 的最小的整数为 \(2^n-1\)。只要可以在常数时间构造出一个整数汉明权重相等的后继,我们就可以通过枚举汉明权重,从 \(2^n-1\) 开始不断寻找下一个数的方式,在 \(O(n)\) 时间内构造出 \(0\sim n\) 的符合要求的排列。

而找出一个数 \(x\) 汉明权重相等的后继有这样的思路,以 \((10110)_2\) 为例:

  • 把 \((10110)_2\) 最右边的 1 向左移动一位,如果不能移动,将它左边的 1 向左移动,以此类推,得到 \((11010)_2\)。

  • 把得到的 \((11010)_2\) 最后移动的 1 原先的位置一直到最低位的所有 1 都移到最右边。这里最后移动的 1 原来在第三位,所以最后三位 010 要变成 001,得到 \((11001)_2\)。

这个过程可以用位运算优化:

int t = x + (x & -x);
x = t | ((((t &-t)/(x & -x)) >> 1) - 1);
  • 第一个步骤,我们把数 x 加上它的 lowbit,在二进制表示下,就相当于把 x 最右边的连续一段 1 换成它左边的一个 1。

    例如,当 \(x =(10110)_2\) 时,\(-x = (01010)_2\), 因此,\((x\ \& -x) = (10)_2\),所以 \(t = x + (x\ \& -x) = (11000)_2\)。

  • 第二个步骤,我们把答案后面的 1 补齐,\(t\) 的 lowbit 是 x 最右边连续一段 1 最左边的 1 移动后的位置,而 \(x\) 的 lowbit 则是 \(x\) 最右边连续一段 1 最左边的位置。

    此时,\(t = (11000)_2\),\(\operatorname{lowbit}(t) = (01000)_2\),\(\operatorname{lowbit}(x)=(00010)_2\)。

  • 接下来的除法操作是这种位运算中最难理解的部分,但也是最关键的部分。我们设原数最右边连续一段 1 最高位的 1 在第 \(r\) 位上(位数从 0 开始),最低位的 1 在第 l 位,\(t\) 的 lowbit 等于 \(1 << (r+1)\) ,x 的 lowbit 等于 \(1 << l\), \((((t\&-t)/(x\&-x))>>1)\) 得到的,就是 \((1<<(r+1))/(1<<l)/2 = (1<<r)/(1<<l) = 1<<(r-l)\) ,在二进制表示下就是 1 后面跟上 \(r-l\) 个零,零的个数正好等于连续 1 的个数减去 1 。

    以前面的例子为例,

    \[\frac{\operatorname{lowbit(t)/2}}{\operatorname{lowbit(x)}} = \frac{(00100)_2}{(00010)_2} = (00010)_2 \]

    把这个数减去 1 得到的就是我们要补全的低位,或上原来的数就可以得到答案。所以枚举 \(0\sim n\) 按汉明权重递增的排列的完整代码为:

for (int i = 0; (1<<i)-1 <= n; i++) {
    for (int x = (1<<i)-1, t; x <= n; t = x+(x&-x), x = x ? (t|((((t&-t)/(x&-x))>>1)-1)) : (n+1)) {
        // 写下需要完成的操作
    }
}

其中要注意 0 的特判,因为 0 没有相同汉明权重的后继。

参考:

标签:return,运算,int,基础,取反,二进制,汉明
From: https://www.cnblogs.com/larry1024/p/17676076.html

相关文章

  • SpringBoot--基础
    SpringBoot--基础SpringBoot的设计目的是用来简化Spring应用的初始搭建以及开发过程idea创建springboot入门步骤(需要idea联网)创建一个空项目之后再项目构建中添加springboot相关配置本处的springboot版本为2.7.14,如果maven报错可以自己修改一下版本,最新的3.0版本......
  • AUTOSAR基础篇之OS-00
    OS主要是为我们解决了以下几个基本问题:改变各任务的执行频率;改变各任务的执行时间;设定各任务的优先级,保证高优先级任务能够及时执行;任务切换时的现场保护与恢复;共享资源的安全访问机制等;  首先,AUTOSAROS是基于OSEKOS继承发展而来,所以上述的OSEKOS的基本......
  • Java语言基础知识全总结
    一.Java的优点1.      跨平台性。一次编译,到处运行。Java编译器会将Java代码编译成能在JVM上直接运行的字节码文件,C++会将源代码编译成可执行的二进制代码文件,所以C++执行速度快2.      纯面向对象。Java所有的代码都必须在类中书写。C++兼具面向对象和面向过程的特......
  • 分享一个Python字符串替换的基础题目(下篇)
    大家好,我是皮皮。一、前言上一篇文章,【瑜亮老师】和【凡人不烦人】引申了下字符串处理的题目,如下所示:扩展一下,下面的结果是什么:strs='abbacba'print(strs.lstrip('ab'))print(strs.rstrip('ab'))二、实现过程这里【FANG.J】还是有点东西的,全部都回答正确了。说明是完......
  • 微信小程序开发基础知识一
    小程序和普通前端网页开发的区别1、运行环境:微信小程序是在微信内部运行的,而普通前端网页是在浏览器中运行的。这意味着微信小程序必须依赖微信提供的运行时环境,而普通前端网页可以在不同的浏览器上运行。因此,微信小程序开发需要专门的开发工具和技术栈。2、开发语言:微信小程序主......
  • 面向对象基础知识
    面向对象思想与方法:面向对象思想是一种软件开发的思维方式,它将现实世界中的事物抽象成对象,并通过对象之间的交互来实现系统的功能。面向对象思想有以下几个核心概念:类(Class):类是对象的模板,描述了对象的属性和行为。例如,我们可以定义一个名为"Person"的类,用于表示人的属性(如姓名、年......
  • maven打包提示“-source1.5中不支持diamond运算符终极解决办法”
    把所有能设置Java的地方都改过来了,还是不行,最后在Maven的setting.xml中设置了一下Jdk好使了<profiles><profile><id>jdk1.8</id><activation><activeByDefault>true</activeByDefault><jdk......
  • 3、运算精度的选择(P106)
    1、fp16和fp32有什么区别?FP32(单精度浮点数)和FP16(半精度浮点数)是两种不同的浮点数表示方式,它们在精度和存储空间上有显著的区别。下面是它们的主要区别以及一个示例来说明这些区别:精度:FP32:单精度浮点数使用32位来表示一个数,其中包括1位符号位、8位指数位和23位尾数位。它具有......
  • networkX-01-基础
    创建一个图Graph是由一组节点和节点对(边)组成的。#创建一个没有节点和边的空图。importnetworkxasnxG=nx.Graph()01节点图G可由多种方式生成。NetWorkX中包含许多图形生成函数(graphgeneratorfunctions),用于读取和写入多种格式的图形。方式1:一次添加一个节点G.......
  • Windows与网络基础——虚拟机镜像相关
    1.虚拟机Windows10安装硬盘分区时,先新建分区,再格式化在启动此电脑——管理——本地用户和组 向下箭头代表为禁用开机状态快照占用内存大于关机状态快照2.虚拟机WindowsServer2016安装要桌面的话,需要选择桌面体验版Server版本的WINDOWS需要给管理员设置密码,且具备复杂性,......