java - 如何使用按位运算检查置换的十六进制整数是否与另一个匹配(性能优化)

Question

在 previous question 中对我的代码中的一部分进行了一些优化讨论之后并获得一些低级别的改进，@SergGr 建议我创建一个新问题来尝试获得高级改进并实现我的主要目标。

在我的代码中，我必须在“乱序”square-1 puzzle 中应用一些 Action 对象，然后检查它是否已解决。当我找到一个 better implementation of a square-1 puzzle object around internet我把它用在我的 Android 应用程序中。

然后，如您所见，class由四个简单的数字(整数)字段构建:

var ul = 0x011233
var ur = 0x455677 //continuation of ul

var dl = 0x998bba
var dr = 0xddcffe //continuation of dl

这些字段表示 square-1 拼图的“fragment ”，其中 hexadecimal 表示中的每个数字都是这些 fragment 之一(双位数，例如 11， 33, bb...表示立方体的同一“ block ”，也就是“大” block )。

如您所见，一些代表拼图中实际 Action 的操作是使用该数字进行的，但最多是通过其位进行排列。

在我的应用程序中，我必须检查拼图是否已解决，但对于我的情况，已解决的状态不一定等于原始字段。当我们谈论 Rubik 的魔方变体时，面可以移动，我们可以有一个解决状态，如 (ul + ""+ ur): [112334 556770], [233455 677011] , [455677 11233*] 等等。

观察:注意前导零...

然后我想到了一个简单的算法来检查已解决的状态，方法是在固定的已解决序列中寻找循环排列，但使用 Strings。然而，经过一些测试后，我意识到这项工作(像我一样使用 Strings)使我的应用程序仍然很慢，一旦我不得不在一个大循环中调用此检查数千次。

使用字符串快速解释我的算法:

• 将所有数字转换为 String(在本例中为十六进制字符串)；
• 固定求解状态 (ul+ur):s = "011233"+"455677";
• 检查是否已解决的状态 (ul+ur):t = "233455"+"677011";
• 如果我们连接 s+s，我们检查是否可以在里面找到 t:"011{233455677011}233455677"，然后 isSolved() 检查返回 true。

我必须在哪里应用它

基本上我的应用程序的核心代码是这样的，我检查这个谜题是否已经解决了:

for (sequence in sequences) { //814*814 elements
    auxCube.applySequence(sequence.seq) //applies the current sequence to the auxiliary cube
    if (auxCube.isSolved()) { //checks if it was solved
        searches.add(Search(sequence.seq)) //adds the success in a list
    }
    auxCube.copy(oldCube) //back test cube to initial state to continue finding sequences
}

如您所见，这里只使用了我制作的两个函数。我将在下面描述 applySequence() 方法。

applySequence() 方法

我自己制作了这个方法，将格式化序列应用于 square-1 拼图对象。一旦这个谜题的官方序列由一些字符组成(看起来像:“(1, 2)/(6, -3)/”我做了一些步骤来提取数字，然后移动立方体。它看起来像:

fun applySequence(sequence: String) {
    //remove all "(", ")", "," and " " characters and split in each "/"
    val pairs = sequence.replace(" ", "").replace("\\(", "").replace("\\)", "").split("/")

    //if starts with / then perform respective move
    if (sequence.startsWith("/")) slashMove()

   //iterate over pairs
    for (pair in pairs) {
        //checks if pair is not empty
        if (pair != "") {
            //split pair in the "," character
            val pairMoves = pair.split(",")
            
            //perform top and bottom moves with extracted numbers
            move(true, Integer.parseInt(pairMoves[0]))
            move(false, Integer.parseInt(pairMoves[1]))
            slashMove()
        }
    }

    //if sequence not ends with / then applies respective move
    if (!sequence.endsWith("/")) slashMove()
}

---

这种方法非常简单，但考虑到它在循环超过 600000 的 for 中使用 String 操作，如 concat() 和 contains()在 Android 中，性能降低了两倍。

在尝试优化之后，我意识到最好的方法之一是按位运算，作者对他的原始代码进行了这样的操作，但我无法弄明白。

作为有关该问题的额外信息，如果我删除对 isSolved() 方法的调用，搜索的最终时间将减少 20~30 秒。

那么，如何使用 bitewising 执行 isSolved() 操作以在大 for 循环(针对 Android)中更轻松地工作？

Answer 1

您可以通过按位运算检查两个值是否相互循环移位。

你的值是6字节(长度为48位)的值，所以我们可以将它们打包成64位的long，然后对一个值进行低48位的循环循环，并检查是否重合另一个。

Ideone

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        long a = (0x011233l) << 24 | 0x455677;
        long b = (0x233455l) << 24 | 0x677011;
        System.out.printf("a: %x   b: %x  \n", a, b);
        if (b == a)
            System.out.printf(" bingo at zero digits shift \n");

        for (int sh=4; sh<48; sh+=4) {
            long bb = (b >> sh)|((b << (64 - sh))>>16); 
            System.out.printf("rotated %d bits  bb: %x \n", sh, bb);
            if (bb == a)
                System.out.printf(" bingo at %d digits shift \n", sh/4);
        }
    }
}

a: 11233455677   b: 233455677011  
rotated 4 bits  bb: 123345567701 
rotated 8 bits  bb: 112334556770 
rotated 12 bits  bb: 11233455677 
  bingo at 3 digits shift 
rotated 16 bits  bb: 701123345567 
skipped
rotated 44 bits  bb: 334556770112