C++ 算法篇 位运算_c++位运算-程序员宅基地

技术标签: C++基础算法  位运算  

 学习目标

 1. 理解与掌握 C++ 中的位运算。
 2. 灵活应用位运算优化程序。

任何信息在计算机中都是采用二进制表示的,数据在计算机中是以补码形式存储的,位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作,不需要转换成十进制,因此处理速度非常快,在信息学竞赛中往往可以优化理论时间复杂度的系数。同时,一个整数的各个二进制位互不影响,利用位运算的一些技巧可以帮助我们简化程序代码。

一、位运算符

C++ 提供了按位与(&)、按位或(| )、按位异或(^)、取反(~)、左移(<<)、右移(>>)这 6 种位运算符。  这些运算符只能用于整型操作数,即只能用于带符号或无符号的 char、short、int 与 long 类型。


 

(1)按位与运算符(&) 

 “a&b”是指将参加运算的两个整数a和b,按二进制位进行“与”运算。

运算规则:0&0=0;  0&1=0;   1&0=0;    1&1=1;      即:两位同时为“1”,结果才为“1”,否则为0
例如:3&5  即 0000 0011& 0000 0101 = 0000 0001  因此,3&5的值得1。
另,负数按补码形式参加按位与运算。

按位与&比较实用的例子:
1、比如我们经常要用的是否被2整除,一般都写成   if(n % 2 == 0) 可以换成 if((n&1) == 0) 
2、按位与运算可以取出一个数中指定位。例如:要取出整数84从左边算起的第3、4、5、7、8位,只要执行84 & 59,因为84对应的二进制为01010100,59对应的二进制为00111011,01010100 &  00111011=  00010000   可知84从左边算起的第3、4、5、7、8位分别是0、1、0、0、0。
 3、清零。如果想将一个单元清零,使其全部二进制位为0,只要与一个各位都为零的数值相与,结果为零。

按位与应用举例1:

整数幂:判断一个数n ,是不是2的整数幂。比如:64=2^6,所以输出“yes”,而65无法表示成2的整数幂的形式,所以输出“NO”。

#include<bits/stdc++.h>
using namespace std;
int main()
{  int n;
   cin>>n;
   if(n&(n-1))cout<<"NO";
   else cout<<"Yes";
}

按位与应用举例2:

计算一个数的二进制中1的个数:

算法1:通过与初始值为1的标志位进行与运算,判断最低位是否为1;然后将标志位左移,判断次低位是否为1;一直这样计算,直到将每一位都判断完毕。

#include<bits/stdc++.h>
using namespace std;
int main()
{  	int n = 0,num;
	unsigned int flag = 1;
	cin>>num;
 	while(flag)
	{	if(num & flag) n++;
		flag = flag << 1;
	}
	cout<<n;
}

算法2:还有一种方法,一个整数减一,可以得到该整数的最右边的1变为0,这个1右边的0变为1。对这个整数和整数减一进行与运算,将该整数的最右边的1变为0,其余位保持不变。直到该整数变为0,进行的与运算的次数即为整数中1的个数。

#include<bits/stdc++.h>
using namespace std;
int main()
{  	int n = 0,num;
	unsigned int flag = 1;
	cin>>num;
 	while(num)
	{	num = num & (num - 1);
		n++;
	}
	cout<<n;
}

 

(2)按位或运算符(|) 

参加运算的两个对象,按二进制位进行“或”运算。
运算规则:0|0=0;  0|1=1;  1|0=1;   1|1=1;
     即 :参加运算的两个对象只要有一个为1,其值为1。
例如:3|5 即 00000011 | 0000 0101 = 00000111  因此,3|5的值得7。 
另,负数按补码形式参加按位或运算。

 按位或 (|) 比较实用的例子
可以用一个unsigned int 来存储多个布尔值。比如一个文件有读权限,写权限,执行权限。看起来要记录3个布尔值。我们可以用一个unsigned int也可以完成任务。

一个数r来表示读权限,它只更改个位来记录读权限的布尔值         00000001  (表示有读权限)     00000000  (表示没有读权限)

一个数w表示写权限,它只用二进制的倒数第二位来记录布尔值    00000010 (表示有写权限)     00000000 (表示没有写权限)

一个数x表示执行权限,它只用倒数第三位来记录布尔值              00000100 (表示有执行权限)    00000000 (表示没有执行权限)

那么一个文件同时没有3种权限就是           ~r | ~ w | ~ x 即为 00000000,就是0
只有读的权限就是                                         r | ~w | ~x 即为 00000001,就是1
只有写的权限就是                                        ~r | w | ~x 即为 00000010,就是2
一个文件同时有3种权限就是                       r | w | x 即为 00000111,就是7

 

(3)按位异或运算符(^)

参加运算的两个数据,按二进制位进行“异或”运算。
运算规则:0 ^ 0=0;  0 ^ 1=1;  1^ 0=1;   1^1=0;
   即:参加运算的两个对象,如果两个相应位为“异”(值不同),则该位结果为1,否则为0。

下面重点说一下按位异或,异或  其实就是不进位加法,如1+1=0,,0+0=0,1+0=1。
异或的几条性质:
1、交换律:a ^ b=b ^ a
2、结合律:(a ^ b) ^ c == a^ (b ^ c)

“异或运算”的特殊作用:
(1)使特定位翻转:   例:X=10101110,使X低4位翻转,用X ^ 0000 1111 = 1010 0001即可得到。
(2)与0相异或,保留原值 ,10101110^ 00000000 = 1010 1110。
(3)对于任何数x都有――自反性:x^ x=0,x^ 0=x    例如:A^B ^ B = A
(4)交换二个数:a  =a ^ b;   b = b ^ a;  a = a ^ b;

按位异或应用举例1:

给出 n 个整数,n 为奇数,其中有且仅有一个数出现了奇数次,其余的数都出现了偶数次。用线性时间复杂度、常数空间复杂度找出出现了奇数次的那个数。
【输入样例】
9
3 3 7 2 4 2 5 5 4
【输出样例】
7

#include<bits/stdc++.h>
using namespace std;
int main()
{   int i,n,m,a;
    cin>>n;
    cin>>a;
    for(int i = 2; i <= n; i++) 
    {cin>>m; a^=m;   }
    cout<<a<<endl;
}

按位异或 应用举例2:

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现
一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空
间,能否设计一个算法实现?
解法一、显然已经有人提出了一个比较精彩的解法,将所有数加起来,减去1+2+...+1000的和。
这个算法已经足够完美了,相信出题者的标准答案也就是这个算法,唯一的问题是,如果数列过大,则可能会导致溢出。
解法二、异或就没有这个问题,并且性能更好。
将所有的数全部异或,得到的结果与1^2^3^...^1000的结果进行异或,得到的结果就是重复数。

#include<bits/stdc++.h>
using namespace std;
int main()
{  int i,n,a[11]={1,2,5,3,4,5,6,7,8,9,10};
   n=a[0]^a[1];
  for(i=2;i<=10;i++)n=n^a[i]; 
  for(i=1;i<=10;i++)n=n^i;
  cout<<n;
}

按位异或 应用举例3:

一系列数中,除两个数外其他数字都出现过两次,求这两个数字,并且按照从小到大的顺序输出.例如 2 2 1 1 3 4.最后输出的就是3 和4

#include<bits/stdc++.h>
using namespace std;
int a[1000];
int main()
{       int n;
        scanf("%d", &n);
        int x = 0;
        for(int i = 1; i <= n; i++) {      scanf("%d", &a[i]); x ^= a[i];    }
        int num1 = 0, num2 = 0;
        int tmp = 1;
        while(!(tmp & x)) tmp <<= 1;
        cout<<tmp<<endl;
        for(int i = 1; i <= n; i++) {
            if(tmp & a[i]) num1 ^= a[i];
            else num2 ^= a[i];
        }
        printf("%d %d\n", min(num1, num2), max(num1, num2));
    return 0;
}

 

(4)按位取反运算符(~)

按位取反运算符(~)是指将整数的各个二进制位都取反,即1变为0,0变为1。

例如,~9=-10,因为9(00001001)所有位取反即为(11110110),这个数最高位是1,所以是补码。补码还原成反码(反码等于补码减1)得到(11110101),再还原为原码(反码到原码最高位不变,其它各位取反)等于(10001010),     十进制为-10。

 

(5)按位左移运算符(<<)

左移运算符是用来将一个数的各二进制位左移若干位,移动的位数由右操作数指定(右操作数必须是非负值),其右边空出的位用0填补,高位左移溢出则舍弃该高位。

在高位没有1的情况下,左移1位相当于该数乘以2,左移2位相当于该数乘以2*2=4,15<<2=60,即乘了4。
但此结论只适用于该数左移时被溢出舍弃的高位中不包含1的情况。

例如:143<<2  结果为60   因为143转换为进制为10001111,左移2得00111100 ,结果为60。

 

(6)按位右移运算符(>>)

右移运算符是用来将一个数的各二进制位右移若干位,移动的位数由右操作数指定(右操作数必须是非负值),移到右端的低位被舍弃,对于无符号数,高位补0。对于有符号数,某些机器将对左边空出的部分用符号位填补(即“算术移位”),而另一些机器则对左边空出的部分用0填补(即“逻辑移位”)。
注意:对无符号数,右移时左边高位移入0;对于有符号的值,如果原来符号位为0(该数为正),则左边也是移入0。
如果符号位原来为1(即负数),则左边移入0还是1,要取决于所用的计算机系统。有的系统移入0,有的

系统移入1。移入0的称为“逻辑移位”,即简单移位;移入1的称为“算术移位”。 
例: a的值是八进制数113755: 
   a:1001011111101101 (用二进制形式表示)
   a>>1: 0100101111110110 (逻辑右移时)
   a>>1: 1100101111110110 (算术右移时)
   在有些系统中,a>>1得八进制数045766,而在另一些系统上可能得到的是145766。Turbo C和其他一些C

编译采用的是算术右移,即对有符号数右移时,如果符号位原来为1,左面移入高位的是1。
源代码:
#include <stdio.h>
main()
{ int a=0113755; printf("%d",a>>1);}

(7)位运算优先级

总的来说比较低,逻辑运算符和数学运算符出现在同一个表达式中,那么需要用括号来表达运算次序。

(8)复合赋值运算符

位运算符与赋值运算符结合,组成新的复合赋值运算符,它们是:

1、&=   例:a &=b       相当于a=a& b
2、|=   例:a |=b           相当于a=a |b
3、>>=  例:a >>=b    相当于a=a>> b
4、<<= 例:a<<=b      相当于a=a<< b
5、^=   例:a ^= b       相当  a=a ^b

运算规则:和前面讲的复合赋值运算符的运算规则相似。

(9)不同长度的数据进行位运算

如果两个不同长度的数据进行位运算时,系统会将二者按右端对齐,然后进行位运算。

以“与”运算为例说明如下:如果一个4个字节的数据与一个2个字节数据进行“与”运算,右端对齐后,左边不足的位依下面三种情况补足:

(1)如果整型数据为正数,左边补16个0。

(2)如果整型数据为负数,左边补16个1。

(3)如果整形数据为无符号数,左边也补16个0。

 

(10)下面列举一些常见的二进制位的变换操作

去掉最后一位 

101101->10110 x>>1
在最后加一个0 101101->1011010 x<<1
在最后加一个1  101101->1011011 (x<<1)+1
把最后一位变成1 101100->101101   x | 1
把最后一位变成0  101101->101100 (x |1) - 1
最后一位取反 101101->101100 x ^ 1
把右数第K位变成1 101001->101101,k=3 x  | (1<<(k-1))
把右数第K位变成0 101101->101101,k=3 x & ~(1<<(k-1))
右数第k位取反  101001->101101,k=3   x ^ (1<<(k-1))
取末三位 1101101->101  x &7
取末k位 1101101->1101,k=5   x & (1<<k-1)
取右数第k位 1101101->1,k=4 x >> (k-1)&1
把末k位变成1  101001->101111,k=4 x|(1<<k-1)
末k位取反  101001->100110,k=4   x^(1<<k-1)
把右边连续的1变成0   100101111->100100000  x&(x+1)
把右起第一个0变成1 100101111->100111111  x|(x+1)
把右边连续的0变成1 11011000->11011111 x|(x-1)
取右边连续的1 100101111->1111 (x^(x+1))>>1
去掉右起第一个1的左边  100101000->1000  x&(x^(x-1))

  

最后一个会在树状数组中用到

 

综合练习:

1、拔河比赛:

题目描述:

一个的学校要举行拔河比赛,为了在赛前锻炼大家,老师决定把班里所有人分为两拨,进行拔河因为为锻炼所以为了避免其中一方的实力过强老师决定以体重来划分队伍,尽量保持两个队伍的体重差最少。

输入格式:    第一行为人数(1<=n<=100),从第二行开始是每个人的体重m,

输出格式:    最小体重差。

输入样例:

3

100  90  200

输出样例:

10

数据范围:

60%的数据保证:(0<=n<=100)  (0<=m<=500)

100%的数据保证:(0<=n<=500)  (0<=m<=1000)

 

2、起床困难综合症:(洛谷)

题目描述:

21世纪,许多人得了一种奇怪的病:起床困难综合症,其临床表现为:起床难,起床后精神不佳。作为一名青春阳光好少年,atm一直坚持与起床困难综合症作斗争。通过研究相关文献,他找到了该病的发病原因: 在深邃的太平洋海底中,出现了一条名为drd的巨龙,它掌握着睡眠之精髓,能随意延长大家的睡眠时间。 正是由于drd的活动,起床困难综合症愈演愈烈, 以惊人的速度在世界上传播。为了彻底消灭这种病,atm决定前往海底,消灭这条恶龙。历经千辛万苦,atm终于来到了drd所在的地方,准备与其展开艰苦卓绝的战斗。drd有着十分特殊的技能,他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来,drd的防御战线由n扇防御门组成。每扇防御门包括一个运算op和一个参数t,其中运算一定是OR,XOR,AND中的一种,参数则一定为非负整数。如果还未通过防御门时攻击力为x,则其通过这扇防御门后攻击力将变为x op t。最终drd受到的伤害为对方初始攻击力x依次经过所有n扇防御门后转变得到的攻击力。

由于atm水平有限,他的初始攻击力只能为0到m之间的一个整数(即他的初始攻击力只能在 0, 1, … , m中任选,但在通过防御门之后的攻击力不受m的限制)。为了节省体力,他希望通过选择合适的初始攻击力使得他的攻击能让drd受到最大的伤害,请你帮他计算一下,他的一次攻击最多能使drd受到多少伤害。

输入格式:

输入文件的第 1 行包含 2 个整数,依次为n, m,表示 drd 有n扇防御门,atm 的初始攻击力为0到m之间的整数。

接下来n行,依次表示每一扇防御门。每行包括一个字符串op和一个非负整数t,两者由一个空格隔开,且op在前,t在后,op表示该防御门所对应的操作,t表示对应的参数。

输出格式:

输出一行一个整数,表示atm的一次攻击最多使drd受到多少伤害。

输入样例:

3 10
AND 5
OR 6
XOR 7

输出样例:

1

数据范围:

100%数据保证(0<=m,t<=10^9)

 

3、乒乓游戏:

一条大街上住着n个乒乓球爱好者,经常组织比赛切磋技术,每个人都有一个不同的技能值a(i)。每场比赛需要3个人:两名选手,一名裁判。他们有一个奇怪的规定,即裁判必须住在两名选手的中间,并且技能值也在两名选手之间。问一共能组织多少种比赛。
输入格式:

第一行    为数据组数T(1<=T<=20)每组数据占一行,首先是整数n(3<=n<=20000),

第二行    然后是n个不同的整数,即a(1),a(2)……a(n)(1<=a(i)<=100000),按照住所从左到右的顺序给出每个乒乓爱好者的技能值。
输出格式:

对于每组数据,输出比赛总数的值。

输入样例:

5

6 1 8 1 0 1

输出样例:

3
数据范围:

30%的数据保证:n<=3000

100%的数据保证:n<=3000



4、高低位交换

题目描述

给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示(不足32位用0补足)。我们称这个二进制数的前16位为“高位”,后16位为“低位”。将它的高低位交换,我们可以得到一个新的数。试问这个新的数是多少(用十进制表示)。

例如,数1314520用二进制表示为0000 0000 0001 0100 0000 1110 1101 1000(添加了11个前导0补足为32位),其中前16位为高位,即0000 0000 0001 0100;后16位为低位,即0000 1110 1101 1000。将它的高低位进行交换,我们得到了一个新的二进制数0000 1110 1101 1000 0000 0000 0001 0100。它即是十进制的249036820。

输入格式

一个小于2^32的正整数

输出格式

将新的数输出

输入输出样例

输入

1314520

输出 

249036820

 

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43736974/article/details/84543970

智能推荐

android 代码 截取屏幕,如何以编程方式在Android上截取屏幕截图?-程序员宅基地

文章浏览阅读346次。这是允许我的屏幕截图存储在SD卡上的代码,以后用于满足您的任何需求:首先,您需要添加适当的权限来保存文件:这是代码(在Activity中运行):privatevoidtakeScreenshot(){Datenow=newDate();android.text.format.DateFormat.format("yyyy-MM-dd_hh:mm:ss",now);try{//i..._屏幕部分截图android代码

注册表禁用计算机管理,Win7注册表编辑器被管理员禁用的解除方法-程序员宅基地

文章浏览阅读2.7k次。熟悉Win7系统的朋友都知道,注册表编辑器是更改Win7系统设置的好工具。在注册表中可以完成控制面板中不能修改的设置。但是有些用户打开注册表编辑器的时候却被提示,注册表编辑器已被管理员禁用,这是怎么回事呢?如何解除Win7对注册表编辑器的限制呢?一、Win7打开注册表的方法1 Win+R键打开Win7系统的运行,在运行数输入regedit点击确定。二、注册表被禁用解除方法Win7注册表编辑器被管理..._注册表编辑器禁用和解除原因

mysql innodb 源码_【InnoDB源码分析】Redo log-程序员宅基地

文章浏览阅读502次。【版本:mysql-8.0.12】1. Mini Transaction(mtr)InnoDB会将事务执行过程拆分为若干个Mini Transaction(mtr),每个mtr包含一系列如加锁,写数据,写redo,放锁等操作。举个例子:void btr_truncate(const dict_index_t *index) {... ...page_size_t page_size(space-&..._mysql innodb 源代码 解读

matlab背景设置_preferences: path: c:\users\administrator\appdata\-程序员宅基地

文章浏览阅读515次。打开C:\Users\Administrator\AppData\Roaming\MathWorks\MATLAB\R2015b\matlab.prf修改为#MATLAB Preferences#Sat Jul 11 15:54:49 CST 2020Editor.VariableHighlighting.Color=C-6931898EditorMRUSize=I8ReplaceSearchText19=SReplaceSearchText18=SReplaceSearchText17=S_preferences: path: c:\users\administrator\appdata\roaming\mathworks\matlab\c

谁说技术男不浪漫!90后程序员2天做出情绪...-程序员宅基地

文章浏览阅读75次。点击上方[全栈开发者社区]→右上角[...]→[设为星标]点击领取全栈资料:全栈资料9月1日,一则关于#程序员2天做出猫咪情绪识别软件#的话题登上微博热搜,参与阅读的人数达到了82..._程序员自研

解决SpringBoot整合redis下的键值序列化的问题_spring boot redis 查询序列化key-程序员宅基地

文章浏览阅读1.3k次。文章目录思考redis实现键值序列化自定义一个序列化转换器编写redis配置文件编写application.properties编写User类编写controller编写service测试思考为什么键值要序序列化呢?​ 不同平台之间的数据传输,深拷贝,浅拷贝,如果不采用序列化,很容易在传输过程中出现各种错误,无法正常使用Redis的序列化到底是什么?​ 简单的是说 就是 key ..._spring boot redis 查询序列化key

随便推点

JavaSE基础知识(十三)--Java的数组以及数组的初始化_int a1=a[rand.nextint(a.length)];-程序员宅基地

文章浏览阅读1.1k次。Java SE 是什么,包括哪些内容(十三)?本文内容参考自Java8标准数组是相同类型的,用一个标识符名称封装到一起的一个对象引用序列或基本数据类型序列,数组是通过方括号下标操作符[ ]来定义和使用的,要定义一个数组,只需要在类型后面加上一个[ ],并取一个合适的标识符名称即可。上面的内容总共体现在三个方面:⑴、数组内的数据类型必须是同一类型,也就是说在一个数组内不能同时存储不同数据类型..._int a1=a[rand.nextint(a.length)];

计算机专业2016高考录取分数线,华南师范大学计算机类专业2016年在广东理科高考录取最低分数线...-程序员宅基地

文章浏览阅读129次。类似问题答案华南师范大学计算机类专业2015年在广东理科高考录取最低分数线学校 地 区 专业 年份 批次 类型 分数 华南师范大学 广东 计算机类 2015 一批 理科 612 学校 地 区 专业 年份 批次 类型 分数 华南师范大学 广东 计算机类 2016 一批 理科 563 华南师范大学 广东 计算机类 2016 一批 理科 563 华南师范大学 广东 计算机类 2015 一批 理科 612..._华南师范大学广东2016各专业分数线

arm-linux-gnueabihf opencv,opencv3.4.9 + armv7 + arm-linux-gnueabihf交叉编译-程序员宅基地

文章浏览阅读249次。mac上编译 arm linux gnueabi交叉编译工具链toolchaincrosstool-ng 编译和安装 交叉编译工具下载: git clone [email protected]:secularbird/crosstool-ng.git 切换到mac编译分支 git ...Windows平台交叉编译Arm Linux平台的QT5&period;7库1.准备交叉编译环境 环境说..._gcc-arm-linux-gnueabihf armv7l

mysql数据库dao模式_mysql中DAO模式-程序员宅基地

文章浏览阅读591次。JDBC封装优点:隔离细节降低代码间耦合性提高代码可扩展性和维护性附注:DAO模式提供了访问关系型数据系统所需操作的接口,将数据访问和业务逻辑分开,对上层提供面向对象的数据访问接口.DAO模式实现两层分离:代码间分工明确,数据访问层代码不影响业务逻辑层代码,这也符合单一职能原则,降低了耦合度,提高了代码的可复用性。。隔离了不同的数据库的实现,采用面向接口编程,如果底层数据变化了,如mysql变成了..._mysqldao

Android对数据按照时间排序,Android实现数据按照时间排序-程序员宅基地

文章浏览阅读748次。经常遇见一个列表,两个接口的情况,两个接口属于两个不同的表数据,那么数据拼接回来之后,并不是按照时间排序的,看起来就相当混乱,所以记录一下如何对数据按照时间排序。步骤一:格式化日期public static Date stringToDate(String dateString) {ParsePosition position = new ParsePosition(0);SimpleDateFo..._安卓代码实现聊天记录根据时间排序

华硕固件默认ip,新路由3 newifi d2刷机刷华硕固件教程-程序员宅基地

文章浏览阅读4.9k次。新路由3默认的功能非常的少,所以不刷个好固件简直就是浪费硬件性能,恢复出厂后默认的路由器IP就是192.168.99.1。准备下面几个工具和固件上面工具准备好以后,下面开始刷机:一. 开启固件 SSH1、开启路由器,进入管理界面 (假设路由器 IP 地址是 192.168.99.1)2、 在浏览器中输入 http://192.168.99.1/newifi/ifiwen_hss.html 并进入3..._路由器刷华硕固件之后默认ip