Skip to content

数字作开关! Bitwise Flag

Bitwise Flag 是一种紧凑的,用于表达布尔值的数据结构

Published: at 07:21 PM

在文章的开头,我想问一个问题。当下的天气是怎么样的?

你的回答可能是晴天,多云,下雨,下雪,大暴雨,甚至暴雨夹雪…谁知道呢?不过这个天气问题可以引出这篇文章的主题,Bitwise Flag。

天气问题

正如你所见,对于当前天气的状态和组合似乎很多。除了我们常见的晴天,雨,雪;很可能还会出现一些组合。例如像是晴天但是下着雨 ( 太阳雨 ) 又或者是刮风又下雨。如何在计算机中描述准确的天气现象组合是这篇文章将要使用的例子之一,那让我们开始吧。

使用 Boolean?

首先要知道的一点是,Boolean 类型中的 True 和 False 会被分别对应为 1 (True / High) 和 0 (False / Low)。因此无论是 True 还是数字 1,False 还是数字 0,它们都代表相同的意思。这是一个很重要的特性,在后面将会用到。

接着,我们要回归到最原始的状态。假设一开始只有晴天和下雨两种状态。如果想要表示当前的天气现象为晴天,不下雨。可以如下表达。

int sun = 1;
int rain = 0;

这样一来,我们可以通过条件表达式来处理一些逻辑。

if (sun)
{
    printf("晴天\n"); // 只有这行会被执行,因为 sun 为 true (数字 1)
}

if (rain)
{
    printf("雨天\n"); // 这里不会被执行,因为 rain 为 false (数字 0)
}

但随着用于表达天气现象的词语越来越多和天气现象开始变得可以组合。例如下雨和下雪可以同时进行,并伴随着闪电,打雷和大风。表达这个天气现象组合的代码就会变成这样。

int sun = 0;
int rain = 1;
int snow = 1;
int wind = 1;
int thunder = 1;
int lightning = 1;

而不难看出,因为随着选项变多,要跟着创建的布尔变量也在随之变多。我们不太可能在任何需要表达天气现象组合的地方都建立那么多的变量,那么要怎么使用单一变量就可以表达一个或者多个布尔值?

使用 Bitwise Flag!

在开始对 Bitwise Flag 的内容前,我想先引入一部分二进制与逻辑运算的内容,以便还没有这块知识的读者也可以一窥这种神奇的数据结构。

二进制

如果你已经了解过二进制,你可以跳过这段内容

我们日常生活中常用的进制方法为十进制 (Decimal / DEC),当遇到 10 的时候就会进位。当我们从 0 数到 9,就会向高位进位,变成 10。从 10 数到 19,我们又会向高位进位,变成 20。直到高位变成了 9,再次进位就会变成了 100。这是十进制的计算过程。

而计算机因为数字电路中的逻辑门透过高低电平,或 1 和 0 来进行逻辑运算,所以二进制 (Binary / BIN) 显得尤为重要,也是计算机唯一能读懂的信息。Bitwise Flag 也正是透过二进制和逻辑运算的巧用来构建了一个紧凑的布尔数据结构。

二进制有两个数字,分别是 01。进位的基本规则就是逢二进一,与十进制类似,当数字不够用时就要向前进位。例如十进制的 0 到 4 在二进制中分别如下表示。

0 1 2 3 4
0000 0001 0010 0011 0100

十进制中的 0 和 1 在二进制中最好表示,使用二进制本身的 0 和 1 就可以。而从十进制的数字 2 开始,因为二进制数字不够用,则开始进位,从 0001 进位到 0010 以此类推,如此反复,我们可以继续推出从十进制数字 5 - 9 的二进制表示法。

5 6 7 8 9
0101 0110 0111 1000 1001

逻辑运算

如果你已经了解过 逻辑与逻辑或逻辑异或 ,你可以跳过这段内容

这里将会讲到本文中用到的三种基础逻辑运算,分别为:

  • 逻辑与 (AND / Logical conjunction / Conjunction / &)
  • 逻辑或 (OR / Logical disjunction / Disjunction / |)
  • 逻辑异或 (XOR / Exclusive disjunction / Exclusive or / ^)

并且它们的数学符号分别如下表示:

AND : \text{AND} \ : \ \land
OR : \text{OR} \ : \ \lor
XOR : \text{XOR} \ : \ \oplus

你可以在 LaTeX 中使用 \land , \lor\oplus 或者在 Typst 的数学模式下使用 and, orxor 来输入代表逻辑与,逻辑或和逻辑异或的符号。

逻辑与的规则为,如果给定的两个变量中只要有一个为 False ( 或者 0 ),那么输出结果就为 False ( 或者 0 )。

A B 结果
True / 1 True / 1 True / 1
True / 1 False / 0 False / 0
False / 0 True / 1 False / 0
False / 0 False / 0 False / 0

逻辑或的规则为,如果给定的两个变量中只要有一个为 True (或者 1),那么输出结果就为 True (或者 1)。

A B 结果
True / 1 True / 1 True / 1
True / 1 False / 0 True / 1
False / 0 True / 1 True / 1
False / 0 False / 0 False / 0

逻辑异或的规则为,如果给定的两个变量不同时输出 True (或者 1)相同则为 False (或者 0)。

A B 结果
True / 1 True / 1 False / 0
True / 1 False / 0 True / 1
False / 0 True / 1 True / 1
False / 0 False / 0 False / 0

其他二进制表示法

这部分内容会对后半部分的内容有些微帮助,你可以当作额外的有趣小知识。跳过这部分内容不会影响对于 Bitwise Flag 的理解。你可以使用你操作系统上的计算器,并且调整到程序员 (Programmer) 模式进行试验。macOS, Windows 和大部分 Linux Distros 的自带计算器都有该模式。

一些特殊的二进制数字有一些其他的表示方法,下面将会提到 2 的幂 (Power of two) 和移位 (Arithmetic shift)

首先,任何 2 的幂在二进制中只会出现一个 1。例如对于如下公式进行列表:

2n=Result2^n = \text{Result}
n 结果 (十进制) 结果 (二进制)
0 1 0001
1 2 0010
2 4 0100
3 8 1000
4 16 0001 0000
5 32 0010 0000
6 64 0100 0000
7 128 1000 0000
8 256 0001 0000 0000
9 512 0010 0000 0000
10 1,024 0100 0000 0000
11 2,048 1000 0000 0000

不难发现,当 n + 1 时,二进制中 1 的位置会向左移动。反之,当 n - 1 时,1 的位置会向右移动 ( 但前提为幂必须为整数 )

因此,当我们要表达的二进制数字正好是 2 的幂时,我们也可以使用下方公式进行表示。

2n2^n

移位 (Arithmetic shift) 是一种位操作 (Bitwise operation),通常来说位操作的处理性能比四则运算快 (特别是乘法运算)。移位分为左移 (Arithmetic left shift / <<) 和右移 (Arithmetic right shift / >>)。

左移的作用是在二进制数的最右位补 0 ,并且舍弃二进制最左位的数字。例如二进制中的十进制 1 为 0001 ,通过左移 1 位变成 0010 。此时如果将这个二进制换算成十进制,我们可以得到数字 2。

右移的作用大同小异,在二进制最左位补 0 ,然后舍弃掉二进制最右位的数字。例如刚才在二进制中的十进制 2 为 0010 ,此时对它进行右移 1 位会变成 0001 ,也就是十进制中的数字 1 (又变回去了!)

如果你认真看的话,你会看到 2 的幂和移位有着千丝万缕的关系。如果二进制中只有一个位置出现了 1,并且初始二进制数为 0001 ,那么当对这个数左移 n 位就等于 2 的 n 次幂。

下面的表格是 2 的 n 次幂与十进制数字 1 向左移位 n 位的结果:

n 幂 (十进制) 幂 (二进制) 移位 (十进制) 移位 (二进制)
0 1 0001 1 0001
1 2 0010 2 0010
2 4 0100 4 0100
3 8 1000 8 1000
4 16 0001 0000 16 0001 0000
5 32 0010 0000 32 0010 0000
6 64 0100 0000 64 0100 0000
7 128 1000 0000 128 1000 0000
8 256 0001 0000 0000 256 0001 0000 0000
9 512 0010 0000 0000 512 0010 0000 0000
10 1,024 0100 0000 0000 1,024 0100 0000 0000
11 2,048 1000 0000 0000 2,048 1000 0000 0000

通过此表我们可以观察到 2 的 n 次幂与十进制数字 1 左移 n 位后的结果一致。

同时移位还有一个妙用。当你的 乘数 y 或者 除数 y 满足 2 的 n 次幂时,就能使用移位来代替乘法或者除法运算。公式使用到了二进制对数 (Binary logarithm),并且设定被乘数 / 被除数为 x

对于乘法来说:

xlog2yx \ll \log_2{y}

对于除法来说:

xlog2yx \gg \log_2{y}

假设我们要做乘法:

17×6417 \times 64

先计算乘数 y 的二进制对数

log264=6\log_2{64} = 6

最后执行左移

17617 \ll 6

无论是通过乘法运算还是左移,最终的结果都是 1,088 。除法道理一样,就不过多赘述了

Bitwise Flag 的开始

进入到正题,是不是松了一口气?不过如果你早就对二进制和逻辑运算掌握的不错,或许你已经跳到这来了。

Bitwise Flag 正是使用二进制和逻辑运算来实现对于一系列的布尔值存储。继续我们天气现象作为例子。现在我们已经有了以下的天气现象:

  • 晴天
  • 下雨
  • 下雪
  • 刮风
  • 打雷
  • 闪电

并且给他们一个唯一的二进制值

天气现象 二进制 十进制 2 的 n 次幂 左移表达
晴天 0001 1 0 1 << 0
下雨 0010 2 1 1 << 1
下雪 0100 4 2 1 << 2
刮风 1000 8 3 1 << 3
打雷 0001 0000 16 4 1 << 4
闪电 0010 0000 32 5 1 << 5

如果以 C 作为示例,可以使用宏或者枚举 (Enum) 来定义

#ifndef SUN
#define SUN 1 << 0
#endif // !SUN

#ifndef RAIN
#define RAIN 1 << 1
#endif // !RAIN

#ifndef SNOW
#define SNOW 1 << 2
#endif // !SNOW

#ifndef WIND
#define WIND 1 << 3
#endif // !WIND

#ifndef THUNDER
#define THUNDER 1 << 4
#endif // !THUNDER

#ifndef LIGHTNING
#define LIGHTNING 1 << 5
#endif // !LIGHTNING
enum WeatherEnum
{
    SUN = 1 << 0,
    RAIN = 1 << 1,
    SNOW = 1 << 2,
    WIND = 1 << 3,
    THUNDER = 1 << 4,
    LIGHTNING = 1 << 5
};

赋予

赋予可以分为单个和多个。当涉及到多个状态赋予时,会使用到逻辑或 (OR)

单个赋予非常简单,只需要将一个整数变量赋值相应的数字即可。如:

int current_weather = SUN; // 目前的十进制值为 1, 二进制 0001, 移位表达 1 << 0

多个赋予将会用到逻辑或 (OR) 的特性来将二进制中不同位置的 1 替换掉原有的 0 ,变更为开启的状态。

int current_weather = RAIN | SNOW; // 目前的十进制值为 6, 二进制 0110

在上方我们定义了 Rain0010 或十进制的 2,而 Snow0100 或十进制的 4

在解释逻辑运算的地方解释过,逻辑或中只要出现一个 True (或者 1) 那么结果就为 True (或者 1),否则为 False (或者 0)

在对 00100100 做逻辑或运算的时候会发生下面的结果:

     0010    => RAIN       
 OR  0100    => SNOW       
------------               
     0110    => RAIN & SNOW

0110 的结果就相当于代表雨天的二进制 0010 和代表雪天的二进制 0100 都被打开了。这就是多项赋值。

如果要实现雨夹雪,还出现刮风打雷闪电的效果,其道理也是一样的。

int current_weather = RAIN | SNOW | WIND | THUNDER | LIGHTNING; // 目前的十进制值为 62, 二进制 0011 1110
     0000 0010     => RAIN                                    
     0000 0100     => SNOW                                    
     0000 1000     => WIND                                    
     0001 0000     => THUNDER                                 
 OR  0010 0000     => LIGHTNING                               
-----------------                                             
     0011 1110     => RAIN & SNOW & WIND & THUNDER & LIGHTNING

检查

检查某个条件的状态为 True (或者 1) 还是 False (或者 0) 可以通过逻辑与 (AND) 来实现。透过将

逻辑与的特性是只要出现一个 False (或者 0),结果为 False (或者 0),否则为 True (或者 1)。我们先来看一个最基本的检查。假设回归到一开始只有晴天,并且检查目前是否是晴天:

int current_weather = SUN; // 目前的十进制值为 1, 二进制为 0001, 移位表达 1 << 0

然后将 current_weather 和要检查的 SUN 做和运算

注意,由于 C 和其他部分语言当中的 == 运算符优先级高于 & ,因此需要使用括号将 current_weather & SUN 括起来进行优先运算

if ((current_weather & SUN) == SUN)
{
    printf("晴天\n"); // 这里会执行,因为 0001 AND 0001 一定等于 0001
}

运算过程如下:

     0001    => current_weather
 AND 0001    => SUN            
------------                   
     0001    => SUN            

过了几天,天空乌云密布,下起了雨还刮起了风。我们的 current_weather 变成了:

int current_weather = RAIN | WIND; // 目前的十进制值为 10, 二进制值为 1010

此时想要去检查是否在下雨和刮风,则可以使用:

    if (current_weather & SUN == SUN)
    {
        printf("晴天\n"); // 不会执行
    }

    if ((current_weather & RAIN) == RAIN)
    {
        printf("下雨\n"); // 会执行
    }

    if ((current_weather & WIND) == WIND)
    {
        printf("刮风\n"); // 会执行
    }

运算过程如下:

检查晴天时

     1010    => current_weather
 AND 0001    => SUN            
------------                   
     0000    => 0 ( NOT SUN )  
     
检查下雨时

     1010    => current_weather
 AND 0010    => RAIN           
------------                   
     0010    => RAIN           
     
检查刮风时

     1010    => current_weather
 AND 1000    => WIND           
------------                   
     1000    => WIND           

移除

移除则是将为 True (或者 1) 的值变更为 False (或者 0),这是通过逻辑异或 (XOR) 来实现。

逻辑异或的特性为当两个变量相同时为 False (或者 0),不同时为 True (或者 1)。

衔接上面的例子:

int current_weather = RAIN | WIND; // 目前的十进制值为 10, 二进制值为 1010

雨停了,但还是在刮风:

current_weather = current_weather ^ RAIN; // 目前的十进制值为 8, 二进制值为 1000
if (current_weather & SUN == SUN)
{
    printf("晴天\n"); // 不会执行
}

if ((current_weather & RAIN) == RAIN)
{
    printf("下雨\n"); // 不会执行
}

if ((current_weather & WIND) == WIND)
{
    printf("刮风\n"); // 会执行
}

计算过程如下:

     1010    => current_weather
 XOR 0010    => RAIN           
------------                   
     1000    => WIND ONLY      

结束

到这里,对于 Bitwise Flag 这种数据结构的基本原理与用法已经阐述完毕。这种结构的用途之广泛也不仅仅限于相关的属性存储。只要有良好的声明以及规范,每一位 (Bit) 都可以代表截然不同,毫不相关的属性。

有趣的例子, Discord

Discord 的 API 权限管理使用了 Bitwise Flag 的设计,有兴趣可以到 Discord Developer Portal 看看。他们一共划分了 50 个不同的权限,即从 1 << 0 一直到 1 << 49 。562,949,953,421,312 是一个很大的整数呢 ( 笑 )

Written by:
Jimmy
Keywords:
Bitwise Flag, 数据结构, 位运算, 二进制, 数学