逻辑运算、位运算


在逻辑上有所谓的「且」、「或」与「反」运算,在 C++ 提供这几个基本逻辑运算所需的逻辑运算符(Logical operator),分别为「且」(&&)、「或」(||)及「反相」(!)三个运算符。

来看看下面这个程序会输出什么?

int num = 75;
cout <<  (num > 70 && num < 80) << endl;
cout << (num > 80 || num < 75)  << endl;
cout << !(num > 80 || num < 75) << endl;

三段程序分别会输出 1、0 与 1,也就是分别表示truefalsetrue三种状况。

&&运算中,如果左边的式子已经被评断为false,可立即判断整个式子为false,因而右边的式子就不会再评断;||运算中如果左边的式子已经被评断为true,可以判断整个式子为true,因而右边的式子就不会再评断。

接下来看看「位运算符」(Bitwise operator),数位设计上有 AND、OR、NOT、XOR 与补数等运算,C++ 提供这些运算的就是位运算符,它们的对应分别是 AND (&)、OR(|)、NOT(!)、XOR(^)与补数(~)。

如果不会基本的位运算,这边可以提供一个程序来显示各个运算的结果:

#include <iostream>
using namespace std;

int main() { 
    cout << "AND 运算:" << endl; 
    cout << "0 AND 0\t\t" << (0 & 0) << endl; 
    cout << "0 AND 1\t\t" << (0 & 1) << endl; 
    cout << "1 AND 0\t\t" << (1 & 0) << endl; 
    cout << "1 AND 1\t\t" << (1 & 1) << endl; 

    cout << "OR 运算:" << endl; 
    cout << "0 OR 0\t\t" << (0 | 0) << endl; 
    cout << "0 OR 1\t\t" << (0 | 1) << endl; 
    cout << "1 OR 0\t\t" << (1 | 0) << endl; 
    cout << "1 OR 1\t\t" << (1 | 1) << endl; 

    cout << "XOR 运算:" << endl; 
    cout << "0 XOR 0\t\t" << (0 ^ 0) << endl; 
    cout << "0 XOR 1\t\t" << (0 ^ 1) << endl; 
    cout << "1 XOR 0\t\t" << (1 ^ 0) << endl; 
    cout << "1 XOR 1\t\t" << (1 ^ 1) << endl; 

    cout << "NOT 运算:" << endl; 
    cout << "NOT 0\t\t" << (!0) << endl; 
    cout << "NOT 1\t\t" << (!1) << endl; 

    return 0;
}

执行结果如下:

AND 运算:
0 AND 0         0
0 AND 1         0
1 AND 0         0
1 AND 1         1
OR 运算:
0 OR 0          0
0 OR 1          1
1 OR 0          1
1 OR 1          1
XOR 运算:
0 XOR 0         0
0 XOR 1         1
1 XOR 0         1
1 XOR 1         0
NOT 运算:
NOT 0           1
NOT 1           0

位运算是逐位运算的,例如 10010001 与 01000001 作 AND 运算,是一个一个位对应运算,答案就是 00000001;而补数运算是将所有的位 0 变 1,1 变 0,例如 00000001 经补数运算就会变为 11111110,例如下面这个程序所示:

signed char num = 255;
cout << ~num;

这段程序会在控制台显示 0,signed char使用一个字节,若用于存储正整数最大可存储 255 的值,255 的二进制表示法为 11111111,经补数运算就是 00000000,也就是 0。

例如下面这个程序,运用位运算来判断使用者的输入是否为奇数:

#include <iostream>
using namespace std;

int main() { 
    int input = 0; 

    cout << "输入正整数:"; 
    cin >> input; 
    cout << "输入为奇数?" 
         << (input & 1 ? 'Y' : 'N') 
         << endl; 

    return 0;
}

执行结果如下:

输入正整数:5
输入为奇数?Y

这个程序的原理是,奇数的数值若以二进制来表示,其最右边的位必为 1,而偶数最右边的位必为 0,所以使用 1 来与输入的值作 AND 运算,由于 1 除了最右边的位为 1 之外,其它位都会是 0,与输入数值 AND 运算的结果,只会留下最右边位为0或为的结果,其它部份都被 0 AND 运算遮掉了。,例如:

00000100    4
00000001    1
00000000    判 断为偶数

00000011    3
00000001    1
00000001    判 断为奇数

底下是个简单的 XOR 字符加密例子,先看看程序:

#include <iostream>
using namespace std;

int main() { 
    char ch = 'A'; 

    cout << "before encoding:" << ch 
         << endl; 

    ch = ch ^ 0x7; 
    cout << "after encoding:" << ch 
         << endl; 

    ch = ch ^ 0x7; 
    cout << "decoding:" << ch 
         << endl; 

    return 0;
}

执行结果如下:

before encoding:A
after encoding:F
decoding:A

0x7是整数的 16 进制写法,其实就是 10 进制的 7,将位与 1 作 XOR 的作用后位反转:

01000001    65 (对应 ASCII 的'A')
00000111    0x7
01000110    70 (对应 ASCII 中的'F')

这个简单的 XOR 字符加密,要解密也只要再进行相同的位反转就可以了。

虽然说明时都只取 8 个位来说明,但实际位在运算时,需依数据类型所占的内存长度而定,例如在使用int类型的 0 运算时,要考虑的不会只有 8 个位。

在位运算上还有左移(<<)与右移(>>)两个运算符(不是coutcin使用的<<>>);左移运算符会将所有的位往左移指定的位数,左边被挤出去的位会被丢弃,而右边会补上 0;右移运算则是相反,会将所有的位往右移指定的位数,右边被挤出去的位会被丢弃,至于左边位补 0 或补 1 则不一定,视系统而定。

可以使用左移运算来作简单的 2 次方运算示范,如下所示:

#include <iostream>
using namespace std;

int main() { 
    int num = 1; 

    cout << "2 的 0 次:" << num
         << endl; 

    num = num << 1; 
    cout << "2 的 1 次:" << num
         << endl; 

    num = num << 1; 
    cout << "2 的 2 次:" << num
         << endl; 

    num = num << 1; 
    cout << "2 的 3 次:" << num 
         << endl; 

    return 0;
}

执行结果如下:

2 的 0 次:1
2 的 1 次:2
2 的 2 次:4
2 的 3 次:8

实际来左移看看就知道为何可以如此运算了:

00000001    1
00000010    2
00000100    4
00001000    8




展开阅读全文