位操作
一些有关位操作的知识
-
常用的等式：-n = ~(n - 1) = ~n + 1 -
获取整数n的二进制中最后一个1：n & (-n)或者n & ~(n - 1) -
去掉整数n的二进制中最后一个1：n & (n - 1)
结构声明中的冒号和数字
C语言的结构体可以实现位段（也称位域），它的定义形式是在一个定义的结构体成员后加上冒号，然后是该成员所占的位数。位段的结构体成员必须是int或unsigned int类型，不能是其他类型。位段在内存中的存储方式是由具体的编译器决定的
-
定义位段的长度不能大于存储单元的长度 -
一个位段如果不能放在一个存储单元里，那么它会把这个存储单元中剩余空间闲置，而从下一个存储单元开始存储下一个位段，即一个位段不能跨越两个存储单元，位段在一个存储单元中的存储是紧凑的 -
位段名缺省时称作无名位段，无名位段的存储空间通常不用，而位段长度为0位表示下一个位段存储在一个新的存储单元中。位段长度为0的时候，位段名必须缺省 -
一个结构体中既可以定义位段成员，也可以同时定义一般的结构体成员。这时，一般成员不和位段存储在同一个单元
举例：
#include <stdio.h>
typedef struct
{
int a:2;
int b:2;
int c:1;
}test;
int main()
{
test t;
t.a = 1;
t.b = 3;
t.c = 1;
printf("%d\n%d\n%d\n", t.a, t.b, t.c);
return 0;
}
由于a占两位，而a被赋值为1，二进制就是01，因此%d输出的时候输出1；b也占两位，赋值为3，二进制是11，由于使用了%d输出，表示的是将这个b作为有符号int型来输出，这样的话二进制的11将会有一位被认为是符号位，并且两位的b也会被扩展为int类型，也就是4字节。
其实a也做了这种扩展，只是扩展符号位的时候，由于数字在计算机中存储都是补码形式，因此扩展符号位的时候正数用0填充高位，负数用1填充高位。因此，对于a来说，输出的时候被扩展为00000000 00000000 00000000 00000001，而b扩展为11111111 11111111 11111111 11111111，也就是-1。同理，t.c的输出也是-1
利用位运算计算数的绝对值
在计算机中，数字都是以补码的形式存在，求负数的绝对值，应该是不管符号位，所有位执行按位取反，末位加1操作即可
对于一个负数，将其右移31位后会变成0xffffffff，即-1；而对于一个正数而言，右移31位则为0x00000000，即0。所以，利用异或操作即可实现这一功能：
int MyAbs(int x)
{
int y;
y = x >> 31;
return (x^y)-y;
}
求整型数的二进制表示中1的个数
方法一
判断数的二进制表示中每一位是否为1，如果为1，就在count上加1，而循环的次数就是n的位数，程序如下：
int func(unsigned int n)
{
int count = 0;
while(n)
{
count += n & 0x1u;
n >>= 1;
}
return count;
}
但该方法在1比较稀疏时效率较低
方法二
当一个数被减1时，它最右边的那个值为1的位将会变成0，同时其右边的所有位都会变成1。因此，我们只需不断的执行x & (x - 1)，就可以把二进制数中的最后一位1逐个去掉，当循环到x等于0的时候，循环的次数就是x对应的二进制数中1的个数，程序如下：
int func(int x)
{
int count = 0;
while(x)
{
count ++;
x = x & (x - 1);
}
return count;
}
不使用sizeof，如何判断操作系统是16位，还是32位
如果没有强调不许用sizeof，如果在32位机器上，sizeof(int) = 4，如果在16位机器上，sizeof(int) = 2
方法一
一般而言，机器位数不同，其表示的数字的最大值也不同。在16位机器上，int可以表示-32768到+32767之间的数，也就是说，它能表示的最大值为32767，如果再加1，将会溢出为-32768。但是，在32位机器上，int能表示的最大值为2147483647，因此32767+1不会溢出。可以根据这个特性，判断系统是16位，还是32位
方法二
对类型为unsigned int的0取反，不同位数下的0值取反，其结果不一样。例如，在32位机器上，执行按位取反运算，结果为429496727295,。而在16位机器上，取反的结果值为65535，可以根据这个特性来判断系统是16位还是32位
大端与小端
采用小端模式的CPU对操作数的存放方式是从低字节到高字节，而大端模式对操作数的存放方式是从高字节到低字节。
80x86机是小端模式，单片机一般为大端模式。Intel处理器一般都是小端模式。
如何判断计算机处理器是大端还是小端
方法一
联合体union的存放顺序是所有成员都从低地址开始存放。
程序如下：
int checkCPU()
{
{
union w
{
int a;
char b;
}c;
c.a = 1;
return (c.b == 1);
}
}
方法二
还可以通过指针地址来判断，由于在32位计算机系统中，short占两个字节，char占1个字节，所以可以采用如下方式判断：
int checkCPU()
{
unsigned short usData = 0x1122;
unsigned char *pucData = (unsigned char*)&usData;
return (*pucData == 0x22);
}
不用除法操作符实现两个正整数的除法
方法一
可以根据除法运算的原理进行减法操作，用除数循环减被除数，减一次结果加1，知道刚好减为0或余数小于被除数为止
int div(int a, int b)
{
int result = 0;
if (b == 0)
{
printf("除数不能为0\n");
return result;
}
while (a >= b)
{
result++;
a = a - b;
}
return result;
}
当a很大，b很小时，这个算法的效率很低
方法二
翻倍比较法。对于方法一，如果每次采用将比较熟翻倍的比较方法，则算法效率能够得到极大优化
int MyDiv(int a, int b)
{
int k = 0;
int c = b;
int res = 0;
if (b == 0)
{
printf("除数不能为0\n");
return 0;
}
if (a < b)
{
return 0;
}
for (; a >= c; c <<= 1; k ++)
{
if (a - c < b)
{
return 1 << k;
}
}
return MyDiv(a - (c >> 1), b) + (1 << (k - 1));
}
方法三
采用移位操作实现：
int div(const int x, const int y)
{
int left_num = x;
int result = 0;
while (left_num >= y)
{
int multi = 1;
while (y * multi <= (left_num >> 1)
{
multi = multi << 1;
}
result += multi;
left_num -= y * multi;
}
return result;
}
只用逻辑运算实现加法
对于二进制加法而言，1 + 1 = 0，1 + 0 = 1，0 + 1 = 1，0 + 0 = 0，与位运算中的异或类似，而且0 + 0的进位是0，1 + 0的进位是0，只有1 + 1的进位有效，这又与&运算相似，即只有1 & 1 = 1，又由于进位是进位到高一位，与<<运算相似。同时，num1和num2相&后，如果结果为0，那么不存在进位，运算完成。用递归实现：
int add(int num1, int num2)
{
if (0 == num2)
{
return num1;
}
int sumTemp = num1 ^ num2;
int carray = (num1 & num2) << 1;
return add(sumTemp, carry);
}
非递归实现：
int add(int num1, int num2)
{
int sum = 0;
int num3 = 0;
int num4 = 0;
while ((num1 & num2) > 0)
{
num3 = num1 ^ num2;
num4 = num1 & num2;
num1 = num3;
num2 = num4 << 1;
}
sum = num1 ^ num2;
return sum;
}
用逻辑运算实现乘法
对于二进制数乘法：1011 * 1010，可以将表达式拆分为两个运算，1011*0010与1011*1000的和，而对于二进制的运算，左移1位，等价于乘以0010，左移3位，等价于乘以1000，所以，两者的乘积为10110与1011000的和
所以，乘法可以通过一些列移位和加法完成。最后一个1可通过b&~(b-1)求得，可通过b&(b-1)去掉，为了高效地得到左移的位数，可以提前计算一个map：
int multiply(int a, int b)
{
bool neg = (b < 0);
if (neg)
{
b = -b;
}
int sum = 0;
map<int, int> bit_map;
for (int i = 0; i < 32; i++)
{
bit_map.insert(pair<int, int>(1 << i, i));
}
while (b > 0)
{
int last_bit = bit_map[b & ~(b - 1)];
sum += (a << last_bit);
b &= b - 1;
}
if (neg)
{
sum = -sum;
}
return sum;
}
|