Swift - Finding longest binary gap of a given integer

Question

I recently had the chance to try Codility's algorithm training, and the very first one in the list is finding the longest binary gap of a given integer.

I tried to implement this in Swift, and after finishing it up, I looked at answers all over the internet. My approach is a bit different from what I have seen from others.

---

What is a Binary Gap?

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

---

The following is from the console which makes it easy to understand the implementation.

Binary String of "1041" is: "10000010001"
Position of 1's: [0, 6, 10]
The longest binary gap is 5

Basically what I am doing is:

1. Iterating each binary character, and store the position/index of 1's in an array.
2. As I am looping through, I find the binary gap between two 1's by subtracting the current index of 1 with previous index of 1, so that it gives me how many 0's are present in between them. I then decrement whatever value I get by 1 ('cause arrays...).
3. As I am looping through, I keep track of the longest binary gap in a variable.

The complexity is O(n), and I'd like to know if this approach is in any way efficient in terms of memory, or any scope of improvements with this? Thanks for your time.

---

Code:

public func getLongestBinaryGapFor(_ N : Int) -> Int {
    
    var arrayOfIndexes:[Int] = []
    let binaryString = String(N, radix:2)
    
    print("Binary String of \"\(N)\" is: \"\(binaryString)\"")
    
    var longestBinaryGap:Int = 0
    var index = 0
    
    for char in binaryString {
        if char == "1" {
            arrayOfIndexes.append(index)
            let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes)
            if arrayOfIndexes.count == 2 {
                longestBinaryGap = currentBinaryGap
            } else if index > 2 {
                if currentBinaryGap > longestBinaryGap {
                    longestBinaryGap = currentBinaryGap
                }
            }
        }
        index += 1
    }
    
    print("Position of 1's: \(arrayOfIndexes)")
    return longestBinaryGap
}

func getCurrentBinaryGapFor(_ array:[Int]) -> Int {
    var currentBinaryGap = 0
    if array.count >= 2 {
        let currentPosition = array.count - 1
        let previousPosition = currentPosition - 1
        currentBinaryGap = array[currentPosition] - array[previousPosition] - 1
        return currentBinaryGap
    } else {
        return currentBinaryGap
    }
}

Answer 1

Naming

According to the API Design Guidelines, needless word should be omitted, and prepositional phrases should be made argument labels. Also variable names should generally be lower (camel) case.

Therefore a better function name would be

public func longestBinaryGap(for n: Int) -> Int 

Also variable names should not contain type information, that applies for example to

var arrayOfIndexes: [Int]

Simplifying your approach

Let's start with func getCurrentBinaryGapFor(), that looks unnecessary complicated. Without additional local variables it can be written as

func getCurrentBinaryGapFor(_ array:[Int]) -> Int {
    if array.count >= 2 {
        return array[array.count - 1] - array[array.count - 2] - 1
    } else {
        return 0
    }
}

In the main function,

let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes)
if arrayOfIndexes.count == 2 {
    longestBinaryGap = currentBinaryGap
} else if index > 2 {
    if currentBinaryGap > longestBinaryGap {
        longestBinaryGap = currentBinaryGap
    }
}

can be simplified to

let currentBinaryGap = getCurrentBinaryGapFor(arrayOfIndexes)
if currentBinaryGap > longestBinaryGap {
    longestBinaryGap = currentBinaryGap
}

and the loop

var index = 0
for char in binaryString {
    if char == "1" {
        // ... do something ...
    }
    index += 1
}

can be written as

for (index, char) in binaryString.enumerated() where char == "1" {
    // ... do something ...
}

Only the last two elements of arrayOfIndexes are used in the program. I would

• either store all positions of ones in the array first, and then determine the longest run from that array once,
• or use two variables for the recent two positions instead of an array.

In either case, a separate function to compute the current gap seems unnecessary.

Summarizing the changes so far, the function would look like this:

public func longestBinaryGap(for n: Int) -> Int {
    var bitPositions: [Int] = [] // Positions of all `1` bits in `n`
    let binaryRepr = String(n, radix:2) //

    for (index, char) in binaryRepr.enumerated() where char == "1" {
        bitPositions.append(index)
    }

    var longestGap: Int = 0
    if bitPositions.count >= 2 {
        for i in 0...bitPositions.count - 2 {
            let gap = bitPositions[i + 1] - bitPositions[i] - 1
            if gap > longestGap {
                longestGap = gap
            }
        }
    }

    return longestGap
}

Using Swift's functional methods this could be written as

public func longestBinaryGap(for n: Int) -> Int {
    let binaryRepr = String(n, radix: 2) //

    let bitPositions = binaryRepr.enumerated()
        .filter { $0.element == "1" }
        .map { $0.offset }

    let longestGap = zip(bitPositions, bitPositions.dropFirst())
        .map { $1 - $0 - 1 }
        .max() ?? 0

    return longestGap
}

which looks elegant, but is actually a bit slower than the previous version.

Boosting the performance

Your approach is \$ O(d) \$ (in time and memory), where \$ d \$ is the number of digits in \$ n \$. That seems very good since any solution must somehow traverse all digits of the given number.

As said above, the memory usage can be reduced to \$ O(1) \$ by keeping only the last two bit positions, instead of using an array.

However, much time can be saved by not converting the integer to a string. The binary digits of a number can be determined efficiently in pure integer arithmetic.

That leads to the following implementation (essentially a Swift version of Find the binary gap of a number N), which is considerably faster:

public func longestBinaryGap1(for n : Int) -> Int {

    if n <= 0 {
        return 0
    }

    var n = n // Make a mutable copy
    // Remove trailing zeros:
    while n % 2 == 0 {
        n /= 2
    }

    var longestGap = 0
    var gap = 0
    repeat {
        n /= 2
        if n % 2 == 0 {
            // Current bit is `0`: increase gap size.
            gap += 1
        } else {
            // Current bit is `1`: check current gap, then reset.
            if gap > longestGap {
                longestGap = gap
            }
            gap = 0
        }
    } while n > 0

    return longestGap
}

And it gets even faster if we use the “find first bit set” function ffsl() (which might take advantage of compiler intrinsics):

public func longestBinaryGap2(for n : Int) -> Int {

    var n = n // Make a mutable copy
    let firstPosition = ffsl(n)
    if firstPosition == 0 {
        return 0
    }
    n = n >> firstPosition

    var longestGap = 0
    while n > 0 {
        let position = Int(ffsl(n))
        if position - 1 > longestGap {
            longestGap = position - 1
        }
        n = n >> position
    }

    return longestGap
}

Benchmark

My simple benchmark:

let M = 1_000_000

do {
    var sum = 0
    let start = Date()
    for n in 1...M { sum += longestBinaryGap(for: n) }
    let end = Date()
    print(sum, end.timeIntervalSince(start))
}

On a 1.2 GHz Intel Core m5 (with the program compiled in Release mode, i.e. with optimizations), I measured approximately:

• Your original code: 3.3 seconds
• longestBinaryGap1(): 0.08 seconds
• longestBinaryGap2(): 0.04 seconds