精华内容
下载资源
问答
  • 位操作基础篇之位操作全面总结

    万次阅读 多人点赞 2012-03-19 09:34:08
    Title: 位操作基础篇之位操作全面总结Author: MoreWindowsE-mail: morewindows@126.comKeyWord: C/C++ 位操作 位操作技巧 判断奇偶 交换两数 变换符号 求绝对值 位操作压缩空间 筛素数 位操作趣味应用 位操作...

    Title:       位操作基础篇之位操作全面总结
    Author:     MoreWindows
    E-mail:      morewindows@126.com
    KeyWord:   C/C++ 位操作 位操作技巧 判断奇偶 交换两数 变换符号 求绝对值 位操作压缩空间 筛素数 位操作趣味应用 位操作笔试面试

    位操作篇共分为基础篇和提高篇,基础篇主要对位操作进行全面总结,帮助大家梳理知识。提高篇则针对各大IT公司如微软、腾讯、百度、360等公司的笔试面试题作详细的解答,使大家能熟练应对在笔试面试中位操作题目。

          下面就先来对位操作作个全面总结,欢迎大家补充。

    在计算机中所有数据都是以二进制的形式储存的。位运算其实就是直接对在内存中的二进制数据进行操作,因此处理数据的速度非常快。

    在实际编程中,如果能巧妙运用位操作,完全可以达到四两拨千斤的效果,正因为位操作的这些优点,所以位操作在各大IT公司的笔试面试中一直是个热点问题。因此本文将对位操作进行如下方面总结:

          一. 位操作基础,用一张表描述位操作符的应用规则并详细解释。

          二. 常用位操作小技巧,有判断奇偶、交换两数、变换符号、求绝对值。

          三. 位操作与空间压缩,针对筛素数进行空间压缩。

          四. 位操作的趣味应用,列举了位操作在高低位交换、二进制逆序、二进制中1的个数以及缺失的数字这4种趣味应用。

    希望读者能认真学习和亲自上机输入代码进行实验,相信通过本文及适当的练习可以使你对位操作有更加深入的了解,在笔试面试中遇到位操作相关试题能更加从容。

    一. 位操作基础

    基本的位操作符有与、或、异或、取反、左移、右移这6种,它们的运算规则如下所示:

    符号

     描述

     运算规则                        by MoreWindows

    &      

     与

    两个位都为1时,结果才为1

    |  

     或    

    两个位都为0时,结果才为0

    ^    

    异或

    两个位相同为0,相异为1

    ~   

    取反

    0变1,1变0

    << 

    左移

    各二进位全部左移若干位,高位丢弃,低位补0

    >> 

    右移

    各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移)

    注意以下几点:

    1.  在这6种操作符,只有~取反是单目操作符,其它5种都是双目操作符。

    2.  位操作只能用于整形数据,对float和double类型进行位操作会被编译器报错。

    3.  对于移位操作,在微软的VC6.0和VS2008编译器都是采取算术称位即算术移位操作,算术移位是相对于逻辑移位,它们在左移操作中都一样,低位补0即可,但在右移中逻辑移位的高位补0而算术移位的高位是补符号位。如下面代码会输出-4和3。

    	int a = -15, b = 15;
    	printf("%d %d\n", a >> 2, b >> 2);

    因为15=0000 1111(二进制),右移二位,最高位由符号位填充将得到0000 0011即3。-15 = 1111 0001(二进制),右移二位,最高位由符号位填充将得到1111 1100即-4(见注1)。

    4.  位操作符的运算优先级比较低,因为尽量使用括号来确保运算顺序,否则很可能会得到莫明其妙的结果。比如要得到像1,3,5,9这些2^i+1的数字。写成int a = 1 << i + 1;是不对的,程序会先执行i + 1,再执行左移操作。应该写成int a = (1 << i) + 1;

    5.  另外位操作还有一些复合操作符,如&=、|=、 ^=、<<=、>>=。

     

    二. 常用位操作小技巧

    下面对位操作的一些常见应用作个总结,有判断奇偶、交换两数、变换符号及求绝对值。这些小技巧应用易记,应当熟练掌握。

    1.判断奇偶

    只要根据最未位是0还是1来决定,为0就是偶数,为1就是奇数。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)来判断a是不是偶数。

    下面程序将输出0到100之间的所有奇数。

    	for (i = 0; i < 100; ++i)
    		if (i & 1)
    			printf("%d ", i);
    	putchar('\n');

    2.交换两数

    一般的写法是:

    void Swap(int &a, int &b)
    {
    	if (a != b)
    	{
    		int c = a;
    		a = b;
    		b = c;
    	}
    }

    可以用位操作来实现交换两数而不用第三方变量:

    void Swap(int &a, int &b)
    {
    	if (a != b)
    	{
    		a ^= b;
    		b ^= a;
    		a ^= b;
    	}
    }

    可以这样理解:

    第一步  a^=b 即a=(a^b);

    第二步  b^=a 即b=b^(a^b),由于^运算满足交换律,b^(a^b)=b^b^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的,所以此时b被赋上了a的值。

    第三步 a^=b 就是a=a^b,由于前面二步可知a=(a^b),b=a,所以a=a^b即a=(a^b)^a。故a会被赋上b的值。
    再来个实例说明下以加深印象。int a = 13, b = 6;

    a的二进制为 13=8+4+1=1101(二进制)

    b的二进制为 6=4+2=110(二进制)

    第一步 a^=b  a = 1101 ^ 110 = 1011;

    第二步 b^=a  b = 110 ^ 1011 = 1101;即b=13

    第三步 a^=b  a = 1011 ^ 1101 = 110;即a=6

    3.变换符号

    变换符号就是正数变成负数,负数变成正数。

    如对于-11和11,可以通过下面的变换方法将-11变成11

          1111 0101(二进制) –取反-> 0000 1010(二进制) –加1-> 0000 1011(二进制)

    同样可以这样的将11变成-11

          0000 1011(二进制) –取反-> 0000 0100(二进制) –加1-> 1111 0101(二进制)

    因此变换符号只需要取反后加1即可。完整代码如下:

    //by MoreWindows( http://blog.csdn.net/MoreWindows )  
    #include <stdio.h>
    int SignReversal(int a)
    {
    	return ~a + 1;
    }
    int main()
    {
    	printf("对整数变换符号 --- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");
    	int a = 7, b = -12345;
    	printf("%d  %d\n", SignReversal(a), SignReversal(b));
    	return 0;
    }

    4.求绝对值

    位操作也可以用来求绝对值,对于负数可以通过对其取反后加1来得到正数。对-6可以这样:

          1111 1010(二进制) –取反->0000 0101(二进制) -加1-> 0000 0110(二进制)

    来得到6。

    因此先移位来取符号位,int i = a >> 31;要注意如果a为正数,i等于0,为负数,i等于-1。然后对i进行判断——如果i等于0,直接返回。否之,返回~a+1。完整代码如下:

    //by MoreWindows( http://blog.csdn.net/MoreWindows )
    int my_abs(int a)
    {
    	int i = a >> 31;
    	return i == 0 ? a : (~a + 1);
    }
    

    现在再分析下。对于任何数,与0异或都会保持不变,与-1即0xFFFFFFFF异或就相当于取反。因此,a与i异或后再减i(因为i为0或-1,所以减i即是要么加0要么加1)也可以得到绝对值。所以可以对上面代码优化下:

    //by MoreWindows( http://blog.csdn.net/MoreWindows )
    int my_abs(int a)
    {
    	int i = a >> 31;
    	return ((a ^ i) - i);
    }
    

    注意这种方法没用任何判断表达式,而且有些笔面试题就要求这样做,因此建议读者记住该方法(^_^讲解过后应该是比较好记了)。

     

    三. 位操作与空间压缩

    筛素数法在这里不就详细介绍了,本文着重对筛素数法所使用的素数表进行优化来减小其空间占用。要压缩素数表的空间占用,可以使用位操作。下面是用筛素数法计算100以内的素数示例代码(注2):

    //by MoreWindows( http://blog.csdn.net/MoreWindows )
    #include <stdio.h>
    #include <memory.h>
    const int MAXN = 100;
    bool flag[MAXN];
    int primes[MAXN / 3 + 1], pi;
    //对每个素数,它的倍数必定不是素数。
    //有很多重复如flag[10]会在访问flag[2]和flag[5]时各访问一次
    void GetPrime_1()
    {
    	int i, j;
    	pi = 0;
    	memset(flag, false, sizeof(flag));
    	for (i = 2; i < MAXN; i++)
    		if (!flag[i])
    		{
    			primes[pi++] = i;
    			for (j = i; j < MAXN; j += i)
    				flag[j] = true;
    		}
    }
    void PrintfArray()
    {
    	for (int i = 0; i < pi; i++)
    		printf("%d ", primes[i]);
    	putchar('\n');
    }
    int main()
    {
    	printf("用筛素数法求100以内的素数\n-- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");  
    	GetPrime_1();
    	PrintfArray();
    	return 0;
    }

    运行结果如下:

    在上面程序是用bool数组来作标记的,bool型数据占1个字节(8位),因此用位操作来压缩下空间占用将会使空间的占用减少八分之七。

    下面考虑下如何在数组中对指定位置置1,先考虑如何对一个整数在指定位置上置1。对于一个整数可以通过将1向左移位后与其相或来达到在指定位上置1的效果,代码如下所示:

    	//在一个数指定位上置1
    	int j = 0;
    	j |=  1 << 10;
    	printf("%d\n", j);
    

    同样,可以1向左移位后与原数相与来判断指定位上是0还是1(也可以将原数右移若干位再与1相与)。

        //判断指定位上是0还是1
    	int j = 1 << 10;
    	if ((j & (1 << 10)) != 0)
    		printf("指定位上为1");
    	else
    		printf("指定位上为0");

    扩展到数组上,我们可以采用这种方法,因为数组在内存上也是连续分配的一段空间,完全可以“认为”是一个很长的整数。先写一份测试代码,看看如何在数组中使用位操作:

    //by MoreWindows( http://blog.csdn.net/MoreWindows )  
    #include <stdio.h>
    int main()
    {
    	printf("     对数组中指定位置上置位和判断该位\n");
    	printf("--- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");
    	//在数组中在指定的位置上写1
    	int b[5] = {0};
    	int i;
    	//在第i个位置上写1
    	for (i = 0; i < 40; i += 3)
    		b[i / 32] |= (1 << (i % 32));
    	//输出整个bitset
    	for (i = 0; i < 40; i++)
    	{
    		if ((b[i / 32] >> (i % 32)) & 1)
    			putchar('1');
    		else 
    			putchar('0');
    	}
    	putchar('\n');
    	return 0;
    }

    运行结果如下:

    可以看出该数组每3个就置成了1,证明我们上面对数组进行位操作的方法是正确的。因此可以将上面筛素数方法改成使用位操作压缩后的筛素数方法:

    //使用位操作压缩后的筛素数方法
    //by MoreWindows( http://blog.csdn.net/MoreWindows ) 
    #include <stdio.h>
    #include <memory.h>
    const int MAXN = 100;
    int flag[MAXN / 32 + 1];
    int primes[MAXN / 3 + 1], pi;
    void GetPrime_1()
    {
    	int i, j;
    	pi = 0;
    	memset(flag, 0, sizeof(flag));
    	for (i = 2; i < MAXN; i++)
    		if (!((flag[i / 32] >> (i % 32)) & 1))
    		{
    			primes[pi++] = i;
    			for (j = i; j < MAXN; j += i)
    				flag[j / 32] |= (1 << (j % 32));
    		}
    }
    void PrintfArray()
    {
    	for (int i = 0; i < pi; i++)
    		printf("%d ", primes[i]);
    	putchar('\n');
    }
    int main()
    {
    	printf("用位操作压缩后筛素数法求100以内的素数\n-- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");  
    	GetPrime_1();
    	PrintfArray();
    	return 0;
    }

    同样运行结果为:

    另外,还可以使用C++ STL中的bitset类来作素数表。筛素数方法在笔试面试出现的几率还是比较大的,能写出用位操作压缩后的筛素数方法无疑将会使你的代码脱颖而出,因此强烈建议读者自己亲自动手实现一遍,平时多努力,考试才不慌。

    位操作的压缩空间技巧也被用于strtok函数的实现,请参考《strtok源码剖析 位操作与空间压缩》(http://blog.csdn.net/morewindows/article/details/8740315

     

    四. 位操作的趣味应用

    位操作有很有趣的应用,下面列举出一些,欢迎读者补充。

    1.  高低位交换

    给出一个16位的无符号整数。称这个二进制数的前8位为“高位”,后8位为“低位”。现在写一程序将它的高低位交换。例如,数34520用二进制表示为:

          10000110 11011000

    将它的高低位进行交换,我们得到了一个新的二进制数:

          11011000 10000110

    它即是十进制的55430。

    这个问题用位操作解决起来非常方便,设x=34520=10000110 11011000(二进制) 由于x为无符号数,右移时会执行逻辑右移即高位补0,因此x右移8位将得到00000000 10000110。而x左移8位将得到11011000 00000000。可以发现只要将x>>8与x<<8这两个数相或就可以得到11011000 10000110。用代码实现非常简洁:

    //高低位交换 by MoreWindows( http://blog.csdn.net/MoreWindows )  
    #include <stdio.h>
    template <class T>
    void PrintfBinary(T a)
    {
    	int i;
    	for (i = sizeof(a) * 8 - 1; i >= 0; --i)
    	{
    		if ((a >> i) & 1)
    			putchar('1');
    		else 
    			putchar('0');
    		if (i == 8)
    			putchar(' ');
    	}
    	putchar('\n');
    }
    int main()
    {
    	printf("高低位交换 --- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");
    
    	printf("交换前:    ");
    	unsigned short a = 3344520;
    	PrintfBinary(a);
    
    	printf("交换后:    ");
    	a = (a >> 8) | (a << 8);
    	PrintfBinary(a);
    	return 0;
    }

    运行结果如下:

    2.  二进制逆序

    我们知道如何对字符串求逆序,现在要求计算二进制的逆序,如数34520用二进制表示为:

          10000110 11011000

    将它逆序,我们得到了一个新的二进制数:

          00011011 01100001

    它即是十进制的7009。

        回顾下字符串的逆序,可以从字符串的首尾开始,依次交换两端的数据。在二进制逆序我们也可以用这种方法,但运用位操作的高低位交换来处理二进制逆序将会得到更简洁的方法。类似于归并排序的分组处理,可以通过下面4步得到16位数据的二进制逆序:

    第一步:每2位为一组,组内高低位交换

          10 00 01 10  11 01 10 00

      -->01 00 10 01 11 10 01 00

    第二步:每4位为一组,组内高低位交换

          0100 1001 1110 0100

      -->0001 0110 1011 0001

    第三步:每8位为一组,组内高低位交换

          00010110 10110001

      -->01100001 00011011

    第四步:每16位为一组,组内高低位交换

          01100001 00011011

      -->00011011 01100001

    对第一步,可以依次取出每2位作一组,再组内高低位交换,这样有点麻烦,下面介绍一种非常有技巧的方法。先分别取10000110 11011000的奇数位和偶数位,空位以下划线表示。

          原 数    10000110 11011000

          奇数位 1_0_0_1_ 1_0_1_0_

          偶数位  _0_0_1_0 _1_1_0_0

    将下划线用0填充,可得

          原 数    10000110 11011000

          奇数位 10000010 10001000

          偶数位 00000100 01010000

    再将奇数位右移一位,偶数位左移一位,此时将这两个数据相或即可以达到奇偶位上数据交换的效果了。

          原 数           10000110 11011000

          奇数位右移 01000001 01000100  

          偶数位左移 00001000 10100000

          相或得到      01001001 11100100

    可以看出,结果完全达到了奇偶位的数据交换,再来考虑代码的实现——

          取x的奇数位并将偶数位用0填充用代码实现就是x & 0xAAAA

          取x的偶数位并将奇数位用0填充用代码实现就是x & 0x5555

    因此,第一步就用代码实现就是:

           x = ((x & 0xAAAA) >> 1) | ((x & 0x5555) << 1);

    类似可以得到后三步的代码。完整程序如下:

    //二进制逆序 by MoreWindows( http://blog.csdn.net/MoreWindows )  
    #include <stdio.h>
    template <class T>
    void PrintfBinary(T a)
    {
    	int i;
    	for (i = sizeof(a) * 8 - 1; i >= 0; --i)
    	{
    		if ((a >> i) & 1)
    			putchar('1');
    		else 
    			putchar('0');
    		if (i == 8)
    			putchar(' ');
    	}
    	putchar('\n');
    }
    int main()
    {
    	printf("二进制逆序 --- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");
    
    	printf("逆序前:    ");
    	unsigned short a = 34520;
    	PrintfBinary(a);
    
    	printf("逆序后:    ");	
    	a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
    	a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
    	a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
    	a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);
    	PrintfBinary(a);
    }

    运行结果如下:

    3.  二进制中1的个数

    统计二进制中1的个数可以直接移位再判断,当然像《编程之美》书中用循环移位计数或先打一个表再计算都可以。本文详细讲解一种高效的方法。以34520为例,可以通过下面四步来计算其二进制中1的个数二进制中1的个数。

    第一步:每2位为一组,组内高低位相加

          10 00 01 10  11 01 10 00

      -->01 00 01 01  10 01 01 00

    第二步:每4位为一组,组内高低位相加

          0100 0101 1001 0100

      -->0001 0010 0011 0001

    第三步:每8位为一组,组内高低位相加

          00010010 00110001

      -->00000011 00000100

    第四步:每16位为一组,组内高低位相加

          00000011 00000100

      -->00000000 00000111

    这样最后得到的00000000 00000111即7即34520二进制中1的个数。类似上文中对二进制逆序的做法不难实现第一步的代码:

           x = ((x & 0xAAAA) >> 1) + (x & 0x5555);

    好的,有了第一步,后面几步就请读者完成下吧,先动动笔再看下面的完整代码:

    //二进制中1的个数  by MoreWindows( http://blog.csdn.net/MoreWindows ) 
    #include <stdio.h>
    template <class T>
    void PrintfBinary(T a)
    {
    	int i;
    	for (i = sizeof(a) * 8 - 1; i >= 0; --i)
    	{
    		if ((a >> i) & 1)
    			putchar('1');
    		else 
    			putchar('0');
    		if (i == 8)
    			putchar(' ');
    	}
    	putchar('\n');
    }
    int main()
    {
    	printf("二进制中1的个数 --- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");
    	
    	unsigned short a = 34520;
    	printf("原数    %6d的二进制为:  ", a);
    	PrintfBinary(a);
    	
    	a = ((a & 0xAAAA) >> 1) + (a & 0x5555);
    	a = ((a & 0xCCCC) >> 2) + (a & 0x3333);
    	a = ((a & 0xF0F0) >> 4) + (a & 0x0F0F);
    	a = ((a & 0xFF00) >> 8) + (a & 0x00FF);	
    	printf("计算结果%6d的二进制为:  ", a);	
    	PrintfBinary(a);
    	return 0;
    }

    运行结果如下:

    可以发现巧妙运用分组处理确实是解决很多二进制问题的灵丹妙药。

    4.  缺失的数字

    很多成对出现数字保存在磁盘文件中,注意成对的数字不一定是相邻的,如2, 3, 4, 3, 4, 2……,由于意外有一个数字消失了,如何尽快的找到是哪个数字消失了?

    由于有一个数字消失了,那必定有一个数只出现一次而且其它数字都出现了偶数次。用搜索来做就没必要了,利用异或运算的两个特性——1.自己与自己异或结果为0,2.异或满足交换律。因此我们将这些数字全异或一遍,结果就一定是那个仅出现一个的那个数。 示例代码如下:

    //缺失的数字  by MoreWindows( http://blog.csdn.net/MoreWindows ) 
    #include <stdio.h>
    int main()
    {
    	printf("缺失的数字 --- by MoreWindows( http://blog.csdn.net/MoreWindows )  ---\n\n");
    	
    	const int MAXN = 15;
    	int a[MAXN] = {1, 347, 6, 9, 13, 65, 889, 712, 889, 347, 1, 9, 65, 13, 712};
    	int lostNum = 0;
    	for (int i = 0; i < MAXN; i++)
    		lostNum ^= a[i];
    	printf("缺失的数字为:  %d\n", lostNum);	
    	return 0;
    }
    

    在这个题目中有一个数字丢失了,如果有两个数字丢失了应该怎么做了,请看《【白话经典算法系列之十二】数组中只出现1次的两个数字(百度面试题)》 

    地址:http://blog.csdn.net/morewindows/article/details/8214003

     

    位操作是一种高效优美的方法,同时由于其高效的运算性能和掌握难度较大,位操作运算一直是笔试面试时的热门话题之一。本文详细总结了位操作的方法与技巧并列出4种位操作趣味应用,如果读者能亲自上机实现代码,相信必能更好应对笔试和面试时可能遇到的位操作问题。

    另外,欢迎各位能提供笔试面试中的位操作相关的题目给我,我将会在提高篇中加入这些。谢谢大家。

     

     

    注1.int类型一般占4字节,32位。因此15准确表达为

    15=00000000 00000000 00000000 00001111(二进制)

    -15准确表达为

    -15=11111111 11111111 11111111 11110001(二进制)

    为了简便起见,文章中使用15=00001111(二进制),-15=11110001(二进制)。

     

    注2.这种筛素数的方法很朴素,会多次重复访问数据,有什么办法能改进一下吗?请看《改进的筛素数方法》一文。

     

    转载请标明出处,原文地址:http://blog.csdn.net/morewindows/article/details/7354571

    如果觉得本文对您有帮助,请点击‘顶’支持一下,您的支持是我写作最大的动力,谢谢。



    展开全文
  • C语言位操作

    千次阅读 多人点赞 2017-06-04 16:51:00
    此文将花费您8~15分钟时间,带您对嵌入式中常用的位操作有个了解。和数字电路有点相似!感谢阅读! 位操作符 1.位与& 1、注意:位与符号是一个&,两个&&是逻辑与。 2、真值表:1&0=0 1&1=1 0&0=0 0&1=0 3、从真值表...

    此文将花费您8~15分钟时间,带您对嵌入式中常用的位操作有个了解。和数字电路有点相似!感谢阅读!

    位操作符

    1.位与&
    1、注意:位与符号是一个&,两个&&是逻辑与。
    2、真值表:1&0=01&1=10&0=00&1=0
    3、从真值表可以看出:位与操作的特点是,只有1和1位与结果为1,其余全是0.
    4、位与和逻辑与的区别:位与时两个操作数是按照二进制位彼次对应位相与的,逻辑与是两个操作数作为整体来相与的。(举例:0xAA&0xF0=0xA0,0xAA && 0xF0=1)
     
    2.位或|
    1、注意:位或符号是一个|,两个||是逻辑或。
    2、真值表:1|0=11|1=10|0=00|1=1
    3、从真值表可以看出:位或操作的特点是:只有2个0相位或才能得到0,只要有1个1结果就一定是1.
    4、位或和逻辑或的区别:位或时两个操作数是按照二进制位彼次对应位相与的,逻辑或是两个操作数作为整体来相或的。

    3.位取反~
    1、注意:C语言中位取反是~,C语言中的逻辑取反是!
    2、按位取反是将操作数的二进制位逐个按位取反(1变成0,0变成1);而逻辑取反是真(在C语言中只要不是0的任何数都是真)变成假(在C语言中只有0表示假)、假变成真。

    实验:

    #include <stdio.h>
    void main()
    {
            int a = 5; // 结果 :
            printf("~~a = %d.\n",~~a);//~~a = 5.
            printf("!!a = %d.\n",!!a);//!!a = 1.
    }

    结论:

    @任何非0的数被按位取反再取反就会得到他自己;任何非0的数被按逻辑取反再取反就会得到1;

    @任何非0的数被按逻辑取反再取反就会得到1;
     
    4.位异或^

    1、位异或真值表:

    1^1=0 

    0^0=0

    1^0=1

    0^1=1

    2、位异或的特点:2个数如果相等结果为0,不等结果为1。

    记忆方法:异或就是相异就或操作起来。


    位与、位或、位异或的特点总结:

    位与:(任何数,其实就是1或者0)与1位与无变化,与0位与变成0
    位或:(任何数,其实就是1或者0)与1位或变成1,与0位或无变化
    位异或:(任何数,其实就是1或者0)与1位异或会取反,与0位异或无变化


    5.左移位<< 与右移位>>
    C语言的移位要取决于数据类型。
    对于无符号数,左移时右侧补0(相当于逻辑移位)

    对于无符号数,右移时左侧补0(相当于逻辑移位)

    对于有符号数,左移时右侧补0(叫算术移位,相当于逻辑移位)

    对于有符号数,右移时左侧补符号位(如果正数就补0,负数就补1,叫算术移位)

    实验:

    #include <stdio.h>

    void main()
    {
    int a = 5; // 0101b
    int b = -5;// 1...0101b
    printf("a<<2 = %d.\n",a<<2);
    printf("a>>2 = %d.\n",a>>2);
    printf("b<<2 = %d.\n",b<<2);
    printf("b>>2 = %d.\n",b>>2);

    }

    结果:

    a<<2 = 20.
    a>>2 = 1.
    b<<2 = -20.
    b>>2 = -2.

    结论:

    左移一位,结果*2;

    右移一位,结果/2;

    注释:有符号数右移结果往小的那边走,-5/4=-1.25->-2;

    分析过程自己去分析数值在计算机内部的存储(以补码形式存储!)

    ~嵌入式中研究的移位,以及使用的移位都是无符号数



    位与位或位异或在操作寄存器时的特殊作用

    1.寄存器操作的要求(特定位改变而不影响其他位)
    1、ARM是内存与IO统一编址的,ARM中有很多内部外设,SoC中CPU通过向这些内部外设的寄存器写入一些特定的值来操控这个内部外设,进而操控硬件动作。所以可以说:读写寄存器就是操控硬件。
    2、寄存器的特点是按位进行规划和使用。但是寄存器的读写却是整体32位一起进行的(也就是说你只想修改bit5~bit7是不行的,必须整体32bit全部写入)
    3、寄存器操作要求就是:在设定特定位时不能影响其他位。
    4、如何做到?答案是:读-改-写三部曲。
      读改写的操作理念,就是:当我想改变一个寄存器中某些特定位时,我不会直接去给他写,我会先读出寄存器整体原来的值,然后在这个基础上修改我想要修改的特定位,再将修改后的值整体写入寄存器。
      这样达到的效果是:在不影响其他位原来值的情况下,我关心的位的值已经被修改了。

      
    2.特定位清零用&
    1、回顾上面讲的位与操作的特点:(任何数,其实就是1或者0)与1位与无变化,与0位与变成0
    2、如果希望将一个寄存器的某些特定位变成0而不影响其他位,可以构造一个合适的1和0组成的数和这个寄存器原来的值进行位与操作,就可以将特定位清零。

    3、举例:

    假设原来32位寄存器中的值为:0xAAAAAAAA,我们希望将bit8~bit15清零而其他位不变,可以将这个数与0xFFFF00FF进行位与即可。

    #include <stdio.h>
    void main()
    {
    printf("0x%X.\n",0xAAAAAAAA&0xFFFF00FF);// 0xAAAA00AA.
    }


    3.特定位置1用|
    1、回顾上面讲的位或操作的特点:任何数,其实就是1或者0)与1位或变成1,与0位或无变化

    2、操作手法和刚才讲的位与是类似的。我们要构造这样一个数:要置1的特定位为1,其他位为0,然后将这个数与原来的数进行位或即可。

    3、举例:

    假设原来32位寄存器中的值为:0xAAAAAAAA,我们希望将bit8~bit15置1而其他位不变,可以将这个数与0x0000FF00进行位或即可。

    #include <stdio.h>
    void main()
    {
    printf("0x%X.\n",0xAAAAAAAA|0x0000FF00);// 0xAAAAFFAA.
    }



    4.特定位取反用^
    1、回顾上面讲的位异或操作的特点:(任何数,其实就是1或者0)与1位异或会取反,与0位异或无变化
    2、操作手法和刚才讲的位与是类似的。我们要构造这样一个数:要取反的特定位为1,其他位为0,然后将这个数与原来的数进行位异或即可。

    进行位或即可。

    3、举例:

    假设原来32位寄存器中的值为:0xAAAAAAAA,我们希望将bit8~bit15取反而其他位不变,可以将这个数与0x0000FF00进行异或即可。

    #include <stdio.h>
    void main()
    {
    printf("0x%X.\n",0xAAAAAAAA^0x0000FF00);// 0xAAAA55AA.
    }

    如何用位运算构建特定二进制数

    1.寄存器位操作经常需要特定位给特定值
    1、从上节可知,对寄存器特定位进行置1或者清0或者取反,关键性的难点在于要事先构建一个特别的数,这个数和原来的值进行位与、位或、位异或等操作,即可达到我们对寄存器操作的要求。

    2、

    解法1:用工具软件或者计算器或者自己大脑计算,直接给出完整的32位特定数。

      优势:可以完成工作,难度也不大,操作起来也不是太麻烦。
      劣势:依赖工具,而且不直观,读程序的人不容易理解。
      评价:凑活能用,但是不好用,应该被更好用的方法替代。
    3、解法2:自己写代码用位操作符号(主要是移位和位取反)来构建这个特定的二进制数

    2.使用移位获取特定位为1的二进制数
    1、最简单的就是用移位来获取一个特定位为1的二进制数。譬如我们需要一个bit3~bit7为1(隐含意思就是其他位全部为0)的二进制数,可以这样:(0x1f<<3)
    2、更难一点的要求:获取bit3~bit7为1,同时bit23~bit25为1,其余位为0的数:((0x1f<<3) | (7<<23))

    3.再结合位取反获取特定位为0的二进制数
    1、这次我们要获取bit4~bit10为0,其余位全部为1的数。怎么做?

    2、利用上面讲的方法就可以:(0xf<<0)|(0x1fffff<<11)

    但是问题是:连续为1的位数太多了,这个数字本身就很难构造,所以这种方法的优势损失掉了。

    3、这种特定位(比较少)为0而其余位(大部分)为1的数,不适合用很多个连续1左移的方式来构造,适合左移加位取反的方式来构造。
    4、思路是:先试图构造出这个数的位相反数,再取反得到这个数。
    (譬如本例中要构造的数bit4~bit10为0其余位为1,那我们就先构造一个bit4~bit10为1,其余位为0的数,然后对这个数按位取反即可)- ~(0x7f<<4)

    4.总结:位与、位或结合特定二进制数即可完成寄存器位操作需求
    1、如果你要的这个数比较少位为1,大部分位为0,则可以通过连续很多个1左移n位得到。
    2、如果你想要的数是比较少位为0,大部分位为1,则可以通过先构建其位反数,然后再位取反来得到。

    3、如果你想要的数中连续1(连续0)的部分不止1个,那么可以通过多段分别构造,然后再彼此位或即可。

    这时候因为参与位或运算的各个数为1的位是不重复的,所以这时候的位或其实相当于几个数的叠加。

      
      

    位运算实战演练1

    回顾:要置1用|,用清零用&,要取反用^,~和<< >>用来构建特定二进制数。
    1.给定一个整型数a,设置a的bit3,保证其他位不变。
    a = a | (1<<3)或者 a |= (1<<3)

    2.给定一个整形数a,设置a的bit3~bit7,保持其他位不变。
    a = a | (0b11111<<3)或者 a |= (0x1f<<3);

    3.给定一个整型数a,清除a的bit15,保证其他位不变。
    a = a & (~(1<<15));或者 a &= (~(1<<15));

    4.给定一个整形数a,清除a的bit15~bit23,保持其他位不变。
    a = a & (~(0x1ff<<15));或者 a &= (~(0x1ff<<15));

    5.给定一个整形数a,取出a的bit3~bit8。
    思路:
    第一步:先将这个数bit3~bit8不变,其余位全部清零。
    第二步,再将其右移3位得到结果。
    第三步,想明白了上面的2步算法,再将其转为C语言实现即可。
    a &= (0x3f<<3);
    a >>= 3;

    6.用C语言给一个寄存器的bit7~bit17赋值937(其余位不受影响)。
    关键点:第一,不能影响其他位;第二,你并不知道原来bit7~bit17中装的值。

    思路:

    第一步,先将bit7~bit17全部清零,当然不能影响其他位。

    第二步,再将937写入bit7~bit17即可,当然不能影响其他位。

    a &= ~(0x7ff<<7);

    a |= (937<<7);

     
     

    位运算实战演练2

    1.用C语言将一个寄存器的bit7~bit17中的值加17(其余位不受影响)。
    关键点:不知道原来的值是多少

    思路:

    第一步,先读出原来bit7~bit17的值

    第二步,给这个值加17
    第三步,将bit7~bit17清零
    第四步,将第二步算出来的值写入bit7~bit17

    tmp = a&(0x7ff<<7);

    tmp>>=7;

    tmp+=17;

    a &=~(0x7ff<<7);

    a|=(tmp<<7); 

    2.用C语言给一个寄存器的bit7~bit17赋值937,同时给bit21~bit25赋值17.
    思路:6.的升级版,两倍的6.中的代码即可解决。
    分析:这样做也可以,但是效果不够高,我们有更优的解法就是合两步为一步。

    a &= ~((0x7ff<<7) | (0x1f<<21));

    a |= ((937<<7) | (0x17<<21))

    技术升级:用宏定义来完成位运算

    1.直接用宏来置位、复位(最右边为第1位)
    #define SET_NTH_BIT(x, n)  (x | (1<<(n-1)))

    #define CLEAR_NTH_BIT(x, n) (x & ~(1<<(n-1)))


    2.截取变量的部分连续位。例如:变量0x88, 也就是0b10001000,若截取第2~4位,则值为:0b100 = 4 

    #define GETBITS(x, n, m) ((x & ~(~(0U)<<(m-n+1))<<(n-1)) >> (n-1)) 
    分析:这个题目相当于我们位运算实战演练1中5.做的事情,只不过要用宏来实现。

     这个题目相当于是要把x的bit(n-1)到bit(m-1)取出来

    注:优先级~ 高于 <<高于&

    #define GETBITS(x, n, m) ((x & (~(~(0U)<<(m-n+1))<<(n-1))) >> (n-1)) 

    U表示unsigned int-32


    复杂宏怎么分析:
    ((x & ~(~(0U)<<(m-n+1))<<(n-1)) >> (n-1))


    第一步,先分清楚这个复杂宏分为几部分:2部分

    @(x & ~(~(0U)<<(m-n+1))<<(n-1))

    @>>(n-1)

    分析为什么要>>(n-1),相当于是我们5.中的第二步第二步,再将其右移3位得到结果。)


    第二步,继续解析剩下的:又分为2部分

    @x&

    @~(~(0U)<<(m-n+1))<<(n-1)

    分析为什么要&,相当于我们5中的第一步 (第一步:先将这个数bit3~bit8不变,其余位全部清零。)


    第三步,继续分析剩下的:
    ~ (~(0U)<<(m-n+1))<<(n-1) 
    这个分析时要搞清楚第2坨到底应该先左边取反再右边<<;还是先右边<<再左边取反。
    解法:第一,查C语言优先级表;第二,自己实际写个代码测试。
    说明这个式子应该是 ~(~(0U)<<(m-n+1))<<(n-1) ,这就又分为2部分了

     0x88:10001000

    例如:变量0x88, 也就是0b10001000,若截取第2~4位,则值为:0b100 = 4 

     ~(~(0U)<<(m-n+1))<<(n-1)):00001110
    (x & ~(~(0U)<<(m-n+1))<<(n-1)):00001000
    (x & ~(~(0U)<<(m-n+1))<<(n-1)) >> (n-1):00001000
    展开全文
  • 2 C语言位操作

    万次阅读 2019-04-16 10:04:19
    常用位操作 在这里插入图片描述 位异或:两位都相等,结果为0,不相等则为1 左移位:将一个操作数的各二进制全部左移若干位,左边移除出去的二进制位丢弃,右边的二进制位补0。每进行一次左移位操作,得到的结果是...

    常用位操作

    在这里插入图片描述
    位异或:两位都相等,结果为0,不相等则为1
    左移位:将一个操作数的各二进制全部左移若干位,左边移除出去的二进制位丢弃,右边的二进制位补0。每进行一次左移位操作,得到的结果是原来操作数的一倍(x<<n=x*2^n)
    右移位:将一个操作数的各二进制全部右移若干位,右边的二进制位补0或补1(如果操作数是无符号数或是有符号正数补0,如果是有符号负数补1),右边移除出去的二进制位丢弃。每进行一次右移位操作,得到的结果是原来操作数的一倍(x>>n=x/2^n)
    位操作与寄存器
    寄存器的操作

    (1)寄存器特定位的清零用&
    (2)寄存器特定位置1用I
    (3)寄存器特定位取反用~
    位运算构建特定二进制数

    (1)如果这个数中比较少为1,大部分为0 ,则可以通过连续很多个1左移n位得到
    (2)如果这个数中比较少为0,大部分为1,则可以通过先构造其位反码,然后再位取反
    (3)如果这个数中连续1或者连续0的部分布置一个,则可以通过多段分别构造,然后再彼此位或即可。·
    用宏定义位运算

    (1)用宏来置位
    用宏定义将一个32位二进制数x的第n位置位,
    该宏为#define SET_BIT_N(x,n) ((x) | (1<<((n)-1)))
    (2)用宏来清零
    用宏定义将一个32位二进制数x的第n位清零,
    该宏为#define SET_BIT_N(x,n) ((x) & ~(1<<((n)-1)))
    ---------------------
    作者:超级峰
    来源:CSDN
    原文:https://blog.csdn.net/weixin_40569915/article/details/83997872

    展开全文
  • 位操作指令

    千次阅读 2019-02-26 20:42:10
     位操作指令 位操作类指令 位操作又称为布尔操作,是以位为单位进行的各种操作。在布尔处理机中,借用进位标志Cy来存放逻辑运算结果,大部分操作都涉及Cy,因此它相当于布尔处理机的“累加器”,称为位累加器,...

     

                                                     位操作指令

    位操作类指令

    位操作又称为布尔操作,是以位为单位进行的各种操作。在布尔处理机中,借用进位标志Cy来存放逻辑运算结果,大部分操作都涉及Cy,因此它相当于布尔处理机的“累加器”,称为位累加器,用符号C表示。

    (1) 位传送指令

    MOV C,bit                  ;Cy←(bit)
    MOV bit,C                  ;bit←(Cy)
    这组指令其中的一个操作数必须是进位标志C,另一个可以使位地址(用bit表示)。
    

    (2) 位置位和位清零指令

    SETB C                     ;Cy←1
    SETB bit                    ;biT←1
    这两条指令可以实现地址单元与位累加器的置位。
    CLR C                      ; Cy←0
    CLR bit                     ; biT←0
    这两组指令可以实现地址单元与位累加器的清零。
    

    (3) 位逻辑运算指令

    ① 位逻辑“与”指令
    ANL C,bit ;CY←(CY)∧(bit)
    ANL C,/bit ; CY←(CY)∧(bit)取反
    这两条指令是将CY标志位中的内容与位地址单元的内容或其内容的反码进行逻辑与操作,并将相与的结果再送入到CY的标志位中。
    ② 位逻辑“或”指令
    ORL C,bit ;CY←(CY)∨(bit)
    ORL C,/bit ; CY←(CY) ∨(bit)取反
    这两条指令是将CY标志位中的内容与直接位地址的内容或其内容的反码进行逻辑与操作,并将相与的结果再送入到CY的标志位中。、
    ③ 位逻辑“非”指令
    CPL C ;CY (CY)取反
    CPL bit ;bit←(bit)取反

    (4) 位条件转移指令←

    类比于JZ/JNZ
    ① 位累加器Cy状态判断转移指令
    JC rel ;若(Cy)=1,转移
    JNC rel ;若(Cy)=0,转移
    ② 位状态判断转移指令
    JNB bit,rel ;若(bit)=0,转移
    JBC bit,rel ;若(bit)=1,转移,且bit←
    JB bit,rel ; 若(bit)=1,转移
    其中JBC指令除了判断位地址的内容外,还将被测位清零。

    展开全文
  • kotlin位操作和位运算

    千次阅读 2020-06-18 11:22:12
    一、位操作: shl(bits) – 左移位 (Java’s <<) shr(bits) – 右移位 (Java’s >>) ushr(bits) – 无符号右移位 (Java’s >>>) and(bits) – 与 & or(bits) – 或 || xor(bits) – 异或 ...
  • 首先介绍操作符与位操作符的区别,位操作是程序设计中对位模式按位或二进制数的一元和二元操作。 在许多的微处理器上, 位运算比加减运算略快, 通常位运算比乘除法运算要快很多。 有时候合理利用一个位操作符,可以...
  • 计算机基础----32位操作系统和64位操作系统的区别

    万次阅读 多人点赞 2019-01-18 18:01:57
    众所周知,我们通常说操作系统是32位还是64位说的是32位处理器或64位处理器,windows系统有32位和64位,但是最近被问到32位操作系统和64位操作系统有什么区别?一时间只能想到64位操作系统更快,其他具体区别却说不...
  • 位操作符介绍

    千次阅读 2018-10-08 18:22:12
    C++:位操作基础篇之位操作全面总结 0X01位操作基础 基本的位操作符有与、或、异或、取反、左移、右移这6种,它们的运算规则如下所示: 符号 描述 运算规则 by MoreWindows &amp; 与 两个位都为1时,...
  • Go的位操作

    千次阅读 2018-03-07 12:30:24
    Go的位操作在计算机内存和处理能力都成本昂贵的时代,位操作是(在某些情况下是唯一的)一种被优先选择来处理信息的方式。即使在今天,直接的位操作在一些情况下同样也很重要。例如:低级系统编程,图像处理,密码学...
  • 位操作篇共分为基础篇和提高篇,基础篇主要对位操作进行全面总结,帮助大家梳理知识。提高篇则针对各大IT公司如微软、腾讯、百度、360等公司的笔试面试题作详细的解答,使大家能熟练应对在笔试面试中位操作题目。 ...
  • bit位操作基础篇之位操作全面总结

    千次阅读 2013-09-18 16:13:37
    KeyWord: C/C++ 位操作 位操作技巧 判断奇偶 交换两数 变换符号 求绝对值 位操作压缩空间 筛素数 位操作趣味应用 位操作笔试面试 位操作篇共分为基础篇和提高篇,基础篇主要对位操作进行全面总结,帮助大
  • stm32位操作详解

    千次阅读 2019-04-11 21:54:00
    stm32位操作详解 STM32位操作原理 思想:把一个比特分成32位,每位都分配一个地址,这样就有32个地址,通过地址直接访问。 位操作基础 位运算 位运算的运算分量只能是整型或字符型数据,...
  • C语言位操作的神应用(位操作

    千次阅读 2016-08-10 10:30:11
    不少代码通过位操作,解题很巧妙,学习语言,就要学其精髓,学其底层,不可蜻蜓点水 例一: 函数getbits(x,p,n),返回x中从右边数第p位开始向右数n位的字段 unsigned getbits(unsigned x,int p,int n) {  ...
  • 在64位操作系统上运行32位的程序

    千次阅读 2019-04-19 10:03:26
    在64位操作系统上运行32位的程序
  • Lua 5.1 位操作(与,或,异或操作)

    万次阅读 2018-11-30 10:42:11
    由于lua5.1不支持位操作,自己写了一个lua的位操作函数,代码如下: 方法1: function Xor(num1,num2) local tmp1 = num1 local tmp2 = num2 local str = "" repeat local s1 = tmp1 % 2 local s2 = tmp...
  • C位操作介绍

    千次阅读 2014-07-04 15:14:20
    C++位操作包括两种:传统的C语言方式的位操作和C++中利用bitset容器的位操作 一、传统的C方式位操作: 1.基本操作:  使用一个unsigned int变量来作为位容器。 2.操作符: | 按位或操作符:result=exp1|exp2...
  • Java移位操作符以及按位操作

    千次阅读 2018-05-28 16:27:35
    位操作符:针对两个整数参数中的对应位执行布尔代数运算,并生成一个结果。 按位与&amp;:如果两个输入位都是1则生成一个输出位1,否则生成一个输出位0。 按位或| :如果两个输入位只要有一位是1则生成一个...
  • 求余操作与按位操作的效率

    千次阅读 2018-05-25 19:24:20
    需求:奇偶数判断 / 二进制数最后一位是0 or 1问题的判断正常方法: n % 2 == 0 偶数按位操作: n &amp; 1 == 0 偶数在LeetCode第190. Reverse Bits中600个测试用例,求余操作提交多次大部分都用时4ms,而按位...
  • 位操作符&(按位与)

    千次阅读 2018-11-23 10:13:40
    位操作符&amp;(按位与)  
  • 详解Java中的位操作

    千次阅读 2018-08-28 12:02:03
    在实际编程中,如果能巧妙运用位操作,完全可以达到四两拨千斤的效果,正因为位操作的这些优点,所以位操作在各大IT公司的笔试面试中一直是个热点问题。 位操作基础   基本的位操作符有与、或、异或、取反、左移...
  • C# 位运算 位操作 教程

    千次阅读 多人点赞 2011-09-18 19:16:58
    在C#中可以对整型运算对象按位进行逻辑运算。按位进行逻辑运算的意义是:依次取被运算对象的每个位,进行逻辑运算,每...C# 中支持的位操作符号有:   运算符号 意义 运算对象类型 运算结果
  • VMware12提示 已将该虚拟机配置为使用 64 位客户机操作系统。但是,无法执行 64 位操作。 此主机支持 Intel VT-x,但 Intel VT-x 处于禁用状态
  • int在64位操作系统中占多少位?

    千次阅读 2017-03-15 13:27:00
    曾经是这样的:16位操作系统中,int 占16位;在32位操作系统中,int 占32位。但是现在人们已经习惯了 int 占32位,因此在64位操作系统中,int 仍为32位。64位整型用 long long 或者 __int64 转载于:...
  • 1.32位64位操作系统基本数据类型字节大小 在一些没有操作系统的嵌入式计算机系统上,int的长度与处理器字长一致;有操作系统时,操作系统的字长与处理器的字长不一定一致,此时编译器根据操作系统的字长来定义int...
  • 位操作(取反)

    千次阅读 2018-11-23 10:07:04
    位操作(取反)  
  • Golang 位操作符总结

    千次阅读 2018-02-11 11:10:01
    位运算可能在平常的编程中使用的并不多,但涉及到底层优化,一些算法及源码可能会经常遇见,下面先回顾一下位操作符的基础: 与操作:&amp; 1 &amp; 1 = 1 1 &amp; 0 = 0 0 &amp; 1 = 0 0 &...
  • perl位操作

    千次阅读 2010-04-21 11:17:00
    另外就是位操作符了,和c一摸一样。 位与:& 位或:| 位非:~ 位异或:^ 左移:$x > 2 注:不要将&用于负整数,因为PERL将会把它们转化为无符号数。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 130,303
精华内容 52,121
关键字:

位操作