我最近偶然发现了2048游戏.您可以通过在四个方向中的任意一个方向上移动它们来合并类似的图块,以制作"更大" 每次移动后,新的图块会出现在随机空位置,其值为2或4.当所有框都被填充并且没有可以合并图块的移动时,或者您创建值为的图块时,游戏会终止2048.

一,我需要遵循明确的战略来实现目标.所以,我想为它编写一个程序.

我目前的算法:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

我做的是在任何时候,我会尝试合并与价值观的瓷砖2和4,就是我努力2和4瓷砖,尽可能最小.如果我这样尝试,所有其他瓷砖自动合并,策略似乎很好.

但是,当我实际使用这个算法时,我只能在游戏结束前获得大约4000点.AFAIK的最高分数略高于20,000分,远高于我目前的分数.有比上面更好的算法吗？

我是一个只是为了好玩而编写代码的人,并没有在学术或专业环境中深入研究它,所以像这些按位运算符这样的东西真的让我感到厌烦.

我正在阅读一篇关于JavaScript的文章,它显然支持按位操作.我一直看到这个地方提到的这个操作,我试着去弄清楚究竟是什么,但我似乎根本没有得到它.那他们是什么？清楚的例子会很棒!:d

还有几个问题 - 按位运算的一些实际应用是什么？你何时可以使用它们？

有人可以用直观的方式解释strassen的矩阵乘法算法吗？我已经完成了(好了,试图通过)书中的解释和维基,但它没有点击楼上.网络上使用大量英语而非正式表示法等的任何链接也会有所帮助.是否有任何类比可以帮助我从头开始构建这个算法而不必记住它？

在汇编编程中,想要从寄存器的低位计算某些东西是相当普遍的,这些位不能保证将其他位置零.在像C这样的高级语言中,你只需将输入转换为小尺寸,让编译器决定是否需要分别将每个输入的高位归零,或者是否可以在输出之后切断结果的高位.事实.

这是为x86-64的(又名AMD64),出于各种原因尤其常见¹,其中的一些是存在于其它的ISA.

我将使用64位x86作为示例,但目的是询问/讨论2的补码和无符号二进制算法,因为所有现代CPU都使用它.(注意,C和C++不保证两个补码⁴,并且有符号溢出是未定义的行为.)

作为示例,考虑一个可以编译为LEA指令²的简单函数.(在X86-64 SysV的(Linux)的ABI ³,前两个函数参数是rdi和rsi,与在返回rax. int是一个32位的类型.)

; int intfunc(int a, int b) { return a + b*4 + 3; }
intfunc:
    lea  eax,  [edi + esi*4 + 3]  ; the obvious choice, but gcc can do better
    ret

gcc知道即使是负有符号整数,加法也只是从右到左,所以输入的高位不会影响进入的内容eax.因此,它保存了一个指令字节并使用 lea eax, [rdi + rsi*4 + 3]

哪些其他操作具有结果低位的这种属性而不依赖于输入的高位？

为什么它有效？

脚注

¹为什么x86-64频繁出现这种情况:x86-64有可变长度指令,其中额外的前缀字节改变了操作数大小(从32到64或16),因此在指令中通常可以保存一个字节.以相同的速度执行.当写入低8b或16b的寄存器(或稍后读取完整寄存器(Intel pre-IvB)时的失速)时,它也具有错误依赖性(AMD/P4/Silvermont):由于历史原因, …

抽象

嗨,假设你有两个不同的独立64位二进制矩阵A和T(它T是自身的转置版本,使用矩阵的转置版本允许在乘法运算T的行而不是列,这对二进制算术来说非常酷)和你想要将这些矩阵相乘,唯一的事情是矩阵乘法结果被截断为64位,如果你得到的值大于1某个特定矩阵单元格中的值,则生成的矩阵单元格将包含1否则0

例

   A        T
00000001 01111101 
01010100 01100101 
10010111 00010100 
10110000 00011000 <-- This matrix is transposed
11000100 00111110 
10000011 10101111 
11110101 11000100 
10100000 01100010 

二元和传统乘法结果:

 Binary  Traditional
11000100  11000100
11111111  32212121
11111111  32213421
11111111  21112211
11101111  22101231
11001111  11001311
11111111  54213432
11001111  11001211

题

如何以最有效的方式以上述方式将这些矩阵相乘？

PS

我试图利用二进制and(即&运算符)而不是在单独的位上执行乘法,在这种情况下,我必须为乘法准备数据:

ulong u;

u = T & 0xFF;
u = (u << 00) + (u …