Return to Answer

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
 repeat {
 let position = Int(ffsl(n))
 if position - 1 > longestGap {
 longestGap = position - 1
 }
 n = n >> position
 } while n > 0
 
 return longestGap
}

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
}

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

public func longestBinaryGap2(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
}

• 3.3 seconds with your original code.
• 0.08 seconds with the final version above.

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.

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
 repeat {
 let position = Int(ffsl(n))
 if position - 1 > longestGap {
 longestGap = position - 1
 }
 n = n >> position
 } while n > 0
 
 return longestGap
}

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

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:

• 3.3 seconds with your original code.
• 0.08 seconds with the final version above.