回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>这个问题与<a href="https://stackoverflow.com/questions/25524678/bejeweled-bit-board-applying-gravity">this</a>有关。你知道吗</p>
<p>设<code>x</code>为8位整数。我将从左到右对位进行编号,因为我们就是这样读的。如果我想得到第三位和第五位,把它们放在第一位和第二位,其他的都是零,我可以有<code>f(x) = (5*x) & 0b11000000</code>。更简洁地说:</p>
<pre><code>00a0b000 -> ab000000 | f_0b00101000(x) = (5*x) & 0b11000000
</code></pre>
<p>但是,如果我希望第五位、第六位和第八位位于前三位,<code>f(x)</code>是不同的:</p>
<pre><code>000ab0cd -> abcd0000 | f_0b00011011(x) = ((x << 3) & 0b11000000) | (x << 4)
</code></pre>
<p>注意,<code>f_n(x)</code>中的<code>n</code>表示我关心哪些位。<code>n</code>可以有任何8位的值。有没有一些<code>x</code>的公共函数(和一些参数)可以将所有需要的位推到左边?而且,这应该是快速的,所以我宁愿只使用位运算。你知道吗</p>
<hr/>
<p>假设我处理的是3位整数。你知道吗</p>
<pre><code>000 -> 000 | f_0(x) = (1*x) & 0
00a -> a00 | f_1(x) = (4*x) & 4
0a0 -> a00 | f_2(x) = (2*x) & 4
0ab -> ab0 | f_3(x) = (2*x) & 6
a00 -> a00 | f_4(x) = (1*x) & 4
a0b -> ab0 | f_5(x) = (3*x) & 6
ab0 -> ab0 | f_6(x) = (1*x) & 6
abc -> abc | f_7(x) = (1*x) & 7
</code></pre>
<p>这些函数都可以组合到<code>f(x, m, a) = (m*x) & a</code>中,我可以创建一个查找表,我可以通过索引从<code>n</code>中获取<code>m</code>和<code>a</code>的值:</p>
<pre><code>t = [(1, 0), (4, 4), (2, 4), (2, 6), (1, 4), (3, 6), (1, 6), (1, 7)]
</code></pre>
<p>所以<code>f_n(x)</code>变成<code>f(x, *t[n])</code>。我认为<code>f(x, m, a) = (m*x) & a</code>是3位的最佳选择。3位的原始版本是:</p>
<pre><code>f(x, a, b, c, d, e, f) = ((x & a) << b) |
((x & c) << d) |
((x & e) << f)
</code></pre>
<p>朴素函数的运算数为8,最优(?)的运算数为2一个。现在8位的朴素函数是:</p>
<pre><code>f(x, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) = ((x & a) << b) |
((x & c) << d) |
((x & e) << f) |
((x & g) << h) |
((x & i) << j) |
((x & k) << l) |
((x & m) << n) |
((x & o) << p)
</code></pre>
<p>此指令中有25个操作。有没有可能降到7或8左右,甚至更低?你知道吗</p>