用单个乘法提取位 [英] Extracting bits with a single multiplication
问题描述
我看到在
I saw an interesting technique used in an answer to another question, and would like to understand it a little better.
我们正在给予64位无符号整数，我们感兴趣的是以下位：
We're given an unsigned 64-bit integer, and we are interested in the following bits:
1.......2.......3.......4.......5.......6.......7.......8.......
具体而言，我们想将其移动到前八的位置，像这样：
Specifically, we'd like to move them to the top eight positions, like so:
12345678........................................................
我们不关心由指示位的值。，和他们没有被preserved。
We don't care about the value of the bits indicated by ., and they don't have to be preserved.
借助解决方案是屏蔽掉不需要的位，并通过 0x2040810204081 <繁衍的结果/ code>。这一点，因为它的出现，是卓有成效的。
The solution was to mask out the unwanted bits, and multiply the result by 0x2040810204081. This, as it turns out, does the trick.
如何一般是这种方法吗？可以这种技术可用于提取的比特的任意子集？如果没有，如何做一个数字出来的方法是否适用于一组特定的位？
How general is this method? Can this technique be used to extract any subset of bits? If not, how does one figure out whether or not the method works for a particular set of bits?
最后，如何总会有去寻找（一个？）正确的乘数提取给定的位？
Finally, how would one go about finding the (a?) correct multiplier to extract the given bits?
推荐答案
很有趣的问题，和聪明的把戏。
Very interesting question, and clever trick.
让我们来看看让操纵单个字节的一个简单的例子。使用无符号的8位为简单起见。想象一下，您的号码是 xxaxxbxx ，你想 ab000000 。
Let's look at a simple example of getting a single byte manipulated. Using unsigned 8 bit for simplicity. Imagine your number is xxaxxbxx and you want ab000000.
的溶液由两个步骤：一个位掩码，随后相乘。所述位掩码是一个简单的与运算，变成无趣位零。在上述情况下，你的面具将 00100100 ，结果 00a00b00 。
The solution consisted of two steps: a bit masking, followed by multiplication. The bit mask is a simple AND operation that turns uninteresting bits to zeros. In the above case, your mask would be 00100100 and the result 00a00b00.
现在困难的部分：即转成 AB ......
Now the hard part: turning that into ab.......
一个乘法是一堆移位和加操作。关键是要允许溢出转移开：我们不需要位，并把我们想要的在正确的地方。
A multiplication is a bunch of shift-and-add operations. The key is to allow overflow to "shift away" the bits we don't need and put the ones we want in the right place.
乘以4（ 00000100 ）将转移一切由2左，让你 a00b0000 。要获得 B 动起来，我们需要通过1乘以（保持在一个合适的位置）+ 4（将b向上）。这笔款项是5，与早期的4相结合，我们得到一个神奇的数字20，或 00010100 。原来是 00a00b00 屏蔽后;乘法得出：
Multiplication by 4 (00000100) would shift everything left by 2 and get you to a00b0000 . To get the b to move up we need to multiply by 1 (to keep the a in the right place) + 4 (to move the b up). This sum is 5, and combined with the earlier 4 we get a magic number of 20, or 00010100. The original was 00a00b00 after masking; the multiplication gives:
000000a00b000000
00000000a00b0000 +
----------------
000000a0ab0b0000
xxxxxxxxab......
从这个方法，你可以扩展到更大数量和更多的比特。
From this approach you can extend to larger numbers and more bits.
一个你问的是问题，这可以用任何位数做什么？我认为答案是否，除非你允许多个屏蔽操作，或数乘法。现在的问题是冲突的问题 - 在上述问题，例如，流浪B。试想一下，我们需要做的这一批像 xaxxbxxcx 。继早前的做法，你认为我们需要{X 2，X {1 + 4 + 16}} = X 42（哦 - 一切问题的答案！）。结果：
One of the questions you asked was "can this be done with any number of bits?" I think the answer is "no", unless you allow several masking operations, or several multiplications. The problem is the issue of "collisions" - for example, the "stray b" in the problem above. Imagine we need to do this to a number like xaxxbxxcx. Following the earlier approach, you would think we need {x 2, x {1 + 4 + 16}} = x 42 (oooh - the answer to everything!). Result:
00000000a00b00c00
000000a00b00c0000
0000a00b00c000000
-----------------
0000a0ababcbc0c00
xxxxxxxxabc......
正如你所看到的，它仍然有效，但才刚刚。他们这里的关键是，有足够的空间，我们要的位之间，我们可以挤一切。 ℃之后我不能添加第四位D正确，因为我会得到我的地方得到C + D的情况下，位可能携带，...
As you can see, it still works, but "only just". They key here is that there is "enough space" between the bits we want that we can squeeze everything up. I could not add a fourth bit d right after c, because I would get instances where I get c+d, bits might carry, ...
因此，没有正式的证据，我会回答你的问题的更有趣的部分如下：不，这不会对任何位数的工作，要提取N位，则需要（N-1）位之间的空间要提取，或者有额外的掩模乘步骤。
So without formal proof, I would answer the more interesting parts of your question as follows: "No, this will not work for any number of bits. To extract N bits, you need (N-1) spaces between the bits you want to extract, or have additional mask-multiply steps."
我可以为位之间必须有（N-1）个零规则是这样想的唯一的例外：如果你想提取两位是相邻的原对方，要保留他们以相同的顺序，那么你仍然可以做到这一点。而对于（N-1）规则的目的，他们算作两位。
The only exception I can think of for the "must have (N-1) zeros between bits" rule is this: if you want to extract two bits that are adjacent to each other in the original, AND you want to keep them in the same order, then you can still do it. And for the purpose of the (N-1) rule they count as two bits.
有另一种见解 - 由@Ternary下面的回答启发（见我的评论那里）。对于每一个有趣的一点，你只需要空间，需要去那里位需要尽可能多的零到它的权利。而且，它需要一样多的位的左边，因为它有导致位到左侧。因此，如果一比特b在正的位置m结束的话，就需要有m-1个零的其左侧，并且n-m的零到其右侧。特别是当位不是在原始数目，因为他们将在重新排序后的顺序相同，这是对原始标准的一个重要的改进。这种装置，例如，一个16位的字
There is another insight - inspired by the answer of @Ternary below (see my comment there). For each interesting bit, you only need as many zeros to the right of it as you need space for bits that need to go there. But also, it needs as many bits to the left as it has result-bits to the left. So if a bit b ends up in position m of n, then it needs to have m-1 zeros to its left, and n-m zeros to its right. Especially when the bits are not in the same order in the original number as they will be after the re-ordering, this is an important improvement to the original criteria. This means, for example, that a 16 bit word
a...e.b...d..c..
可移入
abcde...........
即使有三个其他人之间E和B之间只有一个空间，二D和C之间。无论发生在N-1？在这种情况下， A ... E 变成一块 - 他们都乘以1在正确的地方结束，所以我们得到了E对于免费 。同样如此为B和D（二需要三个位到右侧，D所需要的相同的三到其左边）。所以，当我们计算一个神奇的数字，我们发现有重复的：
even though there is only one space between e and b, two between d and c, three between the others. Whatever happened to N-1?? In this case, a...e becomes "one block" - they are multiplied by 1 to end up in the right place, and so "we got e for free". The same is true for b and d (b needs three spaces to the right, d needs the same three to its left). So when we compute the magic number, we find there are duplicates:
a: << 0 ( x 1 )
b: << 5 ( x 32 )
c: << 11 ( x 2048 )
d: << 5 ( x 32 ) !! duplicate
e: << 0 ( x 1 ) !! duplicate
显然，如果你在一个不同的顺序想这些数字，你将有进一步的空间他们。我们可以重新制定（N-1）规则：如果有这永远是可行的，至少（N-1）位之间的空间;或者，位如果订单在最后的结果是已知的，那么，如果一比特b在正的位置m结束时，它需要具有m-1个零到其左，纳米零到其正确的
Clearly, if you wanted these numbers in a different order, you would have to space them further. We can reformulate the (N-1) rule: "It will always work if there are at least (N-1) spaces between bits; or, if the order of bits in the final result is known, then if a bit b ends up in position m of n, it needs to have m-1 zeros to its left, and n-m zeros to its right."
@Ternary指出，这条规则并不完全工作，因为可以从加入只是到目标区域的右侧位进位 - 也就是，当我们正在寻找的位全部为一。我继续在16位字的五个紧凑位上面给的例子：如果我们开始与
@Ternary pointed out that this rule doesn't quite work, as there can be a carry from bits adding "just to the right of the target area" - namely, when the bits we're looking for are all ones. Continuing the example I gave above with the five tightly packed bits in a 16 bit word: if we start with
a...e.b...d..c..
为了简单起见，我将其命名为位位置 ABCDEFGHIJKLMNOP
我们要做的是数学
ABCDEFGHIJKLMNOP
a000e0b000d00c00
0b000d00c0000000
000d00c000000000
00c0000000000000 +
----------------
abcded(b+c)0c0d00c00
到现在为止，我们认为下面 ABCDE 什么（职位 ABCDE ）不会有问题，但事实上，作为@Ternary指出，如果 b = 1，C = 1，D = 1 然后（b + C）中位置˚F，这意味着（D + 1）位置˚F将携带有点进入电子 - 我们的结果是被宠坏。注意，空间的（在该例子 C ）兴趣无关紧要至少显著位的右侧，自乘法将导致用零填充从beyone所述至少显著位。
Until now, we thought anything below abcde (positions ABCDE) would not matter, but in fact, as @Ternary pointed out, if b=1, c=1, d=1 then (b+c) in position G will cause a bit to carry to position F, which means that (d+1) in position F will carry a bit into E - and our result is spoilt. Note that space to the right of the least significant bit of interest (c in this example) doesn't matter, since the multiplication will cause padding with zeros from beyone the least significant bit.
因此，我们需要修改我们的（M-1）/（N-M）的规则。如果有确切（NM）未使用的位向右（不包括在模式的最后一位 - 在上面的例子C）不止一位，那么我们需要加强规则 - 我们必须这样做反复！
So we need to modify our (m-1)/(n-m) rule. If there is more than one bit that has "exactly (n-m) unused bits to the right (not counting the last bit in the pattern - "c" in the example above), then we need to strengthen the rule - and we have to do so iteratively!
我们来看看不仅符合（NM）标准的位数，还以为是在（N-M + 1）等的那些让我们把他们的人数Q0（确切地纳米来下位），Q（N-M + 1），最多至Q（N-1）（N-1）。然后我们进行风险如果
We have to look not only at the number of bits that meet the (n-m) criterion, but also the ones that are at (n-m+1), etc. Let's call their number Q0 (exactly n-m to next bit), Q1 (n-m+1), up to Q(N-1) (n-1). Then we risk carry if
Q0 > 1
Q0 == 1 && Q1 >= 2
Q0 == 0 && Q1 >= 4
Q0 == 1 && Q1 > 1 && Q2 >=2
...
如果你看看这个，你可以看到，如果你写一个简单的数学EX pression
If you look at this, you can see that if you write a simple mathematical expression
W = N * Q0 + (N - 1) * Q1 + ... + Q(N-1)
和结果是 W＆GT; 2 * N ，那么你需要一个比特来增加RHS准则（N-M + 1）。在这一点上，操作是安全的，只要 W＆LT; 4 ;如果不工作，加大标准一多，等等。
and the result is W > 2 * N, then you need to increase the RHS criterion by one bit to (n-m+1). At this point, the operation is safe as long as W < 4; if that doesn't work, increase the criterion one more, etc.
我认为，按照上述将让你很长的路要走，以你的答案......
I think that following the above will get you a long way to your answer...
这篇关于用单个乘法提取位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
