在Java中寻找二进制间隙

Question

我想知道下面的问题描述代码的性能。

例如，数字9具有二进制表示1001，包含长度为2的二进制间隙。数字529具有二进制表示1000010001，并且包含两个二进制间隙:长度4和长度3的一个。数字20具有二进制表示10100，包含长度1的二进制间隙。数字15具有二进制表示1111，没有二进制间隙。

public static int getBinaryGap(int N) {
    if (N < 5) {
        return 0;
    }
    String binaryRep = Integer.toBinaryString(N);
    int currentGap = 0;
    int finalGap = 0;
    for (int i = 0; i+1 < binaryRep.length(); i++) {
        if (currentGap == 0) {
            if (binaryRep.charAt(i) == '1' && binaryRep.charAt(i + 1) == '0') {
                currentGap++;
            }
        } else {
            if (binaryRep.charAt(i + 1) == '0') {
                currentGap++;
            }
            if (binaryRep.charAt(i + 1) == '1') {
                finalGap = finalGap<currentGap ? currentGap:finalGap;
                currentGap = 0;
            }
        }
    }
    return finalGap;
}

Answer 1

Java约定

在Java中，变量以"lowerCamelCase“开头，以小写字母开头，因此请使用getBinaryGap(int n)。另见甲骨文代码约定

字符串转换

性能可以提高，因为您使用到字符串的转换，而您可以解决它仅使用比特篡改。

复杂性

您的代码有一个循环，所有的固定时间操作。Integer.toBinaryString(int n)的成本与n成线性关系。总的性能将是O(n)，这是可以的。

位翻转

遵循您的逻辑，但都是位测试：

public static int getBinaryGapBitFiddling(int n) {
    if (n < 5) {
        return 0;
    }
    int currentGap = 0;
    int finalGap = 0;
    int currentBit;
    for (int i=0 ; (currentBit = (1<<i))< n; i++)
    {
        int nextBit = currentBit << 1;
        if (currentGap == 0) {
            if ( ((currentBit & n) > 0 )  &&  ((nextBit & n ) == 0 )) {
                currentGap++;
            }
        } else {
            if ((nextBit & n ) == 0) {
                currentGap++;
            }
            if ((nextBit & n ) > 0) {
                finalGap = finalGap<currentGap ? currentGap:finalGap;
                currentGap = 0;
            }
        }
    }
    return finalGap;
}

更多的优化

您可能也可以使用位掩码进行更快的扫描。例如，10和01是运行的开始和结束。