如何使用按位运算检查置换的十六进制整数是否与另一个匹配(性能优化) [英] How to check if permuted hexadecimal integers matches to another using Bitwise operations (performance optimization)

问题描述

在

After discussing a little about optimization of a part from my code in a previous question and getting some low-level improvements, @SergGr suggested me creating a new question to try get a high-level improvement and reach my main goal.

在我的代码中，我必须在加扰"的正方形- 1个拼图对象，然后检查是否已解决.当我发现更好地实现围绕互联网的Square-1拼图对象我将其用于我的Android应用程序.

In my code I have to apply some moves in a "scrambled" square-1 puzzle object and, after, check if it was solved. As I found a better implementation of a square-1 puzzle object around internet I took it to be used in my Android application.

然后，如您所见，构建了类有四个简单数字(integer)字段:

Then, as you can see, the class is built with four simple numbers (integer) fields:

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

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

这些字段表示Square-1拼图的部分"，其中hexadecimal表示形式中的每个数字都是这些部分之一(两位数，例如11，33，bb ...表示立方体的同一块"，其中是大"块.

These fields means the "pieces" of the square-1 puzzle, where each digit in the hexadecimal representation is one of these pieces (double digits such as 11, 33, bb... means the same "piece" of the cube, wich is a "big" piece).

您可以看到，使用该数字进行的一些表示拼图中真实动作的操作都是使用该数字进行的，但最多只能通过其位进行排列.

As ou can see, some operations wich represents real actions through the puzzle are made using that numbers, but at the most is permutations through its bits.

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

In the case of my application I have to check if the puzzle is solved but, for my situation, the solved state is not, necessarly, equals to the raw fields. As we talking about a Rubik's Cube variant the faces could be moved, the we can have a solved state like (ul + " " + ur): [112334 556770], [233455 677011], [455677 11233*] and so on.

Obs .:注意前导零...

然后，我想到了一种简单的算法，可以通过使用固定的求解序列(但使用Strings)查找循环排列来检查求解状态.但是，经过一些测试后，我意识到像我一样使用Strings进行的这项工作使我的应用程序仍然运行得如此缓慢，一旦我不得不在一个大的循环中调用此检查数千次.

Then I thought a simple algorithm to check the solved state by looking for cyclic permutations in a fixed solved sequence, but using Strings. However, after some tests I realized that this work, using Strings as I did, was making my app still so slow, once I have to call this checking thousand times in a big loop.

• 将所有数字转换为String(在这种情况下为十六进制字符串)；
• 固定的已解决状态(ul+ur):s = "011233"+"455677";
• 要检查是否解决的状态(ul+ur):t = "233455"+"677011";
• 如果我们连接s+s，则检查是否可以在"011{233455677011}233455677"内部找到t，然后isSolved()检查将返回true.

• Convert all numbers to String (in this case a hex String);
• A fixed solved state (ul+ur): s = "011233"+"455677";
• A state to check if is solved (ul+ur): t = "233455"+"677011";
• If we concat s+s we check if we can found t inside: "011{233455677011}233455677", then isSolved() checking returns true.

基本上，我的应用程序的核心代码是这个，然后检查是否像这样解决了难题:

Basically the core code of my app is this and I check if the puzzle is solved like this:

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 sucess in a list
    }
    auxCube.copy(oldCube) //back test cube to initial state to continue finding sequences
}

如您所见，这里仅使用了我创建的2个功能.我将在下面描述方法applySequence().

As you can see, there are only 2 functions made by me being used here. I'll describe the method applySequence() bellow.

我自己制作了此方法，将格式化的序列应用于Square-1拼图对象.一旦这个谜题的正式序列由一些字符组成(看起来像:"(1, 2) / (6, -3) /"，我就采取了一些步骤来提取数字，然后移动多维数据集.它看起来像:

I made this method by myself to apply formated sequences to the square-1 puzzle object. Once official sequences for this puzzle are composed by some characters (looks like: "(1, 2) / (6, -3) /" I did some steps to extract the numbers and, after, move the cube. It looks like:

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()
}

---

这种方法非常简单，但考虑到它在a中使用了String操作(如concat()和contains())，导致Android的性能降低了60万倍.

---

This way is so simple but considering it uses String operations like concat() and contains() in a for that loops over 600000 times the performance, in Android, is reduced.

尝试优化后，我意识到最好的方法之一是按位操作，这种操作是作者对原始代码进行的操作，但是我无法弄清楚.

After trying optimize I realized that one the best ways to do it cames with bitwise operations, operations such the author did over his original code, however I couldn't figure it out.

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

As a extra info about the problem, if I remove the call of my isSolved() method the final time of the search reduces in 20~30 seconds.

然后，如何使用比特比特化功能执行isSolved()操作，使其在较大的for循环中工作更轻(针对Android)?

Then, how to perform isSolved() operation using bitewising to work lighter in a big for loop (targeting Android)?

推荐答案

您可以使用按位运算来检查两个值是否彼此循环移位.

You can check if two values are cyclic shift of each other with bitwise operations.

您的值是6个字节(48位长度)的值，因此我们可以将它们打包在64位long中，然后对一个值进行低48位的循环旋转，并检查与另一个值的一致性.

Your values are 6-byte (48 bits length) values, so we can pack them in 64-bit long, then make cyclic rotation of low 48 bits for one value and check for coincidence with other one.

Idone

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

这篇关于如何使用按位运算检查置换的十六进制整数是否与另一个匹配(性能优化)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！