💡 Problem Formulation: 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, the number 9 has a binary representation of 1001 and contains a binary gap of length 2. The challenge is to write a function in Python that, given a positive integer, returns the length of its longest binary gap.
Method 1: Using String Operations
This method involves converting the given integer to its binary representation as a string, stripping the trailing zeros, and then finding the longest sequence of zeros between ones. It is a straightforward approach that utilizes basic Python string operations without any additional libraries.
♥️ Info: Are you AI curious but you still have to create real impactful projects? Join our official AI builder club on Skool (only $5): SHIP! - One Project Per Month
Here’s an example:
def binary_gap(N):
# Strip the trailing zeros and split '1's
gaps = bin(N)[2:].strip('0').split('1')
# Find the longest gap
return max(map(len, gaps)) if gaps else 0
# Example Usage
print(binary_gap(9))The output is:
2
This code snippet defines a function binary_gap that first converts the number to its binary equivalent using the bin function, strips the trailing zeros, and then splits the string at occurrences of ‘1’. It finds the maximum length of the sequences in the resulting list, which represents the binary gap. This single-line functional approach is simple and readable.
Method 2: Bitwise Operations
Instead of string manipulation, this method uses bitwise shifts and masks to directly process the binary digits. It’s an efficient method from a computational standpoint because it operates at the bit level.
Here’s an example:
def binary_gap(N):
# Using bitwise operations
current_gap = 0
max_gap = 0
# Ignore trailing zeros
while N > 0 and N % 2 == 0:
N >>= 1
while N > 0:
if N % 2 == 0:
current_gap += 1
else:
max_gap = max(max_gap, current_gap)
current_gap = 0
N >>= 1
return max_gap
# Example Usage
print(binary_gap(9))The output is:
2
The binary_gap function here iterates through the binary digits of N using bitwise operations. It ignores the trailing zeros first, then traverses the rest of the binary representation to track and record the length of the gaps. This method is particularly good for performance-sensitive applications.
Method 3: Regular Expressions
This method uses Python’s regex library to find all consecutive sequences of zeros surrounded by ones in the binary representation of the given integer. The regex pattern ’10+1′ captures the essence of the binary gap.
Here’s an example:
import re
def binary_gap(N):
# Find all sequences of 0s surrounded by 1s
gaps = re.findall(r'10+1', bin(N))
# Return the length of the longest sequence
return max(map(lambda x: x.count('0'), gaps), default=0)
# Example Usage
print(binary_gap(9))The output is:
2
The regex pattern r'10+1' is used with findall to match sequences within the binary string. The function then maps these matched sequences to their lengths of zero sequences, and finally, max determines the longest one. This method is elegant and compact but requires knowledge of regular expressions.
Method 4: Iterative Approach
An iterative method can be implemented by looping through each binary digit and keeping count of the zeros until one is encountered. Variables to keep track of the current and maximum binary gap will be updated accordingly throughout the loop.
Here’s an example:
def binary_gap(N):
binary = bin(N)[2:]
max_gap = 0
current_gap = 0
for bit in binary:
if bit == '0':
current_gap += 1
else:
max_gap = max(max_gap, current_gap)
current_gap = 0
return max_gap
# Example Usage
print(binary_gap(9))The output is:
2
In this example, the binary representation is iterated bit by bit. When a ‘0’ is encountered, the current gap count is increased. Upon reaching a ‘1’, the current gap is compared to the maximum gap recorded so far, updating if the current is larger. This method is easy to understand for those new to Python programming.
Bonus One-Liner Method 5: Using Built-in Functions
This one-liner uses a combination of built-in Python functions to compute the binary gap. It is perhaps the most Pythonic method but may be less readable for beginners.
Here’s an example:
binary_gap = lambda N: max((len(s) for s in bin(N)[2:].strip('0').split('1')), default=0)
# Example Usage
print(binary_gap(9))The output is:
2
This functional one-liner defines a lambda function that calculates the binary gap. It first converts the number to binary, strips trailing zeros, and splits the string at ‘1’s. The generator expression within max computes the length of these split strings, with default=0 handling the case of no gap.
Summary/Discussion
- Method 1: String Operations. Straightforward and easy to understand. However, it can be less efficient than bitwise operations because of string manipulation overhead.
- Method 2: Bitwise Operations. More efficient than string manipulation for large numbers as it deals with binary data at the lowest level. It might be less readable for those not familiar with bitwise operations.
- Method 3: Regular Expressions. Compact and powerful, especially for pattern matching within strings. Requires understanding of regex, which can be a barrier for some.
- Method 4: Iterative Approach. Simple and readable for beginners. However, it can be slower than methods utilizing Python’s built-in functions effectively.
- Method 5: Using Built-in Functions. Very concise and Pythonic. It may require a deeper understanding of Python’s functional programming capabilities, potentially challenging for new programmers.