C语言位运算总结位操作基础基本的位操作符有与、或、异或、取反、左移、右移这6种,它们的运算规则如下所示:
注意以下几点:
位操作应用
只要根据最未位是0还是1来决定,为0就是偶数,为1就是奇数。因此可以用if (a & 1 == 0)代替if (a % 2 == 0)来判断a是不是偶数。可以得到如下代码:
可以这样理解: 1)a^=b 即a=(a^b); 2)b^=a 即b=b^(a^b),由于^运算满足交换律,b^(a^b)=b^b^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的,所以此时b被赋上了a的值。 3)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=5
变换符号就是正数变成负数,负数变成正数。可以利用求补码的方法(按位取反+1)来 处理。 如对于-11和11,可以通过下面的变换方法将-11变成11 1111 0101(二进制) –取反-> 0000 1010(二进制) –加1-> 0000 1011(二进制) 同样可以这样的将11变成-11 0000 1011(二进制) –取反-> 0000 1010(二进制) –加1-> 1111 0101(二进制) 可以得到如下代码:
对于任何数,与0异或都会保持不变,与-1即0xFFFFFFFF异或就相当于取反,因此,a与i异或后再减i(因为i为0或-1,所以减i即是要么加0要么加1)也可以得到绝对值因此可以得 到如下代码:
给出一个32位的无符号整数。称这个二进制数的前16位为“高位”,后16位为“低位”。现在写一程序将它的高低位交换。例如,数0x1234ABCD用二进制表示为: 0001 0010 0011 0100 1010 1011 1100 1101 将它的高低位进行交换,我们得到了一个新的二进制数: 1010 1011 1100 1101 0001 0010 0011 0100 它即是0xABCD1234。 这个问题用位操作解决起来非常方便,设x=0x1234ABCD由于x为无符号数,右移时会执行逻辑右移即高位补0,因此x右移16位将得到0000 0000 0000 0000 0001 0010 0011 0100。而x左移8位将得到0000 0000 0000 0000 1010 1011 1100 1101。可以发现只要将x$amp;>amp;$gt;16与x$amp;
我们知道如何对字符串求逆序,现在要求计算二进制的逆序,如数34520用二进制表示为:10000110 11011000 00000000 00000000 将它逆序,我们得到了一个新的二进制数:00000000 00000000 00011011 01100001 它即是十进制的7009。 回顾下字符串的逆序的方法,可以从字符串的首尾开始,依次交换两端的数据。在二进制逆序我们也可以用这种方法,但运用位操作的高低位交换来处理二进制逆序将会得到更简洁的方法。类似于归并排序的分组处理,可以通过下面4步得到32位数据的二进制逆序: 第一步:每2位为一组,组内高低位交换 00 00 00 00 00 00 00 00 10 00 01 10 11 01 10 00 → 00 00 00 00 00 00 00 00 01 00 10 01 11 10 01 00 第二步:每4位为一组,组内高低位交换 0000 0000 0000 0000 0100 1001 1110 0100 → 0000 0000 0000 0000 0001 0110 1011 0001 第三步:每8位为一组,组内高低位交换 00000000 00000000 00010110 10110001 → 00000000 00000000 01100001 00011011 第四步:每16位为一组,组内高低位交换 0000000000000000 0110000100011011 → 0110000100011011 0000000000000000 对第一步,可以依次取出每2位作一组,再组内高低位交换,这样有点麻烦,下面介绍一种非常有技巧的 方法。先分别取10000110 11011000的奇数位和偶数位,空位以下划线表示。 原 数 00000000 00000000 10000110 11011000 奇数位 0_0_0_0_ 0_0_0_0_ 1_0_0_1_ 1_0_1_0_ 偶数位 _0_0_0_ 0 _0_0_0_ 0 _0_0_1_0 _1_1_0_0 将下划线用0填充,可得 原 数 00000000 00000000 10000110 11011000 奇数位 00000000 00000000 10000010 10001000 偶数位 00000000 00000000 00000100 01010000 再将奇数位右移一位,偶数位左移一位,此时将这两个数据相与即可以达到奇偶位上数据交换的效果了。 原 数 00000000 00000000 10000110 11011000 奇数位右移 00000000 00000000 01000011 01101100 偶数位左移 00000000 00000000 00001000 10100000 相或得到 00000000 00000000 01001000 11100100 可以看出,结果完全达到了奇偶位的数据交换,再来考虑代码的实现—— 取x的奇数位并将偶数位用0填充用代码实现就是x & 0xAAAAAAAA 取x的偶数位并将奇数位用0填充用代码实现就是x & 0×55555555 因此,第一步就用代码实现就是: x = ((x & 0xAAAAAAAA) $amp;>amp;$gt; 1) | ((x & 0×55555555) $amp; 类似可以得到如下代码:
方法1: 考虑到n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1,同时不改变此位置前的所有位,那么n&(n-1)即可消除这个最低位的1。这样便有了比顺序枚举所有位更快的算法:循环消除最低位的1,循环次数即所求1的个数。此算法的时间复杂度为O(n的二进制表示中的1的个数),最坏情况下的复杂度O(n的二进制表示的总位数)。
方法2: 通过下面四步来计算其二进制中1的个数二进制中1的个数。 第一步:每2位为一组,组内高低位相加 00 00 00 00 00 00 00 00 10 00 01 10 11 01 10 00 → 00 00 00 00 00 00 00 00 01 00 01 01 10 01 01 00 第二步:每4位为一组,组内高低位相加 0000 0000 0000 0000 0100 0101 1001 0100 → 0000 0000 0000 0000 0001 0010 0011 0001 第三步:每8位为一组,组内高低位相加 00000000 00000000 00010010 00110001 → 00000000 00000000 00000011 00000100 第四步:每16位为一组,组内高低位相加 0000000000000000 0000001100000100 → 0000000000000000 0000000000000111 代码如下:
参考资料
你可能还喜欢:
|
|
来自: lixinhecom > 《C语言》