[100%] BinaryGap 解の中、JVMで運行するとどちらが速いか

Codility Lesson1 BinaryGap
2進数整数の1と1の間に連続して存在する0の最大長探索、様々な正解あります。
実際にJVM運行するとどちらが速いのか、気のなる人もいるだろう。
試してみましょう。

##テスト環境##
Windows10、Kotlin 1.4、JVM 15で運行

##解１##

![p31.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/397757/79e32a0f-b6b7-beba-8f99-c909be5fe076.png)

私が出した解答ですが、一番普通のやり方だと思ってます。

```Kotlin
    private fun solution1(N: Int): Int {
        val binaryString = Integer.toBinaryString(N)
        var gap = 0
        var count = 0
        for (element in binaryString) {
            if (element == '0') {
                count++
            } else {
                if (count > gap) gap = count
                count = 0
            }
        }
        return gap
    }
```

##解２##
[CodilityのBinaryGapを競プロ未経験が解いてみた](https://qiita.com/shotastage/items/fe996e6f08a25a7ed39b)
split("1")の結果の長さを測る

```Kotlin
    private fun solution2(N: Int): Int {
        val zeros = Integer.toBinaryString(N).split("1").toTypedArray()
        var index = zeros.size
        var max = 0

        /* 割り切れる数かどうかの判定 */if (N % 2 == 0) {
            index -= 1
        }

        /* 最大値の判定 */for (i in 0 until index) {
            if (zeros[i].length > max) {
                max = zeros[i].length
            }
        }
        return max
    }
```

##解３##
[Code Review](https://codereview.stackexchange.com/questions/159650/find-the-binary-gap-of-a-number-n)のanswer

To find the binary gap of n:
Discard all trailing zeros.
As long as n does not consist of 1s only:
Combine n with n shifted to the right by one place.
The number of repetitions is the length of the largest gap.

```Kotlin
    private fun solution3(N: Int): Int {
        var n = N ushr Integer.numberOfTrailingZeros(N)
        var steps = 0
        while (n and n + 1 != 0) {
            n = n or (n ushr 1)
            steps++
        }
        return steps
    }
```

##解４##
[[100%] BinaryGap（src & jUnit）](https://qiita.com/yp2211/items/fab5224d1423548b3b30)の【案２：シフト演算】
実は解３はこれを最適化したものだと思いますが、これとの差異を知りたいからこれも含めて

```Kotlin
    private fun solution4(N: Int): Int {
        var n = N
        var goal = 0
        var counter = 0
        var counterSwitch = false
        while (n > 0) {
            if (n and 1 == 1) {
                if (counterSwitch) {
                    if (counter > goal) goal = counter
                    counter = 0
                } else {
                    counterSwitch = true
                }
            } else {
                if (counterSwitch) counter++
            }
            n = n shr 1
        }
        return goal
    }
```

##テストコード##
1-10000範囲にRandomのInt百万個を作成
それぞれの解を十回運行する。

```Kotlin
object BinaryGap {
    @JvmStatic
    fun test() {
        GlobalScope.launch {
            val testCaseList: MutableList<Int> = mutableListOf()
            repeat(1000000) {
                testCaseList.add((1..10000).random())
            }

            repeat(10) {
                testRun(testCaseList)
            }
        }
    }

    private fun testRun(testList: MutableList<Int>) {
        var start = System.currentTimeMillis()
        testList.forEach {
            solution1(it)
        }
        val time1 = System.currentTimeMillis() - start

        start = System.currentTimeMillis()
        testList.forEach {
            solution2(it)
        }
        val time2 = System.currentTimeMillis() - start

        start = System.currentTimeMillis()
        testList.forEach {
            solution3(it)
        }
        val time3 = System.currentTimeMillis() - start

        start = System.currentTimeMillis()
        testList.forEach {
            solution4(it)
        }
        val time4 = System.currentTimeMillis() - start


        println("1> $time1    2> $time2    3> $time3    4> $time4")
    }

    //solution1-4略
}
```

##結果##
|1|2|3|4|
|:----:|:----:|:----:|:----:|
|1> 72    |2> 528    |3> 27    |4> 70|
|1> 73    |2> 421    |3> 13    |4> 70|
|1> 78    |2> 428    |3> 20    |4> 73|
|1> 79    |2> 310    |3> 12    |4> 65|
|1> 64    |2> 323    |3> 34    |4> 81|
|1> 89    |2> 317    |3> 12    |4> 60|
|1> 74    |2> 343    |3> 33    |4> 82|
|1> 85    |2> 329    |3> 12    |4> 76|
|1> 71    |2> 310    |3> 14    |4> 65|
|1> 70    |2> 452    |3> 16    |4> 63|

解３の圧勝でした。