6

这可能覆盖得很好，但我对这个主题一无所知，所以我将使用业余术语。假设我在搞乱一些条件，每个条件都在 int 中定义一组非零数字，让我们说 8 位 int。所以对于一个位，我可能有这个：

11XX00XX

说我想要所有有 1 的字节有 1，有 0 的有 0，而不关心 X。所以 11110000 或 11000010 满足了这一点，但 01110000 没有。很容易，对吧？对于算术条件，我只能想象有一些使用 ==、!=、>=、>、<= 或 < 与常数比较。所以我可以说：

X > 16

所以任何大于 16 的数字（00010000）。如果我想查找上述两个示例集中的所有数字怎么办？我可以通过查看它来判断任何以 100XX 结尾的数字都符合要求，因此相交的按位部分包括 11X100XX。然后我必须包括区域 111X00XX 以填充其上方的其余范围。对？虽然我认为对于其他情况，结果不会那么整齐，对吗？无论如何，对于任何这些算术条件与任何可能的按位条件，这背后的算法是什么。肯定有一般情况！

假设有一个，而且可能很明显，如果事情变得更复杂怎么办？如果我的按位要求变为：

11AA00XX

标有 A 的任何内容都必须相同。所以 110000XX 或 111100XX，但不是 111000XX。对于任意数量和任意位置的任意数量的相同位“类型”（A、B、C 等），通过算术比较解决交集的最佳方法是什么？有吗？

我认为这些按位运算是一种单一的比较运算/分支，就像算法的设置方式一样。所以也许一个是所有常量，当某个字节 B 01110000 与它们进行“与”运算时，结果为 00110000。所以那个常量区域，也就是我的“按位条件”，将是 X011XXXX，因为 X011XXXX AND 01110000 = 00110000 . 我所有的“按位条件”都是由 AND、OR 和 XOR 等运算的反转形成的。不确定是否会包含 NAND 之类的东西。这可能会限制实际可能的条件，也许？如果是这样，那么我不在乎那些类型的条件。

很抱歉解释的曲折尝试。我在做什么有名字吗？看起来它在 CS 中很受欢迎，所以一个名字可以让我读到一些关于这个主题的好书。但我主要是在寻找一个好的算法来解决这个问题。我最终将在交叉路口使用超过 2 个东西（可能有几十个或更多），所以解决它的方法可以很好地扩展将是一个巨大的优势。

4

5 回答 5

7

按位

好的，所以我们看一下按位运算，因为这是做你想做的最有效的方法。为清楚起见（和参考），转换为十进制的按位值是

00000001 =   1
00000010 =   2
00000100 =   4
00001000 =   8
00010000 =  16
00100000 =  32
01000000 =  64
10000000 = 128

现在，给定11XX00XX变量的位模式，x我们将执行以下检查：

x AND 128 == true
x AND 64  == true
x AND 8   == false
x AND 4   == false

如果所有这些条件都为真，则该值与模式匹配。本质上，您正在检查以下条件：

1XXXXXXX AND 10000000 == true
X1XXXXXX AND 01000000 == true
XXXX0XXX AND 00001000 == false
XXXXX0XX AND 00000100 == false

用编程语言的说法把它放在一起（我将使用 C#），你会寻找

if ((x && 128) && (x && 64) && !(x && 8) && !(x && 4))  
{
    // We have a match
}

对于更复杂的 11AA00XX 位模式，您将添加以下条件：

NOT ((x AND 32) XOR (x AND 16)) == true

这样做是首先检查x AND 32，根据 in 中该位的值返回 0 或 1 x。然后，它对另一位进行相同的检查，x AND 16. 该XOR操作检查位的差异，如果位不同则返回 1，如果位相同则返回 0。从那里开始，因为如果它们相同，我们想返回 1，我们NOT整个子句。如果位相同，这将返回 1。

算术

在算术方面，您会考虑使用除法和模运算的组合来隔离有问题的位。要使用除法，您首先要找到数字可以被除以的最大可能的 2 次方。换句话说，如果有x=65，则 2 的最高幂是 64。

一旦你完成了除法，你就可以使用模数来取除法后的余数。如上例所示，给定x=65, x MOD 64 == 1。使用该数字，您重复之前的操作，找到 2 的最高幂，然后继续直到模数返回 0。

于 2012-05-08T19:10:14.060 回答
7

扩展一下saluce的答案：

位测试

您可以构建测试模式，因此您不需要单独检查每一位（测试整数比测试一位更快，尤其是一次测试整数就像好）：

testOnes = 128 & 64 // the bits we want to be 1
testZeros = ~(8 & 4) // the bits we want to be 0, inverted

然后以这种方式执行测试：

if (!(~(x & testOnes) & testOnes) &&
    !(~(~x | testZeros))) {
  /* match! */
}

逻辑解释：

首先，在两者中testOnes，testZeros您都将感兴趣的位设置为 1，其余设置为 0。

testOnes testZeros
11000000 11110011

然后x & testOnes将我们不想测试的所有位清零（注意和之间的区别&：&&按位&执行逻辑AND运算，而&&对AND整数执行逻辑运算）。

testOnes
11000000
x        x & testOnes
11110000 11000000
11000010 11000000
01010100 01000000

现在我们测试为 1 的位最多可以是 1，但我们不知道它们是否都是 1：通过反转结果 ( ~(x & testOnes))，我们得到所有我们不关心的数字是 1 和位我们要测试的是 0（如果它们是 1）或 1（如果它们是 0）。

testOnes
11000000
x        ~(x & testOnes)
11110000 00111111
11000010 00111111
01010100 10111111

通过AND对它进行按位运算，testOnes如果感兴趣的位在 中全为 1，则我们得到 0 x，否则为非零。

testOnes
11000000
x        ~(x & testOnes) & testOnes
11110000 00000000
11000010 00000000
01010100 10000000

在这一点上，我们有： 0 如果我们想要测试 1 的所有位实际上都是 1，否则为非 0，因此我们执行一个逻辑NOT来将 0 变为true，将非 0 变为false。

x        !(~(x & testOnes) & testOnes)
11110000 true
11000010 true
01010100 false

零位的测试类似，但我们需要使用按位- OR( |)，而不是按位- AND( &)。首先，我们翻转x，因此应该为 0 的位变为应该为 1，然后OR-ing 将所有不感兴趣的位变为 1，同时保留其余位；所以在这一点上，如果应该是 0 的位x确实为 0，则我们有全 1，否则，我们将结果再次翻转以在第一种情况下得到 0，在第二种情况下得到非 0 . 然后我们应用逻辑NOT（!）将结果转换为true（第一种情况）或false（第二种情况）。

testZeros
11110011
x        ~x       ~x | testZeros ~(~x | testZeros) !(~(~x | testZeros))
11110000 00001111 11111111       00000000          true
11000010 00111101 11111111       00000000          true
01010100 10101011 11111011       00000100          false

注意：您需要意识到我们为每个测试执行了 4 次操作，所以总共 8 次。根据您要测试的位数，这可能仍然少于单独检查每个位。

算术测试

测试相等/差异很容易：XOR测试的数字 - 如果所有位都相等（因此数字相等），则为 0，如果至少有一位不同（因此数字不同），则为非 0。（应用NOT将相等的测试结果true，差异变为false。）

然而，为了测试不等式，你大部分时间都不走运，至少它适用于逻辑运算。您是正确的，可以通过逻辑运算（按位AND并测试 0）来检查 2 的幂（例如，您的问题中的 16），但是对于不是 2 的幂的数字，情况并非如此简单的。举个例子，让我们测试一下x>5：pattern 是 00000101，那么如何测试呢？如果它的前 5 个最高有效位为 1，则该数字更大，但 6 (00000110) 也更大，前 5 个位均为 0。

您可以做的最好的事情是测试该数字是否至少是该数字中最高 2 的幂的两倍（在上面的示例中为 5 的 4）。如果是，那么它比原来的大；否则，它必须至少与数字中的最高 2 次方一样多，然后对不太重要的位执行相同的测试。如您所见，操作数是根据测试数中 1 位的数量动态变化的。

链接位

这XOR是你的朋友：XOR如果两个位相同，则为 0，否则为 1。

我不知道执行测试的简单方法，但以下算法应该会有所帮助：

假设您需要 bits b1, ...,bn相同（全 1 或全 0），然后将所有其他位清零（参见AND上面的逻辑-），然后隔离测试模式中的每个位，然后将它们排列在相同的位置（为方便起见，我们将其设为最低有效位）。然后XOR-ing其中两个然后XOR-ing第三个结果等。将在每个奇数步产生一个偶数，如果原始数字中的位相同，则在每个偶数步产生奇数。您需要在每一步都进行测试，因为对于大量要测试的链接位，仅测试最终结果可能是不正确的。

testLinks
00110000
x        x & testLinks
11110000 00110000
11000010 00000000
01010100 00010000

x        x's bits isolated isolated bits shifted
11110000 00100000          00000001
         00010000          00000001
11000010 00000000          00000000
         00000000          00000000
01010100 00000000          00000000
         00010000          00000001

x        x's bits XOR'd result
11110000 00000000       true (1st round, even result)
11000010 00000000       true (1st round, even result)
01010100 00000001       false (1st round, odd result)

注意：在类 C 语言中，XOR运算符是^.

注意：如何将位对齐到相同的位置？位移。Shift-left ( <<) 将所有位向左移动，“丢失”最高有效位并将 0“引入”最低有效位，实质上是将数字乘以 2；右移>>（ .

于 2012-05-09T10:44:23.273 回答
1

TLDR saluce 的回答：

按位检查分别考虑单个位，而算术检查将所有位一起考虑。确实，它们符合 2 的幂，但不符合任何任意数字。

因此，如果两者都有，则需要实施两组检查。

32 位 int 的所有可能值的存储空间有点大，因此您必须每次都检查它们。只需确保您使用短路来消除重复检查，例如 x > 5 || x > 3。

于 2012-05-09T11:13:18.423 回答
1

您已经定义了一个体面的 DSL 来指定掩码。我会编写一个解析器来读取该掩码并执行特定于每个唯一字符的操作。

AABBB110 = 面罩

步骤 1：将所有唯一字符提取到数组 [01AB] 中。您可以省略“X”，因为不需要任何操作。

第 2 步：遍历该数组，将您的文本掩码处理为单独的位掩码，每个唯一字符一个位掩码，将该字符位置的位替换为 1，所有其他位替换为 0。

Mask_0 = 00000001 = 0x01
Mask_1 = 00000110 = 0x06
Mask_A = 11000000 = 0xC0
Mask_B = 00111000 = 0x38

第 3 步：将每个掩码传递给下面定义的相应函数。

boolean mask_zero(byte data, byte mask) {
  return (data & mask) == 0;
}

boolean mask_one(byte data, byte mask) {
  return (data & mask) == mask;
}

boolean mask_same(byte data, byte mask) {
  byte masked=data & mask;
  return (masked==0) || (masked==mask);
}
于 2012-05-13T01:13:03.027 回答
1

您希望结果集采用什么格式？算术集（我们称之为 A）和按位集（我们称之为 B）都具有可快速测试的优点和易于迭代的优点。但是这些定义中的每一个都可以定义另一个不能定义的东西，所以它们的交集需要完全是另外的东西。

我要做的是分别处理测试和迭代。通过简单地使用逻辑“与”将两个集合转换为任意数学表达式（按位集合可以转换为一些按位运算，正如其他海报所描述的），可以轻松创建易于测试的定义。这很容易推广到任何类型的集合 - 只需存储对两个父集合的引用，当被问到两个集合中是否有一个数字时，只需检查两个父集合。

然而，一个任意的数学表达式根本不容易迭代。对于迭代，最简单的方法是对集合 B 进行迭代（可以通过仅更改不受集合约束的位来完成），并允许集合 A 约束结果。如果 A 使用 > 或 >=，则向下迭代（从最大数开始）并在 false 时停止以获得最大效率；如果 A 使用 < 或 <=，则向上迭代（从最小数字开始）并在 false 时停止。如果 A 使用 ==，那么只有一个数字需要检查，如果 A 使用 !=，那么任何一个方向都可以（但你不能在 false 时停止）。

请注意，按位集的行为类似于可索引的数字数组 - 例如，由 11XX00XX 定义的按位集可以视为索引范围从 0000 到 1111 的数组，索引的位适合相应的槽。这使得在集合上向上或向下迭代变得容易。集合 A 可以以类似的方式被索引，但是因为它很容易成为一个无限集合（除非受您机器的 int 值的限制，尽管它不一定是，即 BigInteger），所以迭代不是最安全的事情超过。

于 2012-05-13T15:07:20.587 回答