65.9K
CodeProject 正在变化。 阅读更多。
Home

将位运算应用于位域作为原始 SIMD

Patrice T
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.81/5 (30投票s)

2022 年 4 月 3 日

CPOL

17分钟阅读

viewsIcon

54251

downloadIcon

628

如何将位运算应用于位域作为原始 SIMD

目录

  1. 引言
  2. 位函数
    1. 位 AND OR XOR
    2. 位 NOT
    3. 位左移和右移
  3. 奇偶判断
    1. 经典方法：取模
    2. 位运算：掩码
  4. 乘以/除以 2
    1. 经典解决方案
    2. 位运算解决方案
  5. 计算设置为 1 的位数
    1. 经典方法：逐位检查
    2. 位运算解决方案
  6. 连续的 1
    1. 经典方法：逐位检查
    2. 位运算解决方案
  7. 格雷码
  8. 浮点数编码
  9. 处理巨大的位数组
  10. 霍夫曼压缩
    1. 编码
    2. 解码
  11. N 皇后问题
    1. 经典解决方案
    2. 位运算解决方案
    3. 两个版本的基准测试
  12. 康威生命游戏
    1. 经典方法：单细胞
    2. 位运算：并行处理
    3. 两个版本的基准测试
  13. 五词 Wordle 问题
    1. 字母到位图转换
    2. 加载单词文件
    3. 组合五个单词
  14. 关注点
  15. 链接
  16. 历史

引言

位运算是非常基础且快速的处理器指令，它们是通过对数据应用逻辑运算符来实现的，但方式是我们大多数人都不熟悉的。

位运算的使用主要分为两大类：

  • 数据拆分/组合：例如，浮点数值是打包在二进制值中的三个部分的组合，访问各个部分需要进行一些拆分。
  • 位域上的 SIMD：对位域的每个位应用相同的操作。康威生命游戏是完美的例子。

问题在于，使用位运算需要一定的专业知识来了解何时有利可图，以及如何构建一个利用它们的算法。

操作成本

这是一个小型的操作成本表

操作 (Operation) 32 位操作数成本 64 位操作数成本 注释
整数除法
整数取模		 16 + 附加开销 32 + 附加开销 成本为每 2 位 1 个时钟周期
当数据宽度加倍时，需要加倍的时钟周期。
O(n)=n
整数乘法 5 + 附加开销 6 + 附加开销 当数据宽度加倍时，需要多 1 个时钟周期。
O(n)= log(n)
加法
减法		 1 1 对于任何数据宽度，成本都是恒定的
O(n)= 1
位运算
AND, OR, SHIFT...		 1 1 对于任何数据宽度，成本都是恒定的
O(n)= 1

在本文中，大 O 表示法指的是数据的大小（以位为单位）。

位函数

从单个位的角度来看，位运算符主要与逻辑运算符（AND, OR, NOT）相同。

区别在于，逻辑运算独立地应用于值（变量/寄存器）的每个位。这导致最多可以同时进行 64 次逻辑运算，而无需诉诸多线程。

位 AND OR XOR

这些是二元运算符（2 个操作数）。XOR 通常不作为逻辑运算符提供。

A B A AND B A OR B A XOR B
0011 0101 0001 0111 0110

位运算解决方案的成本为 O(n)= 1，逻辑解决方案的成本为 O(n)= n。

	// BitWise.cpp
	// And operator Bitwise
	C = A & B;
	// And operator Logical
	for (int i = 0; i < ISize; i++)
		CA[i] = (AA[i] && BA[i]);
	Print("A and B    = ", C, "A[] and B[]= ", CA);

	// Or operator Bitwise
	C = A | B;
	// Or operator Logical
	for (int i = 0; i < ISize; i++)
		CA[i] = (AA[i] || BA[i]);
	Print("A or B     = ", C, "A[] or B[] = ", CA);

	// Xor operator Bitwise
	C = A ^ B;
	// Xor operator Logical
	for (int i = 0; i < ISize; i++)
		CA[i] = ((AA[i] == 0) != (BA[i] == 0));
	Print("A xor B    = ", C, "A[] xor B[]= ", CA);

Bitwise.cpp 在 Bitwise.zip 中.

// Result
A          = 0b00110010011110110010001111000110
AA[]       = 0b00110010011110110010001111000110

B          = 0b01100100001111001001100001101001
BA[]       = 0b01100100001111001001100001101001

A and B    = 0b00100000001110000000000001000000
A[] and B[]= 0b00100000001110000000000001000000

A or B     = 0b01110110011111111011101111101111
A[] or B[] = 0b01110110011111111011101111101111

A xor B    = 0b01010110010001111011101110101111
A[] xor B[]= 0b01010110010001111011101110101111

A 和 B 是整数，并应用了位运算。AA 和 BA 是整数数组，每个整数包含 1 位，并应用了逻辑运算。结果相同。

位 NOT

NOT 是一个一元运算符（1 个操作数）。

A NOT A
01 10

位运算解决方案的成本为 O(n)= 1，逻辑解决方案的成本为 O(n)= n。

	// BitWise.cpp
	// Not operator Bitwise
	C = ~A;
	// Not operator Logical
	for (int i = 0; i < ISize; i++)
		CA[i] = (!AA[i]);
	Print("not A      = ", C, "not A[]    = ", CA);

Bitwise.cpp 在 Bitwise.zip 中.

// Result
A          = 0b00110010011110110010001111000110
AA[]       = 0b00110010011110110010001111000110

not A      = 0b11001101100001001101110000111001
not A[]    = 0b11001101100001001101110000111001

A 是一个整数，并应用了位运算。AA 是一个整数数组，每个整数包含 1 位，并应用了逻辑运算。结果相同。

位左移和右移

移位运算符将位移动给定的位数，它们基本上是乘以或除以 2 的幂。

A B A 左移 B A 右移 B
0101 1 01010 00010
0101 2 10100 00001

位运算解决方案的成本为 O(n)= 1，逻辑解决方案的成本为 O(n)= n。

	// BitWise.cpp
	// Shift operator Bitwise
	C = A << 1;
	// Shift operator Logical
	CA[0] = 0;
	for (int i = 0; i < ISize - 1; i++)
		CA[i + 1] = (AA[i]);
	Print("A << 1     = ", C, "A[] << 1   = ", CA);

	// Shift operator Bitwise
	C = A << 2;
	// Shift operator Logical
	CA[0] = 0;
	CA[1] = 0;
	for (int i = 0; i < ISize - 2; i++)
		CA[i + 2] = (AA[i]);
	Print("A << 2     = ", C, "A[] << 2   = ", CA);

Bitwise.cpp 在 Bitwise.zip 中.

// Result
A          = 0b00110010011110110010001111000110
AA[]       = 0b00110010011110110010001111000110

A << 1     = 0b01100100111101100100011110001100
A[] << 1   = 0b01100100111101100100011110001100

A << 2     = 0b11001001111011001000111100011000
A[] << 2   = 0b11001001111011001000111100011000

A 是一个整数，并应用了位运算。AA 是一个整数数组，每个整数包含 1 位，并应用了逻辑运算。结果相同。

奇偶判断

通常，我们想知道一个整数是奇数还是偶数。

对于人类来说，它是十进制的，我们只需看个位数的值。

对于计算机来说，它是二进制的，个位也做同样的事情，如果位=0，则是偶数，否则是奇数。

位运算解决方案的成本为 O(n)= 1，数学解决方案（取模）的成本为 O(n)= n。

经典方法：取模

经典解决方案是获取整数除法的余数，即模运算。

int IsOdd(int X) {
	return (X % 2); // Modulo
}

int IsEven(int X) {
	return 1-(X % 2); // Modulo
}

位运算：掩码

位运算解决方案是掩码个位。内联代码甚至可以提高效率。

int IsOdd(int X) {
	return (X & 1); // Mask
}

int IsEven(int X) {
	return 1-(X & 1); // Mask
}

乘以/除以 2、4、8

乘法和除法是非常好的通用操作，但对于 2 的幂次方的运算，位运算解决方案更有效。

对于计算机来说，乘以/除以 2、4、8 就像我们人类乘以/除以 10、100、1000 一样。

位运算解决方案的成本为 O(n)= 1，数学解决方案（除法、取模）的成本为 O(n)= n，（乘法）为 O(n)= log(n)。

经典解决方案

int Mult2(int X) {
	return (X * 2); // Multiplication
}

int Mult4(int X) {
	return (X * 4); // Multiplication
}

int Mult8(int X) {
	return (X * 8); // Multiplication
}

int Div2(int X) {
	return (X / 2); // Division
}

int Div4(int X) {
	return (X / 4); // Division
}

int Div8(int X) {
	return (X / 8); // Division
}

int Mod2(int X) {
	return (X % 2); // Modulo
}

int Mod4(int X) {
	return (X % 4); // Modulo
}

int Mod8(int X) {
	return (X % 8); // Modulo
}

位运算解决方案

int Mult2(int X) {
	return (X << 1); // Shift Left
}

int Mult4(int X) {
	return (X << 2); // Shift Left
}

int Mult8(int X) {
	return (X << 3); // Shift Left
}

int Div2(int X) {
	return (X >> 1); // Shift Right
}

int Div4(int X) {
	return (X >> 2); // Shift Right
}

int Div8(int X) {
	return (X >> 3); // Shift Right
}

int Mod2(int X) {
	return (X & 0b0001); // Mask
}

int Mod4(int X) {
	return (X & 0b0011); // Mask
}

int Mod8(int X) {
	return (X & 0b0111); // Mask
}

计算设置为 1 的位数

一个经典的数学问题：计算一个整数中设置为 1 的位数。

经典方法：逐位检查

经典解决方案逐位计数。成本取决于数据的位大小 O(n)=n。

	int BitsCnt(unsigned long int Bits) {
	// Extracting bits with modulos and divisions
    int Cnt=0;
    do {
        Cnt += Bits % 2;
        Bits = Bits / 2;
    }
    while (Bits != 0)
    return Cnt;
}
	int BitsCnt(unsigned long int Bits) {
	// Extracting bits with basic birwise operations
    int Cnt=0;
    do {
        Cnt += Bits & 1;
        Bits = Bits >> 1;
    }
    while (Bits != 0)
    return Cnt;
}

位运算解决方案

通过一个巧妙的位运算解决方案，每当数据大小加倍时，解决方案就增加一个步骤，这是位运算的 SIMD 用法。成本取决于数据位大小的对数 O(n)=log(n)。

	int BitsCnt(unsigned long int Bits) {
	// Bitwise solution for 32 bits integer
    Bits= (Bits & 0x55555555) + ((Bits >> 1) & 0x55555555);
    Bits= (Bits & 0x33333333) + ((Bits >> 2) & 0x33333333);
    Bits= (Bits & 0x0f0f0f0f) + ((Bits >> 4) & 0x0f0f0f0f);
    Bits= (Bits & 0x00ff00ff) + ((Bits >> 8) & 0x00ff00ff);
    Bits= Bits + (Bits >>16);
    return Bits & 0xff;
}

最长的连续 1

我最近遇到了一个快速问题，其中有人在询问是否可以加快其算法：这段 C 代码能缩短并保持相同的复杂度吗？[^]

这段代码是关于在二进制整数中找到最长的连续 1。

经典方法：逐位检查

在这个解决方案中，逐位检查。

这段代码循环的次数取决于最左边设置为 1 的位的位，并且循环包含除法/取模。成本取决于数据的大小 O(n)=n。

int LargestRunof1(int n){
    int count=0,max=0; 
    while(n>0)
        {
        if(n%2==1) // Modulo
            count++;
        else
            {
            if(count>max)
                max=count;
            count=0;
        }
        n/=2; // Division
    }
    if(count>max)
        max=count;
    return max;
}

提问者提供的源代码.

位运算解决方案

在位运算解决方案中，对每个位同时执行相同的操作，这是 SIMD。

这段代码循环的次数取决于最长连续 1 的长度。在最坏情况下（所有位都设置为 1），成本为 O(n)= n。

// Code of my solution
int LargestRunof1(int n){
    int max=0,Tmp; 
    Tmp= n;
    while(n>0)
        {
        max++;
        Tmp >>= 1; // Shift
        n &= Tmp; // and Mask
    }
    return max;
}
// Improved code
int LargestRunof1(int n){
    int max=0; 
    while(n>0)
        {
        max++;
        n &= (n >> 1); // Shift and Mask
    }
    return max;
}

格雷码

尽管普通大众知之甚少，但格雷码的使用非常广泛。在几乎所有具有由处理器控制的运动部件的设备中，格雷码都用于传感器，该传感器指示该部件的位置。此类设备包括数控机床 (CNC)、机械臂、3D 打印机等。

如果你有一只机械臂，你想知道每个肘部的角度，而不仅仅是折叠或展开，你需要一个传感器来获取那个角度。如果使用简单的二进制编码，只要你处于特定位置，事情就能完美运行，但如果你正好处于位置 2 和 3 之间，传感器输出 2 或 3 取决于某个阈值，如果你正好处于位置 3 和 4 之间，问题就出现了，因为 3 和 4 之间有 3 位翻转，你无法确定这些位是否会在同一阈值下翻转。这会导致出现 3 7 5 4 这样的序列，因为阈值问题。

格雷码是一种解决方案，因为二进制值被重新排序，使得任何连续值之间只有一个位会翻转。

一个使用 3 位格雷编码的轮子。
格雷码 - 维基百科[^]		 
List of binary values and their Gray encoding
    Binary  Gray
 0  0b0000  0b0000
 1  0b0001  0b0001
 2  0b0010  0b0011
 3  0b0011  0b0010
 4  0b0100  0b0110
 5  0b0101  0b0111
 6  0b0110  0b0101
 7  0b0111  0b0100
 8  0b1000  0b1100
 9  0b1001  0b1101
10  0b1010  0b1111
11  0b1011  0b1110
12  0b1100  0b1010
13  0b1101  0b1011
14  0b1110  0b1001
15  0b1111  0b1000
	// Gray encode Bitwize
	C = A ^ (A >> 1);
	// Gray encode Logical
	CA[31] = AA[31];
	for (int i = ISize - 2; i >= 0; i--)
		CA[i] = (AA[i + 1] == 0) != (AA[i] == 0);
	Print("Gray(A)    = ", C, "Gray(A[])  = ", CA);

	// convert a Gray coded 32 bits integer to its binary value
	// Gray decode Bitwize
	C ^= C >> 16;
	C ^= C >> 8;
	C ^= C >> 4;
	C ^= C >> 2;
	C ^= C >> 1;
	// Gray decode Logical
	for (int i = ISize - 2; i >= 0; i--)
		CA[i] = (CA[i + 1] == 0) != (CA[i] == 0);
	Print("DeGray(A)  = ", C, "DeGray(A[])= ", CA);

Bitwise.cpp 在 Bitwise.zip 中.

A          = 0b00110010011110110010001111000110
AA[]       = 0b00110010011110110010001111000110

Gray(A)    = 0b00101011010001101011001000100101
Gray(A[])  = 0b00101011010001101011001000100101

DeGray(A)  = 0b00110010011110110010001111000110
DeGray(A[])= 0b00110010011110110010001111000110

正如在位运算解决方案中可以看到的，编码和解码同时在每个位上进行，这是 SIMD。

最流行的使用格雷码的设备可能是机械鼠标。

格雷码来自（3 个）轮子和（5 个）传感器。
轮子由填充部分和孔组成，每个轮子有两个传感器，传感器之间的移位为 0.25 序列，以获得格雷码输出。
文件：鼠标机构图.svg - 维基百科[^]

浮点数编码

一个浮点数由 3 部分组成，都打包在一个整数中。如果需要访问某个特定部分，就需要用到位运算。

浮点运算 - 维基百科[^]

在 C 语言中，基本上有两种方法可以访问这些部分：一种是使用位域结构，另一种是使用位运算。区别在于源代码层面，位域结构隐藏了技术细节，但在底层，使用的是位运算。

#include <stdio.h>

/*
Bitmap of a float 32 bits in an integer
33      22 
10      32                     0
SEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM
Sign
 Exponent
         Mantisa
*/

union MyFloat {
    unsigned int rawDataRep;
    float floatRep;
    struct {
        unsigned m: 23;  // Mantisa 23 bits
        unsigned e: 8;   // Exponent 8 bits
        unsigned s: 1;   // Sign 1 bit
    }
    componentesRep;
};

void printFP(union MyFloat mf) {
    unsigned int Sign, Exp, Man, Sew;
    printf ("Float: %f\nSign: %i Mantisa: 0x%08x Exponent: %i\nInteger: 0x%08x.\n",
            mf.floatRep, (int) mf.componentesRep.s,
            (unsigned int) mf.componentesRep.m, (int) mf.componentesRep.e,
            mf.rawDataRep);
            
    Sign= mf.rawDataRep >> 31;
    Exp= (mf.rawDataRep >> 23) & 0xff;
    Man= mf.rawDataRep & 0x7fffff;
    Sew= (Sign << 31) | (Exp << 23) | Man;
    printf ("Bitwise\nSign: %i Mantisa: 0x%08x Exponent: %i\nInteger: 0x%08x\n\n",
            Sign, Man, Exp, Sew);
}

void main() {
    union MyFloat mf;
    mf.floatRep = 355.0/113.0;
    printFP(mf);

    mf.floatRep = 355.0/113.0 * 4;
    printFP(mf);

}</stdio.h>

Float.cpp 在 Bitwise.zip 中.

Float: 3.141593
Sign: 0 Mantisa: 0x00490fdc Exponent: 128
Integer: 0x40490fdc.
Bitwise
Sign: 0 Mantisa: 0x00490fdc Exponent: 128
Integer: 0x40490fdc

Float: 12.566372
Sign: 0 Mantisa: 0x00490fdc Exponent: 130
Integer: 0x41490fdc.
Bitwise
Sign: 0 Mantisa: 0x00490fdc Exponent: 130
Integer: 0x41490fdc

处理巨大的位数组

在文章《整数分解：令人头疼的素数列表》中，我描述了一种压缩巨大素数列表的方法，该解决方案涉及一个巨大的位数组。

通过使用一个 30 的轮子（在文章《整数分解：试除法算法》中讨论），我得出结论，每 30 的切片只有 8 个可能的素数，这是通过移除 2、3 和 5 的倍数的结果。

由于一个数字要么是素数要么不是素数，一个单独的位可以存储这个信息，而 8 位正好是一个字节。我们很幸运，因为它简化了处理，但也可以处理大于 8 的值。

数组的构建方式如下。示例代码生成要粘贴到头文件中的数组。

// encode Prime Numbers as C array
void TD_EncodeArray(int Max) {
	long long Wheel[] = { 6, 4, 2, 4, 2, 4, 6, 2, 0 };
	long long Cand = 1;
	cout << "Encodage liste nombres premiers compressée" << endl;
	cout << "{";
	while (Cand < Max) {
		int Code = 0;
		int Index = 1;
		int Ind = 0;
		do {
			if ((TD_SRW(Cand) == Cand) && (Cand != 1)) {
				Code |= Index; // It is a prime, set the bit accordingly
			}
			Cand += Wheel[Ind];
			Index = Index << 1;
			Ind++;
		} while (Wheel[Ind] != 0);
		cout << "0x";
		cout << setfill('0') << setw(2) << hex << Code << ",";
	}
	cout << "0}" << dec << endl;
}

源代码和下载文件在文章《整数分解：令人头疼的素数列表》中[^]。

下面是如何使用位运算 AND 检索信息。对位置为 1 的位进行简单的掩码就可以知道它是否是素数。在示例代码中，一个头文件将高达 1,000,000 的素数编码在一个大小为 33,334 个字符的数组中。

// IsPrime taking advantage of long list of primes table
// returns 1 if prime, returns 0 otherwise
int IsPrimeLP(MyBigInt Cand) {
	const unsigned long long Wheel[] = { 6, 4, 2, 4, 2, 4, 6, 2, 0 };
	const unsigned long long WOffset[] = { 1, 7, 11, 13, 17, 19, 23, 29, 0 };
	if (Cand <= EPrimesMax) {
		Count = 1;
		// Cand is within list of primes
		long long x = Cand / WSize; // position in wheel list
		long long y = Cand % WSize; // offset in wheel
		for (int Index = 0; WOffset[Index] != 0; Index++) {
			if (WOffset[Index] == y) {
				return ((EPrimes[x] >> Index) & 0x01);
			}
		}
		if (Cand == 2)
			return 1;
		else if (Cand == 3)
			return 1;
		else if (Cand == 5)
			return 1;
		else
			return 0; // multiple of 2, 3 or 5
	}
	// Search a Factor
	return (TD_SRLPW(Cand) == 1);
}

源代码和下载文件在文章《整数分解：令人头疼的素数列表》中[^]。

霍夫曼压缩

虽然 RLE 压缩流由字节组成，但霍夫曼压缩流由位组成。因此，在使用霍夫曼压缩时，需要将位流转换为字节，并在解压缩时反过来操作。

霍夫曼编码 - 维基百科[^]

这是示例句子“code project for those who code”的霍夫曼树。

示例代码中的树的翻译。请注意，霍夫曼码必须从右到左读取。

struct Huffman {
	char Letter;
	int Freq;
	int Code;
	int Len;
};

string Sentence = "code project for those who code";

// Huffman codes are read from right to left
Huffman HTree[] = { { 'o', 6, 0b00, 2 }, { 'c', 3, 0b010, 3 }, { 'r', 2, 0b0110, 4 }, 
			{ 't', 2, 0b1110, 4 }, { 'p', 1, 0b00001, 5 }, { 'j', 1, 0b10001, 5 },
			{ 'd', 2, 0b1001, 4 }, { 'e', 4, 0b101, 3 }, { 'h', 2, 0b0011, 4 },
			{ 'w', 1, 0b01011, 5 }, { 'f', 1, 0b011011, 6 }, { 's', 1, 0b111011, 6 },
			{ ' ', 6, 0b111, 3 } };
int HTreeLen = 13;

Huffman.cpp 在 Bitwise.zip 中.

对于编码/解码，需要使用一个变量（缓冲区），其大小至少为 8 位（一个字节）+ 最长的霍夫曼码（此处为 6 位），因此至少需要 16 位。

编码

我们将霍夫曼码连接到一个缓冲区中，当有 8 位或更多位时，我们将字节保存到流中。连接是通过位移位和位 OR 完成的。我们将部分组合在一起。

	// Huffman encode
	cout << "Huffman encoded by bytes" << endl;
	unsigned char HList[20];
	unsigned int HBuf = 0, HOffset = 0, HIndex = 0;
	for (int i = 0; Sentence[i] != 0; i++) {
		// search matching letter
		for (l = 0; Sentence[i] != HTree[l].Letter; l++)
			;
		HBuf |= HTree[l].Code << HOffset;
		HOffset += HTree[l].Len;
		if (HOffset > 7) {
			HList[HIndex] = HBuf & 0xff;
			HIndex++;
			for (int j = 7; j >= 0; j--) {
				cout << (((HBuf & 0xff) >> j) & 1);
			}
			cout << " ";
			HBuf >>= 8;
			HOffset -= 8;
		}
	}
	// end of stream
	HBuf |= 1 << HOffset;
	HList[HIndex] = HBuf & 0xff;

	HIndex++;
	HOffset += 1;
	for (int j = 7; j >= 0; j--) {
		cout << (((HBuf & 0xff) >> j) & 1);
	}
	cout << endl << endl;

Huffman.cpp 在 Bitwise.zip 中.

编码结果

Letters match in Huffman table   : 
c   o  d    e       p     r    o  j     e   c   t        f      o  r        t    h    o  s      e       w     h    o      c   o  d    e   
010 00 1001 101 111 10000 0110 00 10001 101 010 0111 111 110110 00 0110 111 0111 1100 00 110111 101 111 11010 1100 00 111 010 00 1001 101 

Huffman encoded by bytes
00100010 11111011 01100000 11000100 11001010 10111111 01100001 11110111 01100001 11101111 11010111 01110000 10010001 00001101

字节流的构建方式如下

Huffman encoding Steps
0000000000000000 = Huffman Buffer reset
             010 = Huffman code
             010 = Huffman code Shifted
0000000000000010 = Merged to buffer
              00 = Huffman code
           00    = Huffman code Shifted
0000000000000010 = Merged to buffer
            1001 = Huffman code
       1001      = Huffman code Shifted
0000000100100010 = Merged to buffer
        00100010 = Byte to save
0000000000000001 = Huffman Buffer updated
             101 = Huffman code
            101  = Huffman code Shifted
0000000000001011 = Merged to buffer
             111 = Huffman code
         111     = Huffman code Shifted
0000000001111011 = Merged to buffer
...

解码

对于解码，我们需要一个与编码时相同大小的变量（缓冲区）。对于解码，我们使用位运算来拆分输入流。

	// Huffman decode
	cout << "Huffman decode" << endl;
	HBuf = 0;
	HOffset = 0;
	int i = 0;
	while (i < HIndex || HBuf > 1) {
		// load buffer when necessary
		while (i < HIndex && HOffset < 25) {
			HBuf |= ((unsigned int) HList[i]) << HOffset;
			HOffset += 8;
			i++;
		}
		// find next Huffman code
		for (l = 0; l < HTreeLen; l++) {
			int Mask = ~(0xffffffff << HTree[l].Len);
			if ((HBuf & Mask) == HTree[l].Code) {
				// Matched
				break;
			}
		}
		if (l < HTreeLen) {
			// Matched
			cout << HTree[l].Letter;
			HBuf >>= HTree[l].Len;
			HOffset -= HTree[l].Len;
		} else {
			// not matched
			cout << "Error";
		}
	}
	cout << endl << endl;

Huffman.cpp 在 Bitwise.zip 中.

字节流的解码方式如下

Huffman decoding Steps
0000000000000000 = Huffman Buffer
        00100010 = Read byte
        00100010 = Shift
0000000000100010 = Merge in Huffman Buffer
        11111011 = Read byte
11111011         = Shift
1111101100100010 = Merge in Huffman Buffer
             010 = Matched code
0001111101100100 = Huffman Buffer
              00 = Matched code
0000011111011001 = Huffman Buffer
            1001 = Matched code
0000000001111101 = Huffman Buffer
        01100000 = Read byte
 01100000        = Shift
0011000001111101 = Merge in Huffman Buffer
             101 = Matched code
0000011000001111 = Huffman Buffer
             111 = Matched code
0000000011000001 = Huffman Buffer
           00001 = Matched code
0000000000000110 = Huffman Buffer
        11000100 = Read byte
    11000100     = Shift
...

N 皇后问题

在 N 皇后问题中，我们需要以一种互相不攻击的方式放置国际象棋皇后。

八皇后问题 - 维基百科[^]

每次想在新的一行放置皇后时，都需要检查哪些位置可用，并跳过所有被先前皇后锁定的位置。

经典解决方案

在经典解决方案中，对于棋盘上的每个皇后，我们保存其列号，而对于下一行的皇后，我们必须检查所选列是否被先前皇后锁定。我们必须检查所有先前的皇后才能知道一列是否被锁定。

int IsFree(int Row, int Col, int *Board) {
	// per row, check vertical and diagonals for Queens in previous rows
	for (int Scan = 0; Scan < Row; Scan++) {
		Checks++;
		if (Board[Scan] == Col)
			return 0;
		Checks++;
		if (Board[Scan] == Col + (Row - Scan))
			return 0;
		Checks++;
		if (Board[Scan] == Col - (Row - Scan))
			return 0;
	}
	return 1;
}

void NQueensClas(int Size) {
	// search first solution
	// Backtracking
	int Board[Size + 1];
	int Row = 0;
	cout << endl << "NQueen Classical Backtraking " << Size << endl;
	Checks = 0;
	Board[0] = 0;
	while (Row < Size) {
		while (Board[Row] < Size) {
			if (IsFree(Row, Board[Row], Board)) {
				break;
			} else {
				Board[Row]++;
			}
		}
		if (Board[Row] < Size) { // New Queen OK
			Row++;
			Board[Row] = 0;
		} else { // Backtrack
			Row--;
			Board[Row]++;
		}
	}
	cout << "First Solution ";
	for (Row = 0; Row < Size; Row++) {
		cout << Board[Row] + 1 << " ";
	}
	cout << endl;
	cout << "Checks: " << Checks << endl;
}

NQueens.cpp 在 Bitwise.zip 中.

位运算解决方案

通过位运算，我们不再仅仅保存皇后的列号，而是使用变量作为位图，并在放置皇后时将与皇后所在列匹配的位设置为 1。

位运算利用了一个事实：对于给定的行，所有先前的皇后都是固定的，并且锁定的列的掩码可以一次性计算出来。

整个兴趣在于，当我们开始新的一行时，前一行的位图显示了所有先前皇后的位置，仅仅设置最后一个皇后的位就可以得到一个显示所有皇后位置的位图。

void NQueensBit(int Size) {
	// search first solution Bitwise operations
	// Backtracking
	int Board[Size + 1][5];
	// Column 0 is Queen position
	// Column 1 is bitfield synthesis of locked positions
	// Column 2 is bitfield of locked positions in diagonal
	// Column 3 is bitfield of locked positions in vertical
	// Column 4 is bitfield of locked positions in diagonal

	int Row = 0;
	cout << endl << "NQueen Bitwise Backtraking " << Size << endl;
	Checks = 0;
	Board[0][0] = 0;
	Board[0][1] = 0;
	Board[0][2] = 0;
	Board[0][3] = 0;
	Board[0][4] = 0;
	while (Row < Size) {
		while (Board[Row][0] < Size) {
			Checks++;
			if (Board[Row][1] & (1 << Board[Row][0])) { // a single check tells if the position is locked or not
				Board[Row][0]++;
			} else {
				break;
			}
		}
		if (Board[Row][0] < Size) { // New Queen OK
			Row++;
			Board[Row][0] = 0;
			// Setting mask for locked positions in new row
			Board[Row][2] = (Board[Row - 1][2] | (1 << Board[Row - 1][0])) << 1;	// Update Diagonal
			Board[Row][3] = Board[Row - 1][3] | (1 << Board[Row - 1][0]);			// Update Vertical
			Board[Row][4] = (Board[Row - 1][4] | (1 << Board[Row - 1][0])) >> 1;	// Update Diagonal
			Board[Row][1] = Board[Row][2] | Board[Row][3] | Board[Row][4];			// Combine them

		} else { // Backtrack
			Row--;
			Board[Row][0]++;
		}
	}
	cout << "First Solution ";
	for (Row = 0; Row < Size; Row++) {
		cout << Board[Row][0] + 1 << " ";
	}
	cout << endl;
	cout << "Checks: " << Checks << endl;

	for (Row = 0; Row < Size; Row++) {
		for (int Scan = 1; Scan < 5; Scan++) {
			for (int Col = 0; Col < Size; Col++) {
				cout << ((Board[Row][Scan] >> Col) & 1);
			}
			cout << " ";
		}
		cout << endl;
	}
}

NQueens.cpp 在 Bitwise.zip 中.

对于每一行，我们跟踪三个方向（垂直和两个对角线）上的所有先前皇后，然后将三个位图组合起来以获得当前行的所有约束。将组合的约束与新皇后想要的位置进行单个掩码操作，就可以知道是否被锁定。

The Bitmap stack for the first solution of size 8
Combined Diag \   Vertical Diag /
00000000 00000000 00000000 00000000 // Constraint for first queen, all positions are free
11000000 01000000 10000000 00000000 // Constraint with first queen in column 1
10111100 00100100 10001000 00010000 // Constraint with second queen in column 5
10111011 00010010 10001001 00100010 // Constraint with third queen in column 8
11001111 00001011 10001101 01001100 // ...
11111101 00010101 10101101 11011000 
10111111 00001011 10101111 10110100 
11101111 00100101 11101111 11101000 

Or by Queen numbers
Combined Diag \   Vertical Diag /
00000000 00000000 00000000 00000000 // Constraint for first queen, all positions are free
11000000 01000000 10000000 00000000 // Constraint with first queen in column 1
10122200 00100200 10002000 00020000 // Constraint with second queen in column 5
10212033 00010020 10002003 00200030 // Constraint with third queen in column 8
12004443 00001042 10002403 02004300 // ...
25553404 00050104 10502403 25043000 
50535666 00005016 10502463 50430600 
77706563 00700501 17502463 74306000

两个版本的基准测试

8、15、25 和 31 皇后问题执行结果：请注意，每种解决方案需要检查新皇后的所需位置与所有先前皇后的次数。

NQueen Classical Backtracking 8
First Solution 1 5 8 6 3 7 2 4 
Checks: 6,440 Time taken by function: 0 microseconds
NQueen Bitwise Backtracking 8
First Solution 1 5 8 6 3 7 2 4 
Checks: 876 Time taken by function: 0 microseconds

NQueen Classical Backtracking 15
First Solution 1 3 5 2 10 12 14 4 13 9 6 15 7 11 8 
Checks: 268,453 Time taken by function: 1,000 microseconds
NQueen Bitwise Backtracking 15
First Solution 1 3 5 2 10 12 14 4 13 9 6 15 7 11 8 
Checks: 20,280 Time taken by function: 0 microseconds

NQueen Classical Backtracking 25
First Solution 1 3 5 2 4 9 11 13 15 19 21 24 20 25 23 6 8 10 7 14 16 18 12 17 22 
Checks: 26,215,802 Time taken by function: 62,003 microseconds
NQueen Bitwise Backtracking 25
First Solution 1 3 5 2 4 9 11 13 15 19 21 24 20 25 23 6 8 10 7 14 16 18 12 17 22 
Checks: 1,216,775 Time taken by function: 11,000 microseconds

NQueen Classical Backtracking 31
First Solution 1 3 5 2 4 9 11 13 15 6 18 23 26 28 31 25 27 30 7 17 29 14 10 8 20 12 16 19 22 24 21
Checks: 10,956,081,667 Time taken by function: 22,742,300 microseconds
NQueen Bitwise Backtracking 31
First Solution 1 3 5 2 4 9 11 13 15 6 18 23 26 28 31 25 27 30 7 17 29 14 10 8 20 12 16 19 22 24 21
Checks: 408,773,285 Time taken by function: 2,689,153 microseconds

这是每个尺寸的运行时间，看看位运算算法有多快。

大小 经典检查次数 位运算检查次数 经典运行时间 位运算运行时间 经典/位运算
8 皇后 6,440 876 0 毫秒 0 毫秒 7.35
15 皇后 268,453 20,280 1 毫秒 1 毫秒 13.24
25 皇后 26,215,802 1,216,775 80 毫秒 14 毫秒 21.55
31 皇后 10,956,081,667 408,773,285 23,414 毫秒 2,796 毫秒 26.80

这两个程序遵循相同的算法，并尝试放置皇后的次数相同。由于在位运算解决方案中，只需一次检查就知道一列是否可用，因此与经典解决方案的区别在于先前的皇后堆栈。

表中最后一列显示了确定一列是否可用的平均检查次数。

对于这两个版本，对于 N 大小的棋盘，算法在最坏情况下需要 N 行乘以 N 列乘以 1 次检查。对于位运算版本，检查是常数时间完成的；对于经典版本，检查取决于行数 N。对于经典版本，O(n)=n^3；对于位运算版本，O(n)=n^2。

康威生命游戏

康威生命游戏（GoL）涉及一个由活细胞和死细胞组成的巨大网格。在计算下一代时，相同的操作集被应用于所有处于活动状态的细胞。

一个简单的优化：在游戏区域周围添加一行额外的空单元格，并将边界单元格作为普通单元格处理，这比不断检查边界单元格的成本要低。

在示例程序 GoL.cpp 中，输入数据是 RLE 压缩的：RLE：对人类友好的压缩[^]

经典方法：单细胞

在一个 n*m 的网格中，对于每个单元格，需要检查 8 个邻近单元格。对于 320*240 大小的网格，需要 76,800 次循环。每次循环有 11 次操作。

inline int CellGetN(int Row, int Col) {
	//return (FieldNext[Row / FieldBits][Col] >> (Row % FieldBits)) & 1;
	return (FieldNext[Row >> 6][Col] >> (Row & 0x3f)) & 1;
}

// Next generation Classical
void LNext() {
	Field2N(); // Copy of Field 2 FieldNext
	for (int Row = 1; Row < FieldRows + 2; Row++) {
		for (int Col = 1; Col < FieldCols + 2; Col++) {
			int Cnt;
			Cnt = CellGetN(Row - 1, Col - 1);
			Cnt += CellGetN(Row - 1, Col);
			Cnt += CellGetN(Row - 1, Col + 1);

			Cnt += CellGetN(Row , Col - 1);
			Cnt += CellGetN(Row , Col + 1);

			Cnt += CellGetN(Row + 1, Col - 1);
			Cnt += CellGetN(Row + 1, Col);
			Cnt += CellGetN(Row + 1, Col + 1);

			if (Cnt == 3 || (Cnt == 2 && CellGetN(Row, Col))) {
				// CellSet(Row, Col);
				Field[Row >> 6][Col] |= (unsigned long long) 1 << (Row & 0x3f);
			} else {
				// CellClear(Row, Col);
				Field[Row >> 6][Col] &= ~((unsigned long long) 1 << (Row & 0x3f));
			}
		}
	}
}

GoL.cpp 在 Bitwise.zip 中.

碰巧我的编译器（默认设置）不会优化对整数数组中位元的访问。FieldBits 是常数 64，但我的编译器不会自动将除法和取模优化为位运算解决方案。所以我做了两个版本的函数来访问单个位。

inline int CellGetN(int Row, int Col) {
	//	Classical acces to a bit in an array of integers
	return (FieldNext[Row / FieldBits][Col] >> (Row % FieldBits)) & 1;
	// Bitwise version
	//return (FieldNext[Row >> 6][Col] >> (Row & 0x3f)) & 1;
}

位运算：并行处理

在康威生命游戏的情况下，位运算允许并行处理，这确实是单指令多数据 (SIMD)。使用 64 位字长，我们一次处理多达 62 个单元格。

位运算存在两个主要问题：

  1. 没有位运算的加法，我们必须设计一系列位运算来让我们知道每个单元格周围有多少个邻居。
  2. 由于游戏区域大于处理器字长，我们需要设计一个逻辑来连接字。对于一个 240 列的游戏区域，我使用 4 个 64 位整数来存储一行，60 位存储游戏区域，2 位用于同一行整数之间的连接。

对于 320*240 大小的网格，只需要 1,280 次循环，因为下一代是由 60 个单元格的切片计算的。对于每个 60 个单元格的块，计算邻居需要 45 次操作，即每个单元格 0.75 次操作。

由于游戏区域被切片到整数中，我们使用位运算，我们需要预留位来连接切片，因为我们需要知道切片的左边和右边的位来计算下一代。

/* Contains of an integer in bitwise solution
 00LPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPR
 0 is unused bits
 L 1 bit linking to left
 P 60 bits of playfield
 R 1 bit linking to right
 */
// Next generation Bitwise
void LNext() {
	unsigned long long Bit0, Bit1, Bit2, Carry0, Carry1;
	// Link slices
	for (int Row = 0; Row < FieldQWords; Row++) {
		for (int Col = 0; Col < FieldCols + 2; Col++) {
			unsigned long long Tmp = Field[Row][Col] & (long long) 0x1ffffffffffffffe;
			if (Row != 0) {
				Tmp = Tmp | ((Field[Row - 1][Col] >> 60) & 1);
			}
			if (Row != 3) {
				Tmp = Tmp | ((Field[Row + 2][Col] & 2) << 60);
			}
			FieldNext[Row][Col] = Tmp;
		}
	}
	// Calc next generation
	for (int Row = 0; Row < FieldQWords; Row++) {
		for (int Col = 1; Col < FieldRows + 1; Col++) {
			Bit0 = FieldNext[Row][Col - 1] << 1;

			Bit1 = Bit0 & FieldNext[Row][Col - 1];
			Bit0 = Bit0 ^ FieldNext[Row][Col - 1];

			Bit1 = Bit1 | (Bit0 & (FieldNext[Row][Col - 1] >> 1));
			Bit0 = Bit0 ^ (FieldNext[Row][Col - 1] >> 1);

			Carry0 = Bit0 & (FieldNext[Row][Col] << 1);
			Bit0 = Bit0 ^ (FieldNext[Row][Col] << 1);
			Carry1 = Bit1 & Carry0;
			Bit1 = Bit1 ^ Carry0;
			Bit2 = Carry1;

			Carry0 = Bit0 & (FieldNext[Row][Col] >> 1);
			Bit0 = Bit0 ^ (FieldNext[Row][Col] >> 1);
			Carry1 = Bit1 & Carry0;
			Bit1 = Bit1 ^ Carry0;
			Bit2 = Bit2 | Carry1;

			Carry0 = Bit0 & (FieldNext[Row][Col + 1] << 1);
			Bit0 = Bit0 ^ (FieldNext[Row][Col + 1] << 1);
			Carry1 = Bit1 & Carry0;
			Bit1 = Bit1 ^ Carry0;
			Bit2 = Bit2 | Carry1;

			Carry0 = Bit0 & FieldNext[Row][Col + 1];
			Bit0 = Bit0 ^ FieldNext[Row][Col + 1];
			Carry1 = Bit1 & Carry0;
			Bit1 = Bit1 ^ Carry0;
			Bit2 = Bit2 | Carry1;

			Carry0 = Bit0 & (FieldNext[Row][Col + 1] >> 1);
			Bit0 = Bit0 ^ (FieldNext[Row][Col + 1] >> 1);
			Carry1 = Bit1 & Carry0;
			Bit1 = Bit1 ^ Carry0;
			Bit2 = Bit2 | Carry1;

			Field[Row][Col] = (FieldNext[Row][Col] | Bit0) & Bit1 & ~Bit2;
		}
	}
}

GoL.cpp 在 Bitwise.zip 中.

两个版本的基准测试

这是 1000 代的运行时间。可以看到位运算算法虽然繁琐但回报丰厚。

经典运行时间 经典运行时间
位运算访问		 位运算运行时间
5,100 毫秒 2,313 毫秒 48 毫秒

可以看到，在经典版本上，使用位运算来访问整数数组中的一个位对运行时有巨大影响，至少在编译器默认设置下是这样。

五词 Wordle 问题

最近，我在 YouTube 上看到一个视频，其中有人被问到是否可以用 25 个不重复的字母组成五个单词。他的初始解决方案非常糟糕。

第一个视频：你能找到：二十五个不重复字母组成的五个五字母单词吗？ - YouTube[^]
第二个视频：有人将我的代码提高了 40,832,277,770% - YouTube[^]

为了解决这个问题，我们需要不断检查一个字母是否已经被之前的单词使用。在朴素解决方案中，字母是逐个检查的，对于第五个单词，有 20 * 5 个字母需要检查才能知道第五个单词是否正确。在位运算解决方案中，我们使用一个位域，每个字母用 1 位表示，要判断第五个单词是否正确，只需一次比较。

字母到位图转换

为了利用位运算的优势，需要将字母转换为位图。

Uppercase letters A-Z are ASCII encoded from 65-to 90
Lowercase letters a-z are ASCII encoded from 97-to 122
BitNumber = Letter & 0x1f; // This formula gives the Letter Number in alphabet
Mask = 1 << (Letter & 0x1f); // This formula sets the matching bit
			       zyxwvutsrqponmlkjihgfedcba
'a' =>		0b00000000000000000000000000000010
'z' =>		0b00000100000000000000000000000000
"panel" =>	0b00000000000000010101000000100010

单词的位图在本文中称为掩码。

加载单词文件

我使用了视频链接中的一个单词文件，问题是该文件对什么是单词的定义非常松散。我不得不在读取文件时进行过滤。

  • 任何长度不是 5 个字符的单词都会被拒绝。
  • 任何包含非字母字符的单词都会被拒绝。
  • 任何包含大写字母的单词都会被拒绝，因为它们可能是缩写。
  • 任何包含重复字母的单词都会被拒绝。
  • 任何不包含元音的单词也会被拒绝。元音包括 'y'，因为“glyph”这个词。
  • 任何包含掩码（已经在单词列表中）的单词都会被拒绝，被视为字母异位词。
Anagrams:
			       zyxwvutsrqponmlkjihgfedcba
"panel" =>	0b00000000000000010101000000100010
"nepal" =>	0b00000000000000010101000000100010

// reads the wordfile
void MLit5() {
	ifstream Words("words.txt");
	string Line;
	//Sets a mask for fast detectiong of voyels
	int Voy = 0;
	Voy |= (1 << ('a' & 0x1f));
	Voy |= (1 << ('e' & 0x1f));
	Voy |= (1 << ('i' & 0x1f));
	Voy |= (1 << ('o' & 0x1f));
	Voy |= (1 << ('u' & 0x1f));
	Voy |= (1 << ('y' & 0x1f));
	
	if (Words.is_open()) {
		while (getline(Words, Line)) {
			FL++;
			if (Line.length() != 5) { // reject if length is not 5
				RLn++;
			} else {
				F5++;
				FA++;
				FD++;
				FLC++;
				int Mask = 0;
				int OK = 1;
				for (int Scan = 0; Scan < 5; Scan++) {
					if (isalpha(Line[Scan]) != 0) { // reject char is not alphabet
						if ((Line[Scan] & 0x60) == 0x40) { // reject if uppercase
							OK = 0;
							FLC--;
							RLt++;
							break;
						}
						int BSet = 1 << (Line[Scan] & 0x1f); // set bitmap for new letter
						if (Mask & BSet) { // reject if letter already seen
							OK = 0;
							FD--;
							RLD++;
							break;
						}
						Mask |= BSet; // add letter to mask
					} else {
						OK = 0;
						FA--;
						FD--;
						FLC--;
						RLt++;
						break;
					}
				}
				if (OK && (Mask & Voy)) { // reject if no voyel
					MSort(Mask, Line); // insert in sorted list
				}
			}
		}
		Words.close();

Mots5x5.cpp 在 Bitwise.zip 中.

插入排序，使用二分搜索添加新单词。

// insert word in sorted list
void MSort(int Mask, string Line) {
	if (MNb == 0) {
		MList[MNb].Mask = Mask;
		strcpy(MList[MNb].Mot, Line.data());
		MNb++;
	} else if (MList[MNb - 1].Mask < Mask) {
		MList[MNb].Mask = Mask;
		strcpy(MList[MNb].Mot, Line.data());
		MNb++;
	} else {
		// dichotomy search
		int Db = 0, Fn = MNb - 1;
		while (Db < Fn) {
			int Md = (Db + Fn) / 2;
			if (MList[Md].Mask < Mask) {
				Db = Md + 1;
			} else {
				Fn = Md;
			}
		}
		// insert in list if new word
		if (MList[Fn].Mask != Mask) {
			for (int Scan = MNb; Scan > Fn; Scan--) {
				MList[Scan].Mask = MList[Scan - 1].Mask;
				strcpy(MList[Scan].Mot, MList[Scan - 1].Mot);
			}
			MList[Fn].Mask = Mask;
			strcpy(MList[Fn].Mot, Line.data());
			MNb++;
		}
	}
}

Mots5x5.cpp 在 Bitwise.zip 中.

单词文件过滤结果。

File Lines :466,551
Five letters Lines :22,950
Alphabet Only Lines :22,240
No UpperCase Letter Lines :13,052
No Duplicate Letter Lines :17,577
No Anagrams :5,334

组合五个单词

我使用一个非递归的回溯算法来构建 5 个单词的集合。嵌套了 5 个循环。

简单的位运算 AND 可以判断新单词的字母是否已在当前单词集合中使用。

				if ((Mask[1] & MList[Mot[2]].Mask) == 0) { // if no overlap
					Mask[2] = Mask[1] | MList[Mot[2]].Mask;// accept new word in set
// search sets of 5 words
void MLot() {
	int Mot[6], Mask[6];
	Mask[0] = 0;

	for (Mot[1] = 0; Mot[1] < MTop(Mask[0], 5); Mot[1]++) {
		MPick++;
		if ((Mask[0] & MList[Mot[1]].Mask) == 0) {
			Mask[1] = Mask[0] | MList[Mot[1]].Mask;

			for (Mot[2] = MBot(Mask[1], Mot[1]); Mot[2] < MTop(Mask[1], 4); Mot[2]++) {
				MPick++;
				if ((Mask[1] & MList[Mot[2]].Mask) == 0) {
					Mask[2] = Mask[1] | MList[Mot[2]].Mask;

					for (Mot[3] = MBot(Mask[2], Mot[2]); Mot[3] < MTop(Mask[2], 3); Mot[3]++) {
						MPick++;
						if ((Mask[2] & MList[Mot[3]].Mask) == 0) {
							Mask[3] = Mask[2] | MList[Mot[3]].Mask;

							for (Mot[4] = MBot(Mask[3], Mot[3]); Mot[4] < MTop(Mask[3], 2); Mot[4]++) {
								MPick++;
								if ((Mask[3] & MList[Mot[4]].Mask) == 0) {
									Mask[4] = Mask[3] | MList[Mot[4]].Mask;

									for (Mot[5] = MBot(Mask[4], Mot[4]); Mot[5] < MTop(Mask[4], 1); Mot[5]++) {
										MPick++;
										if ((Mask[4] & MList[Mot[5]].Mask) == 0) {
											PNb++;
											cout << PNb << " " << MList[Mot[1]].Mot << " " << MList[Mot[2]].Mot << " "
													<< MList[Mot[3]].Mot << " " << MList[Mot[4]].Mot << " "
													<< MList[Mot[5]].Mot;
											cout << " " << Mot[1] << " " << Mot[2] << " " << Mot[3] << " " << Mot[4]
													<< " " << Mot[5] << endl;
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

Mots5x5.cpp 在 Bitwise.zip 中.

单词集合搜索结果。

Start Search
1 chimb fjord vangs expwy klutz 107 750 3346 5142 5289
2 klong jambs chivw expdt furzy 411 1030 3907 4026 5331
3 klong chivw expdt jumby zarfs 411 3907 4026 4793 5243
4 fjord gucks vibex nymph waltz 750 2675 4074 4311 5299
5 fjord swack vibex glyph muntz 750 3663 4074 4290 5291
6 fjord chivw pbxes glaky muntz 750 3907 4010 4137 5291
7 fjord chivw pbxes mangy klutz 750 3907 4010 4200 5289
8 jambs gconv whilk expdt furzy 1030 3271 3502 4026 5331
9 jocks dwarf vibex glyph muntz 1162 3594 4074 4290 5291
10 gconv whilk expdt jumby zarfs 3271 3502 4026 4793 5243
Picked Words 25,714,697,452
Fini

找到 10 个集合。单词集合后面的数字是排序列表中的位置。选择的单词是构建单词集合时尝试的单词数量。

关注点

巧妙地使用位运算可以大大提高算法的效率，但其使用更加复杂，因为我们对这些操作不太熟悉。

历史

  • 2022 年 3 月 21 日：初稿
  • 2022 年 4 月 3 日：首次发布草稿
  • 2022 年 4 月 5 日：改进版
  • 2022 年 4 月 13 日：第二版：添加了康威生命游戏
  • 2022 年 6 月 13 日：第三版：改进
  • 2022 年 7 月 31 日：第四版：改进和更多示例
  • 2022 年 8 月 5 日：第五版：添加了处理巨大位数组的示例
  • 2022 年 8 月 20 日：第五版 5.1：源代码中的拼写错误
  • 2022 年 12 月 10 日：第六版：添加了 Wordle 单词的示例
© . All rights reserved.