Skip to main content
Wrong indentation appears to be a copy-paste problem
Source Link
Toby Speight
  • 81.7k
  • 14
  • 101
  • 308

I took a task from Codility to find longest sequence of zeros in binary representation of an integer.

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.

I am a Java developer, but decided to implement it in C++. What could be improved? Is my approach correct? (The compiler version provided by Codility is C++14).

 

 

int solution(int N) {
    int longest_binary_gap = -1;
    unsigned int mask = 1 << 31;
    
    // Find the first occurence of 1
    for (; !(mask & N) && mask != 0; mask >>= 1);
    while (mask != 0) {
        // Move to the next binary digit
        mask >>= 1;
        int current_gap = 0;
        // Count zeroes
        for (; !(mask & N) && mask != 0; mask >>= 1, current_gap += 1);
        
        // Check if the interval ends with 1 and if it is the longes found so far
        if (mask != 0 && current_gap > longest_binary_gap) {
            longest_binary_gap = current_gap;
        }
    }
    return (longest_binary_gap < 0) ? 0 : longest_binary_gap;
    
}

}

I took a task from Codility to find longest sequence of zeros in binary representation of an integer.

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.

I am a Java developer, but decided to implement it in C++. What could be improved? Is my approach correct? (The compiler version provided by Codility is C++14).

 

int solution(int N) {
int longest_binary_gap = -1;
unsigned int mask = 1 << 31;

// Find the first occurence of 1
for (; !(mask & N) && mask != 0; mask >>= 1);
while (mask != 0) {
    // Move to the next binary digit
    mask >>= 1;
    int current_gap = 0;
    // Count zeroes
    for (; !(mask & N) && mask != 0; mask >>= 1, current_gap += 1);
    
    // Check if the interval ends with 1 and if it is the longes found so far
    if (mask != 0 && current_gap > longest_binary_gap) {
        longest_binary_gap = current_gap;
    }
}
return (longest_binary_gap < 0) ? 0 : longest_binary_gap;

}

I took a task from Codility to find longest sequence of zeros in binary representation of an integer.

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.

I am a Java developer, but decided to implement it in C++. What could be improved? Is my approach correct? (The compiler version provided by Codility is C++14). 

int solution(int N) {
    int longest_binary_gap = -1;
    unsigned int mask = 1 << 31;
    
    // Find the first occurence of 1
    for (; !(mask & N) && mask != 0; mask >>= 1);
    while (mask != 0) {
        // Move to the next binary digit
        mask >>= 1;
        int current_gap = 0;
        // Count zeroes
        for (; !(mask & N) && mask != 0; mask >>= 1, current_gap += 1);
        
        // Check if the interval ends with 1 and if it is the longes found so far
        if (mask != 0 && current_gap > longest_binary_gap) {
            longest_binary_gap = current_gap;
        }
    }
    return (longest_binary_gap < 0) ? 0 : longest_binary_gap;
    
}
Source Link

Largest binary gap

I took a task from Codility to find longest sequence of zeros in binary representation of an integer.

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.

I am a Java developer, but decided to implement it in C++. What could be improved? Is my approach correct? (The compiler version provided by Codility is C++14).

int solution(int N) {
int longest_binary_gap = -1;
unsigned int mask = 1 << 31;

// Find the first occurence of 1
for (; !(mask & N) && mask != 0; mask >>= 1);
while (mask != 0) {
    // Move to the next binary digit
    mask >>= 1;
    int current_gap = 0;
    // Count zeroes
    for (; !(mask & N) && mask != 0; mask >>= 1, current_gap += 1);
    
    // Check if the interval ends with 1 and if it is the longes found so far
    if (mask != 0 && current_gap > longest_binary_gap) {
        longest_binary_gap = current_gap;
    }
}
return (longest_binary_gap < 0) ? 0 : longest_binary_gap;

}