use*_*342 4 math computer-science bit-manipulation
这可能是很好的覆盖,但我对这个问题一无所知,所以我将使用业余术语.假设我正在搞乱一些条件,每个条件都在int中定义一组非零数字,我们只说8位int.所以对于一个按位,我可能有这个:
11XX00XX
说我希望所有字节都有1s,其中有1s,0s有0,并且不关心Xs.所以11110000或11000010实现了这一点,但01110000却没有.够容易吧？对于算术条件,我只能想象使用==,!=,> =,>,<=或<与常数进行比较.所以我可以说:
X > 16
所以任何大于16的数字(00010000).如果我想查找上述示例集中的所有数字,该怎么办？我可以通过观察它看出任何以100XX结尾的数字都符合要求,因此交叉点的按位部分包括11X100XX.然后我必须包括区域111X00XX以填充其上方的其余范围.对？虽然我认为对于其他情况,它不会如此整洁,正确吗？无论如何,对于任何这些算术条件与任何可能的那些按位算法相比,这背后的算法是什么.当然必须有一般情况!
假设有一个,它可能是显而易见的,如果事情变得更复杂怎么办？如果我的按位要求变为:
11AA00XX
标有A的任何东西必须相同.所以110000XX或111100XX,但不是111000XX.对于任意数量和任何位置的任意数量的相同位"类型"(A,B,C等),通过某种算术比较求解交点的最佳方法是什么？有吗？
我正在考虑这些按位运算是一种单一的比较运算/分支,就像算法的设置一样.所以也许一个是所有常数,当某个字节B 01110000与它们进行AND运算时,会产生00110000.因此,常数区域,即我的"按位条件",将是X011XXXX,因为X011XXXX AND 01110000 = 00110000我所有的"按位条件"都是通过像AND,OR和XOR这样的操作的反转形成的.不确定是否会包含像NAND这样的东西.这可能会限制实际可能的条件,也许？如果是这样,那么我不关心那些类型的条件.
很抱歉蜿蜒的尝试解释.我正在做什么名字？看起来它在CS中已经很好用了,所以一个名字可以让我对这个主题进行一些很好的阅读.但我主要只是寻找一个好的算法来解决这个问题.我最终会在十字路口使用两个以上的东西(可能有几十个或更多),所以解决它的方法可以很好地扩展.
好的,所以我们看一下按位操作,因为这是做你想要的最有效的方法.为清楚起见(和参考),转换为十进制的按位值是
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,根据该位的值返回0或1 x.然后,它对另一位进行相同的检查x AND 16.该XOR操作检查位的差异,如果位是不同的则返回1,如果位相同则返回0.从那里开始,因为我们想要返回1,如果它们是相同的,我们NOT整个条款.如果位相同,则返回1.
在算术方面,您将看到使用除法和模运算的组合来隔离有问题的位.要与除法一起工作,首先要找到数字可以除以的最大二次幂.换句话说,如果你有x=65,那么2的最高功率是64.
完成除法之后,然后使用模数来取除除法后的余数.如上例所示,给出x=65,x MOD 64 == 1.使用该数字,您可以重复之前的操作,找到最高的2的幂,并继续直到模数返回0.
扩展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
此时，我们得到：如果要测试1的所有位实际上都是1，则为0，否则为非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，否则为非全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被测试的数字为1 －如果所有位都相等（因此数字相等），则为0；如果至少一位不同（因此数字不同），则为0。（应用NOT将相等的测试结果转换true为false。）
但是，要测试不平等性，至少在大多数情况下，您运气不佳，因为它适用于逻辑运算。您是正确的，可以使用逻辑运算（按位运算AND并测试0）来检查2的幂（例如，您的问题中为16 ），但是对于不是2的幂的数字，则不是这样简单。例如，让我们测试一下x>5：模式为00000101，那么如何测试？如果它的第一五个最高有效位为1，则该数字更大，但是当前五个位均为0时，该数字也更大，为6（00000110）。
最好的办法是测试该数字是否至少是该数字中最高幂乘2的两倍（在上面的示例中为4表示5）。如果是，则大于原始大小；否则，它必须至少等于数量中的最高2的幂，然后对次要位进行相同的测试。如您所见，操作数是动态的，取决于测试编号中1位的数量。
链接位
在这里，XOR是您的朋友：XOR如果两个位相同，则产生0，否则产生1。
我不知道执行测试的简单方法，但是以下算法应该有所帮助：
假设您需要将位b1... ... bn保持相同（全为1或全为0），然后将所有其他位清零（请参见AND上面的逻辑），然后隔离测试模式中的每个位，然后将它们排列在相同的位置（为方便起见，将其设为最低有效位）。然后XOR，将其中的两个相加，然后XOR将第三个与结果相加，以此类推。如果原始位数相同，则在每个奇数步将产生偶数，在每个偶数步将产生奇数。您将需要在每个步骤进行测试，因为对于大量要测试的链接位，仅测试最终结果可能是不正确的。
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运算符为^。
注意：如何将位线排列到相同位置？移位。左移（<<）将所有位向左移动，“丢失”最高有效位，并将“ 0”引入最低有效位，实际上是将数字乘以2；shift-right（>>）的操作类似，向右移位，本质上是将整数除以2，但是，它会将相同的位“引入”到已经存在的最高有效位（因此保持负数为负） 。