c语言中位运算符_位运算符的用法

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

C语言的运算符是一个很有意思的东西,运用起来可以解决很多麻烦的事,但是想要灵活应用也有一定的难度,总结一下c语言运算符的用法和一些常用技巧.

一.C语言位运算符简介

C语言的位运算符有六种，分别是：

>>   右移运算符

<<   左移运算符

&   按位与运算符

|    按位或运算符

^    按位异或运算符

~    按位取反运算符

这些运算符都是对于基本数据类型的二进制位进行操作的，这里我们只讨论整型数据类型的位运算

二.各个运算符的具体使用

>> 右移运算符:将整数的二进制形式整体向右移动,移动过后左边缺的位的填充取决于编译器,可能是算术右移也可能是逻辑右移

<< 左移运算符:将整数的二进制形式整体向左移动,移动过后右边缺的位用0补全

逻辑右移:在位移的过程中,符号位左边可能移入新的位,移入的新位用0填充,则称为逻

辑移位

算术右移:在位移的过程中,符号位左边可能移入新的位,移入的新位由符号位决定,符号位为

1则移入的新位用1补充,符号位为0则用0补充,保持原数的正负不变,这样的移位

方式称为算术移位.

具体是逻辑右移还是算术右移取决于编译器(我使用的编译器为vs,为算术右移)

注意：没有逻辑左移和算术左移

例：

int a = 10;
int b = 20;
int c = -2;
int d = -25;
printf("%d\n",a>>1);
printf("%d\n",b<<2);
printf("%d\n",c<<2);
printf("%d\n",d>>3);
输出结果:
5
40
-8
-4

分析:

10       (28个0)1010

右移1位  0(28个0)101    =       5

在我刚刚接触位运算的时候我对d的位移结果很是不解

因为:

-25   二进制为  1(26个0)11001

位移后为         1111(26个0)11  结果怎么看都不是-4

实际上在计算机的位移运算中,正数和负数的运算都是使用补码的形式运算

正数的补码 = 正数的原码

负数的补码 = 负数的原码除符号位外按位取反 +　1;

负数的原码 = （负数的补码-1）再对除符号位之外按位取反

负数的存储实际上也是以负数的补码存储的

所以

-25  二进制为           1(26个0)11001

-25  在程序中为　　　   1(26个1)00111

位移后为                1111(26个1)00

再换为二进制原码形式   1(26个0)00100     为  -4

& 按位与运算符  对两个操作数的二进制每一位进行,1&1=1,1&0=0,0&1=0,0&0=0

|  按位或运算符  对两个操作数的二进制每一位进行,1|1=1,1|0=1,0|1=1,0|0=0

例子程序：

int a = -1;
int b = 2;
int c = 4;
printf("%d\n",b & c );
printf("%d\n", b | c );
printf("%d\n",a & b );
printf("%d\n", a | b );
输出:
0
6
2
-1

正数就不再分析了

负数还是按补码的形式

-1   补码   1(29个1)11

2    补码   0(29个0)10

进行按位或运算为   1(30个1)1    转换为负数原码刚好为-1

进行按位与运算为   0(29个0)10   为2

^    按位异或运算符  对两个操作数的二进制数每一位进行1^1=0，0^1=1，1^0=1；0^0=1

~    取反运算符      对操作数的二进制每一位进行,取反1->0,0->1

这两种运算符也是基于补码进行运算的

三.位运算符的具体应用

打印一个数的二进制形式
void printBit(int a)
{
	int i = 31;
	while( i >= 0 )
	{
		printf("%d",a>>i & 1);
		i--;
	}
	printf("\n");
}
不使用临时变量实现两个数值交换
void swap(int *a,int *b)
{
	*a = (*a)^(*b);
	*b = (*a)^(*b);
	*a = (*a)^(*b);
}
取出a中的第n位
int getBit(int a, int n)
{
	return  a>>n & 1;
}
将a中的第n位设为0
void setBitZero(int *a,int n)
{
	(*a) = (*a) & ~(1<<n);
}
将a中的第n位设为1
void setBitOne(int *a,int n)
{
	(*a) = (*a) | (1<<n);
}
求a的相反数
a = ~a+1;

四．一个运用位运算符的ACM题

找球号(一）

时间限制：3000 ms  | 内存限制：65535 KB

难度：3

描述

在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，现在说一个随机整数k(0<=k<=100000100)，判断编号为k的球是否在这堆球中（存在为“YES”,否则为“NO”），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。

输入

第一行有两个整数m，n(0<=n<=100000，0<=m<=1000000)；m表示这堆球里有m个球，n表示这个游戏进行n次。
接下来输入m+n个整数，前m个分别表示这m个球的编号i，后n个分别表示每次游戏中的随机整数k

输出

输出“YES”或“NO”

样例输入

样例输出

这道题并不是一个难题，解法很多，由于数据量比较大，所以在求解的时间限制上很多种方法会超时，这道题虽然我做出来的，但是在运行时间上落后太多的，我使用的是c++ stl 中的set实现，用时2700+ms，内存也用的不少，下面贴一个比较好的方法：

#define MAXN 3125010
int vis[MAXN] = {0} ;
int main()
{
	int m , n , x ;
	int i ;
	scanf("%d%d", &m , &n ) ;
	for( i = 0 ; i < m ; ++i )
	{
		scanf("%d", &x ) ;
		vis[ x / 32 ] |= 1 << x % 32 ;
	}
	for( i = 0 ; i < n ; ++i )
	{
		scanf("%d", &x ) ;
		if( vis[ x / 32 ] & ( 1 << x % 32 ) )
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0 ;
}

使用了c语言的位运算符，在数组的一个内存空间中存储32个数字是否存在的信息，这样既节省下来了内存空间，也使得查找数字时候时间复杂度为O(1)