C语言位运算

原创
2016/10/23 20:18
阅读数 489

一、掩码运算

1.什么是掩码?

计算机中最小的单位是字节,一个字节代表8个二进制位。在实际的应用中许多信息并不需要使用一个字节来表示。例如表示当前系统运行是否正常,这种标志的取值只有0和1两种。因此使用是个完整的字节保存该标志就很浪费了。

这些标志为是以位的形式存储的,因此当需要提取这些标志位的时候就需要使用掩码。掩码是人为生成的整数值,配合基本的位运算,可以提取变量中指定的位。其基本思想是将变量中所需要的位保持,其它位清零。

例如下面的程序:

#include <stdio.h>

int main(void)
{
  unsigned char a, b;
  unsigned char mask = 0x30; //二进制00111000
  a = 0xff;  //测试用的数据
  b = a & mask;  //使用掩码得出数据a的第4~6位
  printf("the flag b is : 0x%x\n", b);
  return 0;
}

运行结果为:

在Linux中许多标志位都使用这种概念,将标志位聚集以节省存储空间。典型的一个应用是Linux文件的权限标志位。一个Linux文件往往有需索标志位,最基本的实现应当具有九个标志位,分别是所有者、组用户和其它用户的读写执行位。

二、不安全的位运算

由于不同体系结构中变量的大小是不相同的,因此在使用掩码进行操作的过程中会遇到一些问题。以下是一个不安全运算的例子:

#include <stdio.h>

int main(void)
{
  int a = 0x3;  //在16位计算机上运行,这时int占2个字节
  int b = 0xfffe;
  printf("the result is : 0x%x\n", a & b);
  return 0;
}

在16位状态下运行看起来好像没什么问题,但是如果将此代码放到一个整型变量占4个字节的系统上,这时a&0xfffe的结果就不正确了,由于a是一个无符号整型,而b是一个短整型,在位与运算时会将b扩展为一个无符号整型数,这时b实际上变成0x0000fffe,这样运算后不仅会将最低一位置0,也会将其高16位置0.

为了预防移植性的问题,需要使用更好的代码:

#include <stdio.h>

int main(void)
{
  int a = 0x1234567f;

  /**
   * b为整数1取反,不论在32为系统还是16位系统上
   * ~1均可保证最低位是“0”,而高位均为1
   */
  int b = ~1;
  printf("the result is : 0x%x\n", a & b);
  return 0;

使用这个方法,代码就具有了良好的移植性,可以在任何字长的机器中进行移植,编译系统会根据体系结构来确定常量值占用的字节,这样操作数的长度就根据运行平台确定,这种使用方法是安全的。

三、异或运算的特性

异或运算是C语言运算符中使用频率很高的一个运算。异或又称XOR运算符,它规定若参与运算的两个二进制位相同,则结果为0,不同为1:

0 ^ 0 == 0, 0 ^ 1 == 1, 1 ^ 0 == 1, 1 ^ 1 == 0

1.与1相异或--取原值的相反值

假设有01111010,与11111111做异或运算:

  01111010
^ 11111111
  10000101

2.与0异或--保留原值

假设有01111010,与00000000做异或操作如下:

  01111010
^ 00000000
  01111010

利用这两个特性可以实现对某些位的快速翻转,而其它的位保持不变。下面实例演示了异或运算的这种特性。该程序首先定义了一个变量flags,flags变量中的第三个位代表一个标志位,这个标志相当于一个开关,现在需要迅速将这个标志位的值取反:

#include <stdio.h>

int main(void)
{
  int flags = 0xfffffff7; //存储标志位的整型数据
  int mask = 0x08;        //掩码
  printf("the first 0x%x\n", flags=flags ^ mask);

  printf("the srcond 0x%x\n", flags ^ mask);
  return 0;
}

运行结果为:

3.交换两个值,不需要用临时变量

异或运算可以实现交换两个变量而不使用临时变量,而且这个交换不用担心变量会溢出。例如交换a和b:

a = a ^ b;  //①
b = b ^ a;  //②
a = a ^ b;  //③

这时候a和b的值已经交换。下面用一个实例说明这一点:

   a = 011
^  b = 100
   a = 111  (a ^ b的结果)
^  b = 100
   b = 011  (b ^ a的结果)
^  a = 111
   a = 100  (a ^ b的结果)

公式推导:

  • 将式①带入式②得:b = b^a = b^a^b,根据交换律得b = a^b^b。由于b^b等于0,a^0等于a,所以b = a^0 = a,即b = a 。
  • 将式①②分别带入③得:a = a^b = (a^b)^(b^a^b) = a^a^b^b^b = 0^b = b,即a = b 。

由此可以编写一个实现两个变量交换的程序:

 

#include <stdio.h>

int main(void)
{
  int a, b;
  a = 2;
  b = 3;
  a = a ^ b;
  b = b ^ a;
  a = a ^ b;
  printf("a is : %d, b id : %d\n", a, b);
  return 0;
}

运行结果:

四、移位运算

1.移位运算的陷阱

在进行移位运算的操作时,需要特别注意的是运算符的操作数一定要小于移位数据的长度。例如int a,在移位时所移位数不能超过31.如果超过,结果是未定义的也就是结果未知。如下代码:

#include <stdio.h>

int main(void)
{
  int a = 32;
  int x = 0xFFFFFFFF; //定义一个整型
  printf("%d\n", 0xFFFFFFFF >> 32);  //右移32位,结果未定义
  printf("%d\n", x >> 32);  //右移32位,结果未定义
  printf("%d\n", 0xFFFFFFFF >> a);  //右移32位,结果未定义
  return 0;
}

编译器会提示警告:

正确的移位操作的移位数不能超过变量长度减1:

#include <stdio.h>

int main(void)
{
  int a = 31;
  int x = 0xFFFFFFFF; //定义一个整型
  printf("%d\n", 0xFFFFFFFF >> 31);  //右移31位
  printf("%d\n", x >> 31);  //右移31位,最高位变为最低位
  printf("%d\n", 0xFFFFFFFF >> a);  //右移31位
  return 0;
}

输出结果为:

第一个输出1是因为0xFFFFFFFF会被C编译器解释为无符号整数,在右移时最高位补符号位即0,因此移位后最低位为1,其余位为0 。

第二次输出-1是因为x是一个有符号整型,所以0xFFFFFFFF的最高位1会被解释为符号位,右移最高位补符号位即1,所以移位后32位都是1,结果就是-1 。

2.移位运算的实例

实现变量a的循环右移。所谓循环右移就是右移时低位移出部分补到高位上:

步骤:

1.将a右端(低位)的n位放到b中的高位 

b = a << (32 - n);

2.将a右移n位高位补0

c = a >> n;

注意:由于不同平台处理时会出现偏差,所以在执行此步骤是应加上对a高位的清楚,所以应写成如下形式:

c = a >> n;
c = c & ~(~0 << n);  //保证c的高位不会出现由于移位产生的“1”的干扰

3.将b和c进行 | 运算

c = c | b;

则变量c中保存的就是所要的结果。

程序如下:

#include <stdio.h>

int right_shift(int a, int n)
{
  int b, c;
  b = a << (32 - n);
  c = a >> n;
  c = c & ~(~0 << (32 - n));
  c = c | b;
  return c;
}

int main(void)
{
  int a, b;
  a = 8;
  b = right_shift(a, 4);  //循环右移4位
  printf("the result : 0x%x\n", b);
  return 0;

运行结果:

 

展开阅读全文
打赏
0
7 收藏
分享
加载中
更多评论
打赏
0 评论
7 收藏
0
分享
返回顶部
顶部