How to replace this String operations with Bitwise

问题:

Considering I have this fields in a Base object:

//these fields have their bits constantly permuted
//and have their values defined to "011233455677..."
//to integers acts like Strings

var ul = 0x011233
var ur = 0x455677
var dl = 0x998bba
var dr = 0xddcffe

And considering I have this method which operates those fields as String values:

private fun Cubo.isSolved(): Boolean {             
    val solved = Base()

    //function to append "leading zero" to the hex integer
    fun fill(s: String) = if (s.length == 5) "0$s" else s

    //all these fields are declared at the global escope

    //converted ul, ur, dl, dr from solved obj to hex string
    a1 = fill(Integer.toHexString(solved.ul))
    b1 = fill(Integer.toHexString(solved.ur))
    c1 = fill(Integer.toHexString(solved.dl))
    d1 = fill(Integer.toHexString(solved.dr))

    //concats the converteds ul and ur into a new one
    ab1 = a1 + b1
    //concats the converteds dl and dr into a new one
    cd1 = c1 + d1

    //do the same with fields of THIS object
    a2 = fill(Integer.toHexString(this.ul))
    b2 = fill(Integer.toHexString(this.ur))
    c2 = fill(Integer.toHexString(this.dl))
    d2 = fill(Integer.toHexString(this.dr))
    ab2 = a2 + b2
    cd2 = c2 + d2

    //checks if concatenated fields from THIS object exists inside the 
    //duplicated [solved] object fields.
    //This will help me to check if fields from THIS object are 
    //cyclic/circular permutations of the [solved] object.
    return (ab1 + ab1).contains(ab2) && (cd1 + cd1).contains(cd2)
}

My goal is to know how to replace that operations with bitwise operations, once the fields are integers?

I'm trying this because my app is so slow and this method is reducing its performance once it is called thousand times in loop, then realized a way of improve my application performance could be using the bitwising operations.

And to simplify the idea of ​​this method, it used just to verify that the field THIS object corresponds to the fields of a "SOLVED" object, but this is done considering the possibility that the fields of the test object are cyclically permuted.

回答1:

Concatenating

"Concatenating" two hexadecimal 6-digit numbers is actually a left shift of 24 bits (since every hexdecimal digit has 4 bits and the length is 6) of the first number and taking the second number bitwise or the result of the shift.

infix fun Long.hexConcat(num: Long) = num.or(shl(24))

Contains

To check whether a 6-digit hex number is either contained in the first or last 6-digits of a 12-digit hex number, you can bitwise and them both (to test the end). To test if it is at the start you have to first right shift it by 24 bits and then bitwise and it.

infix fun Long.containsAsHex(num: Long) = and(num) == num || shr(24) == num

Example:

fun main() {

    val a = 0x011233L
    val b = 0x455677L

    val c = a hexConcat b

    println(c.toString(16)) // 11233455677
    println(c containsAsHex a) // true
}

Of course you can parametrize hexConcat further to not limit it to 6-digit hexadecimal numbers.

---

In case the 6-digit hex number can be anyhwhere in a 12-digit hex number:

To check whether a hexadecimal number "contains" another one you shift it 4 bits to the right until its value is 0 or you found the match which would mean that the shifted number bitwise and the number to test has to equal the number to test.

infix fun Long.containsAsHex(num: Long): Boolean {

    var shifted = this

    while (true) {

        if(shifted.and(num) == num) {
            return true
        }

        if(shifted == 0L) {
            return false
        }

        shifted = shifted.shr(4) // shift one hex digit
    }

    @Suppress("UNREACHABLE_CODE")
    return false
}

回答2:

Assuming your target state is fixed and has a fixed size of 12 hex chars, I'd do it a bit differently. I'd first pre-calculated all the rotations of the solved and then checked against them using simple equals. I'm not sure where it makes sense to store that in your application. In this code I pass that as the target parameter.

class Cubo() {

    var ul: Int = 0x011233
    var ur: Int = 0x455677
    var dl: Int = 0x998bba
    var dr: Int = 0xddcffe

    constructor(ul: Int, ur: Int, dl: Int, dr: Int) : this() {
        this.ul = ul
        this.ur = ur
        this.dl = dl
        this.dr = dr
    }

    fun isSolved(target: TargetState): Boolean {
        return target.checkSolved(this)
    }
}


class TargetState(val uRot: AllRotations, val dRot: AllRotations) {
    constructor(c: Cubo) : this(AllRotations(concat(c.ul, c.ur)), AllRotations(concat(c.dl, c.dr))) {
    }

    fun checkSolved(c: Cubo): Boolean {
        val u = concat(c.ul, c.ur)
        val d = concat(c.dl, c.dr)
        return uRot.contains(u) and dRot.contains(d)
    }

    companion object {
        fun concat(l: Int, r: Int): Long {
            return l.toLong().shl(AllRotations.singleBitsCount).or(r.toLong())
        }

    }
}


class AllRotations(value: Long) {

    val rotatedValues = Array<Long>(doubleDigitsCount) { i -> rotate(value, digitSize * i) }

    fun contains(test: Long): Boolean {
        for (v in rotatedValues) {
            if (v == test)
                return true
        }
        return false
    }


    companion object {
        const val singleDigitsCount = 6
        const val doubleDigitsCount = 2 * singleDigitsCount
        const val digitSize = 4
        const val singleBitsCount = digitSize * singleDigitsCount
        const val doubleBitsCount = digitSize * doubleDigitsCount
        const val mask = 1L.shl(doubleBitsCount) - 1


        fun rotate(value: Long, shift: Int): Long {
            val hi = value.shl(shift).and(mask)
            val lo = value.shr(doubleBitsCount - shift)
            return hi.or(lo)
        }
    }
}

Here is a simple test that it works:

val solved = Cubo(0x011233, 0x455677, 0, 0)
val targetState = TargetState(solved)

val c1 = Cubo(0x233455, 0x677011, 0, 0)
val c2 = Cubo(0x455677, 0x011233, 0, 0)
val cbad = Cubo(0x455677, 0x011233, 1, 0)

println(c1.isSolved(targetState))
println(c2.isSolved(targetState))
println(cbad.isSolved(targetState))