C语言位运算总结-创新互联

目录

目录

在桑植等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供网站建设、成都网站设计 网站设计制作按需开发,公司网站建设,企业网站建设,成都品牌网站建设,成都全网营销,成都外贸网站制作,桑植网站建设费用合理。

一、引言

二、位逻辑运算和移位运算

1、按位与(&)

2、按位或(|)

3、按位异或(^)

4、取反(~)

5、左移操作(<<)

6、右移操作(>>)

三、常识与技巧

1、判断某一位是0还是1

2、任意数与0异或保持不变

3、任意数与本身异或为0

四、数据结构练习题

1、消失的数字

2、数组中数字出现的次数


一、引言

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说白了,就是直接对整数在内存中的二进制位进行操作。运位算包括位逻辑运算和移位运算,位逻辑运算能够方便地设置或屏蔽内存中某个字节的一个二进制位或几个二进制位,也可以对两个数按位相加等;移位运算可以对内存中某个二进制数左移或右移几位等。需要注意的一点是计算机中的数值是以补码的形式存储的。。。

二、位逻辑运算和移位运算 1、按位与(&)

运算规则:参加运算的两个数,如果两个数相应位的值都是1,则该位的结果值为1,否则为0。即:0 & 0 =0;0 & 1 =0;1 & 0 =0;1 & 1 =1。

# includeint main(){

	int a = 11;
	//二进制表示:0000 0000 0000 0000 0000 0000 0000 1011
	int b = 21;
	//二进制表示:0000 0000 0000 0000 0000 0000 0001 0101

	//a&b:       0000 0000 0000 0000 0000 0000 0000 0001
	printf("%d\n",a&b);
	return 0;
}

输出结果:

1
请按任意键继续. . .
2、按位或(|)

运算规则:参加运算的两个数,如果两个数相应位的值至少有一个为1,则该位的结果值为1,否则为0。即:0 | 0 =0;0 | 1 =1;1 | 0 =1;1 | 1 =1。

# includeint main(){

	int a = 11;
	//二进制表示:0000 0000 0000 0000 0000 0000 0000 1011
	int b = 21;
	//二进制表示:0000 0000 0000 0000 0000 0000 0001 0101

	//a|b:        0000 0000 0000 0000 0000 0000 0001 1111
	printf("%d\n",a|b);
	return 0;
}

代码结果:

31
请按任意键继续. . .
3、按位异或(^)

运算规则:参加运算的两个数,如果两个数相应位的值不同,则该位的结果值为1,否则为0。即:0 | 0 =0;0 | 1 =1;1 | 0 =1;1 | 1 =0。

# includeint main(){

	int a = 11;
	//二进制表示:0000 0000 0000 0000 0000 0000 0000 1011
	int b = 21;
	//二进制表示:0000 0000 0000 0000 0000 0000 0001 0101

	//a^b:        0000 0000 0000 0000 0000 0000 0001 1110
	printf("%d\n",a^b);
	return 0;
}

代码结果:

30
请按任意键继续. . .
4、取反(~)

运算规则:参加运算数,如果该数相应位为0,则该位的结果值为1,如果该数相应位为1,则该位的结果值为0。即:~ 0 =1;~ 1 =0。

# includeint main(){

	int a = 11;
	//二进制表示(补码):0000 0000 0000 0000 0000 0000 0000 1011

	//~a(补码):         1 111 1111 1111 1111 1111 1111 1111 0100
	//~a(反码=补码-1):  1 111 1111 1111 1111 1111 1111 1111 0011
	//~a(源码 = 反码符号位不变其他位取反):         
	//                    1 000 0000 0000 0000 0000 0000 0000 1100  = -12

	printf("%d\n",~a);
	return 0;
}

代码结果

-12
请按任意键继续. . .
5、左移操作(<<)

运算规则:对运算符<<左边的运算量的每一位全部左移右边运算量表示的位数,右边空出的位补0。左移一位变为原来二倍。

# includeint main(){

	int a = 11;
	//二进制表示(补码):0000 0000 0000 0000 0000 0000 0000 1011
	//a<<1:               0000 0000 0000 0000 0000 0000 0001 0110
	int b = -11;
	//原码:              1000 0000 0000 0000 0000 0000 0000 1011
	//反码:               1111 1111 1111 1111 1111 1111 1111 0100
	//补码:              1111 1111 1111 1111 1111 1111 1111 0101
	//b<<1的补码          1111 1111 1111 1111 1111 1111 1110 1010
	//b<<1的反码          1111 1111 1111 1111 1111 1111 1110 1001
	//b<<1的原码          1000 0000 0000 0000 0000 0000 0001 0110  = -22

	printf("%d\n%d\n",a<<1,b<<1);
	return 0;
}

代码结果

22
-22
请按任意键继续. . .
6、右移操作(>>)

运算规则:对运算符>>左边的运算量的每一位全部右移右边运算量表示的位数,右边低位被移出去舍弃掉,空出的高位补0还是补1,分两种情况:

(1)对无符号数进行右移时,空出的高位补0。这种右移称为逻辑右移。

(2)对带符号数进行右移时,空出的高位全部以符号位填补。即正数补0,负数补1。这种右移称为算术右移。

注意:

  • 如果被移位的对象长度是n位,那么移位计数必须大于或等于0,且严格小于n。因此,不可能做到在单次操作中将某个数值中的所有位都移出。例如:若一个int型整数是32位,n是一个int型整数,那么n<<31和n<<0这样写是合法的,而n<<32和n<<-1这样写是非法的。
  • 当需要对某整数(浮点数不能进行移位操作)进行除以2的n次幂的操作时,最好用右移n位进行替换,因为在计算机中计算除法更“费劲”,右移运算符更高效一点。
# includeint main(){

	int a = 11;
	//二进制表示(补码):0000 0000 0000 0000 0000 0000 0000 1011
	//a>>1:               0000 0000 0000 0000 0000 0000 0000 0101  = 5
	int b = -11;
	//原码:              1000 0000 0000 0000 0000 0000 0000 1011
	//反码:               1111 1111 1111 1111 1111 1111 1111 0100
	//补码:              1111 1111 1111 1111 1111 1111 1111 0101
	//b>>1的补码          1111 1111 1111 1111 1111 1111 1111 1010
	//b>>1的反码          1111 1111 1111 1111 1111 1111 1111 1001
	//b>>1的原码          1000 0000 0000 0000 0000 0000 0000 0110  = -6

	unsigned int c = 6;
	//补码:              0000 0000 0000 0000 0000 0000 0000 0110
	//c>>1的补码          0000 0000 0000 0000 0000 0000 0000 0011  = 3

	printf("%d\n%d\n%d\n",a>>1,b>>1,c>>1);
	return 0;
}

代码结果:

5
-6
3
请按任意键继续. . .
三、常识与技巧 1、判断某一位是0还是1
# includeint main(){
	//判断第M位是0还是1
	int M = 3;
	int a = 11;
	//补码:              0000 0000 0000 0000 0000 0000 0000 1011
	//1<

代码结果:

a的从左向右第M位是1。
请按任意键继续. . .
2、任意数与0异或保持不变
# includeint main(){

	int a = 11;
	//补码:              0000 0000 0000 0000 0000 0000 0000 1011
	int b = 0;
	//原码:              0000 0000 0000 0000 0000 0000 0000 0000

	// a^b = b^a          0000 0000 0000 0000 0000 0000 0000 1011  = 11

	printf("%d\n",a^b);
}

代码结果:

11
请按任意键继续. . .
3、任意数与本身异或为0
# includeint main(){

	int a = 11;
	//补码:              0000 0000 0000 0000 0000 0000 0000 1011

	// a^a                0000 0000 0000 0000 0000 0000 0000 0000  = 0

	printf("%d\n",a^a);
}

代码结果:

0
请按任意键继续. . .
4、将二进制位最后一位1变成0

对于任意整数 x,令 x=x & (x−1),该运算将 x 的二进制表示的最后一个 1 变成 0。

# includeint main(){
	int x = 10;
	//x:      0000 0000 0000 0000 0000 0000 0000 1010
	//x-1:     0000 0000 0000 0000 0000 0000 0000 1001
	//x&(x-1): 0000 0000 0000 0000 0000 0000 0000 1000

	return 0;
}
四、数据结构练习题 1、消失的数字

数组nums包含从0n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

示例:

输入:[3,0,1]
输出:2
  • 首先我们需要知道:1、任何数与0异或不变;2、相同数异或为0;
  • 数组 nums中有 n 个数,在这 n个数的后面添加从 0 到 n 的每个整数,则添加了 n+1 个整数,共有 2n+1 个整数;

  • 在2n+1 个整数中,消失的数字只在后面 n+1 个整数中出现一次,其余的数字在前面 n 个整数中(即数组中)和后面 n+1 个整数中各出现一次,即其余的数字都出现了两次;

  • 对这2n+1个整数进行异或,出现两次的异或没了,只剩下出现一次的数字(即消失的数字);

int missingNumber(int* nums, int numsSize){
    int i;
    int res = 0;
    for(i = 0; i< numsSize;i++){
        res ^= nums[i];
    } 
    for(i = 0; i<= numsSize; i++){
        res ^= i;
    }
    return res;

}
2、数组中数字出现的次数

剑指offer56:

一个整型数组 nums里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

示例1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]
  • 设出现一次的两个数字是a 和b,那么所有数字异或的结果就等于ab异或的结果,我们记为x。如果我们把x写成二进制的形式{x_{32}x_{31}...x_{k}...x_{1}}, x_{i}=0/1,i=1...32;
  • 我们现在思考一个问题,x_{k}=1意味着什么?意味着ab他们的第k位不相同;

  • 还有一个重要信息;除了ab其他数字两两相同。也就表示他们第k位相同;

  • 我们根据第k位区分数据有两个作用,1、ab肯定区分开;2、相同的数字分到同一组;

  • 对两个组分别异或就可以得到ab

# include# includeint* singleNumbers(int* nums, int numsSize, int* returnSize){

    //假设出现一次的是a,b
    int res = 0;
    int res1 = 0;
    int res2 = 0;
    int i;
    int M=0;
    // 首先求出a^b
    for(i=0;i

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文名称:C语言位运算总结-创新互联
网站路径:http://myzitong.com/article/jopdd.html