【C++ primer】高效的逻辑运算符

一，引例
问题：把一个字节逆置，要求用移位的方法 unsigned char ch 八位

思路一：初始一个unsigned char temp=0;

用1分别左移 0--7位跟ch 相与，如果大于零，则在7-i(相对应的位置置1否则置0)

#include <iostream>
using namespace std;

unsigned char RollbackChar(unsigned char ch) 
{ 
        unsigned char temp = 0; 
        for(int i = 0 ; i < 8 ; i++) 
                if(ch & (1<<i)) 
                        temp |= (1<<(7-i)); 
        return temp; 
}
int main()
{
    unsigned char a=8;
    cout<<(int)RollbackChar(a);
    
    return 0;
}

或者

unsigned char reverse3( unsigned char c)//一步一步向前移动
{
        unsigned char r = 0;
        
        r |= c&1;
        
        for( int i = 0; i < 7; i++)
                r =r<<1,c=c>>1,r |= c&1;      

        return r;
}

思路二：查表法，典型的空间换时间，在现代的CPU上，这种算法具有最快的速度。

就是把每一种情况（256种）对应的情况都表示到一个数组中，然后查询

unsigned char reverse1(unsigned char c)
{
static unsigned char table[256] =
{
0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,
0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,
0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,
0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,
0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,
0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,
0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,
0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,
0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,
0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,
0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,
0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,
0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,
0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF
};
return table[c];
}

思路三：逐位判断，看起来似乎比算法1更简洁，但是因为if语句牵涉到一个跳转指令引起流水线重置的问题，在现在的CPU上不见得更快速。

unsigned char reverse4( unsigned char c)
{
unsigned char r = 0;

if( c&0x01 ) r |= 0x80; //第一位置1
if( c&0x02 ) r |= 0x40;
if( c&0x04 ) r |= 0x20;
if( c&0x08 ) r |= 0x10;
if( c&0x10 ) r |= 0x08;
if( c&0x20 ) r |= 0x04;
if( c&0x40 ) r |= 0x02;
if( c&0x80 ) r |= 0x01;

return r;
}

二，C/C++用移位实现乘除法运算,提高运行效率
用移位实现乘除法运算
a=a*4;
b=b/4;
可以改为：
a=a<<2;
b=b>>2;
说明：
除2 = 右移1位 乘2 = 左移1位
除4 = 右移2位 乘4 = 左移2位
除8 = 右移3位 乘8 = 左移3位

通常如果需要乘以或除以2的n次方，都可以用移位的方法代替。大部分的C编译器,用移位的方法得到代码比调用乘除法子程序生成的代码效率高。实际上，只要是乘以或除以一个整数，均可以用移位的方法得到结果，如：
a=a*9 分析a*9可以拆分成a*(8+1)即a*8+a*1, 因此可以改为： a=(a<<3)+a
a=a*7 分析a*7可以拆分成a*(8-1)即a*8-a*1, 因此可以改为： a=(a<<3)-a
除法还没有想好

三，例题
1）问题：结构体中的字节是哪边是高位哪边是低位。
结论：结构体从上往下依次为 从低位往高位排放
代码：

#include<iostream.h>
union aaa{              //共用体，共用结构中最大的结构的内存
 unsigned char b;
 struct node
 {
  unsigned char a1:1;//最低位
  unsigned char a2:1;//...
  unsigned char a3:1;
  unsigned char a4:1;
  unsigned char a5:1;
  unsigned char a6:1;
  unsigned char a7:1;
  unsigned char a8:1;//最高位
 }wang;
 
};
void  main()
{
 aaa pp;      
 pp.b = 43; //0010 1011
 cout << (int)pp.b << endl;
 cout << (int)pp.wang.a1 << " " << (int)pp.wang.a2 << " " << (int)pp.wang.a3 << " " << 
  (int)pp.wang.a4 << " " << (int)pp.wang.a5 << " " << (int)pp.wang.a6 << " " << 
  (int)pp.wang.a7 << " " << (int)pp.wang.a8 << " " ;
 cout << endl;
}

输出：
43
1 1 0 1 0 1 0 0

2）反转一个字节 和 判断32位整数二进制中1的个数 的算法

unsigned char reverse8( unsigned char c )
{
    c = ( c & 0x55 ) << 1 | ( c & 0xAA ) >> 1;
    c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
    c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
    return c;
}
unsigned long func(unsigned long x)
{
    x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL);
    x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL);
    x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL);
    x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL);
    x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL);
    return x;
}

四，C语言的底层操作

1）概述
　　 C语言的内存模型基本上对应了现在von Neumann（冯·诺伊曼）计算机的实际存储模型，很好的达到了对机器的映射，这是C/C++适合做底层开发的主要原因，另外，C语言适合做底层开发还有另外一个原因，那就是C语言对底层操作做了很多的的支持，提供了很多比较底层的功能。
2）结合问题分别进行阐述。
　　问题一：移位操作
　　 在运用移位操作符时，有两个问题必须要清楚：
　　 (1)在右移操作中，腾空位是填 0 还是符号位；
　　 (2)什么数可以作移位的位数。
答案与分析：
　　 ">>"和"<<"是指将变量中的每一位向右或向左移动, 其通常形式为:
　　 右移: 变量名>>移位的位数
　　 左移: 变量名<<移位的位数
　　经过移位后, 一端的位被"挤掉",而另一端空出的位以0 填补,在C语言中的移位不是循环移动的
　　(1) 第一个问题的答案很简单，但要根据不同的情况而定。如果被移位的是无符号数，则填 0 。如果是有符号数，那么可能填 0 或符号位。如果你想解决右移操作中腾空位的填充问题，就把变量声明为无符号型（unsigned），这样腾空位会被置 0。
　　(2) 第二个问题的答案也很简单：如果移动 n 位，那么移位的位数要不小于 0 ，并且一定要小于 n 。这样就不会在一次操作中把所有数据都移走。
　　 比如，如果整型数据占 32 位，n 是一整型数据，则 n << 31 和 n << 0 都合法，而 n << 32 和 n << -1 都不合法。
　　

【注意】即使腾空位填符号位，有符号整数的右移也不相当与除以。为了证明这一点，我们可以想一下 -1 >> 1 不可能为 0 。
　

　问题二：位段结构
struct RPR_ATD_TLV_HEADER
{
ULONG res1:6;
ULONG type:10;
ULONG res1:6;
ULONG length:10;
};
　　位段结构是一种特殊的结构, 在需按位访问一个字节或字的多个位时, 位结构比按位运算符更加方便。
　　位结构定义的一般形式为:
struct位结构名{
　数据类型 变量名: 整型常数;
　数据类型 变量名: 整型常数;
} 位结构变量;
　　

其中: 整型常数必须是非负的整数, 范围是0~15, 表示二进制位的个数, 即表示有多少位。
　　变量名是选择项, 可以不命名, 这样规定是为了排列需要。
　　例如: 下面定义了一个位结构。
struct{
　unsigned incon: 8; /*incon占用低字节的0~7共8位*/
　unsigned txcolor: 4;/*txcolor占用高字节的0~3位共4位*/
　unsigned bgcolor: 3;/*bgcolor占用高字节的4~6位共3位*/
　unsigned blink: 1; /*blink占用高字节的第7位*/
}ch;
　　位结构成员的访问与结构成员的访问相同。
　　例如: 访问上例位结构中的bgcolor成员可写成:ch.bgcolor
　　位结构成员可以与其它结构成员一起使用。按位访问与设置，方便&节省
　　例如:
struct info{
　char name[8];
　int age;
　struct addr address;
　float pay;
　unsigned state: 1; //工人的状态
　unsigned pay: 1; //工资是否已发放
}workers;'
　　上例的结构定义了关于一个工人的信息。其中有两个位结构成员, 每个位结构成员只有一位, 因此只占一个字
节但保存了两个信息, 该字节中第一位表示工人的状态, 第二位表示工资是否已发放。由此可见使用位结构可以节
省存贮空间。
　　注意不要超过值限制

　　

问题三：按位运算符
　　C语言和其它高级语言不同的是它完全支持按位运算符。这与汇编语言的位操作有些相似。 C中按位运算符列出
如下:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━
操作符 作用
────────────────────────────
& 位逻辑与
| 位逻辑或
^ 位逻辑异或
- 位逻辑反
>> 右移
<< 左移
━━━━━━━━━━━━━━━━━━━━━━━━━━━━
　　注意：
　　1、 按位运算是对字节或字中的实际位进行检测、设置或移位, 它只适用于字符型和整数型变量以及它们的变
体, 对其它数据类型不适用。
　　2、 关系运算和逻辑运算表达式的结果只能是1或0。 而按位运算的结果可以取0或1以外的值。要注意区别按位
运算符和逻辑运算符的不同, 例如, 若x=7, 则x&&8 的值为真(两个非零值相与仍为非零), 而x&8的值为0。
　　3、 | 与 ||，&与&&，~与! 的关系
　　 &、| 和 ~ 操作符把它们的操作数当作一个为序列，按位单独进行操作。比如：10 & 12 = 8，这是因为"&"操作符把 10 和 12 当作二进制描述 1010 和 1100 ，所以只有当两个操作数的相同位同时为 1 时，产生的结果中相应位才为 1 。同理，10 | 12 = 14 ( 1110 )，通过补码运算，~10 = -11 ( 11...110101 )。<以多少为一个位序列>

&&、|| 和！操作符把它们的操作数当作"真"或"假"，并且用 0 代表"假"，任何非 0 值被认为是"真"。它们返回 1 代表"真"，0 代表"假"，对于"&&"和"||"操作符，如果左侧的操作数的值就可以决定表达式的值，它们根本就不去计算右侧的操作数。所以，!10 是 0 ，因为 10 非 0 ；10 && 12 是 1 ，因为 10 和 12 均非 0 ；10 || 12也是 1 ，因为 10 非 0 。并且，在最后一个表达式中，12 根本就没被计算，在表达式 10 || f( ) 中也是如此。