Largest binary gap

Question

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;

}

Answer 1

1. Using a signed type for an integer you want to do bit-manipulations on, or which cannot (must not) be negative is an obvious case of Java damage.

2. While in Java, an int is always a 32 bits 2's complement integer, C++ caters to a far wider range of targets. Admittedly, not all the options are still used (even rarely), but you should not assume the bit-width.

3. Java may not allow implicit conversion of integers to boolean, but C++ does. You seem to get that difference though. Sometimes. Maybe half the time.

4. Yes, you can start from the most significant bit. The most telling disadvantages are

   • that you will always traverse all bits,
   • that you have to use a mask, and
   • that you need the bit-width (look in <cstdint>/stdint.h> for a macro, or better use std::numeric_limits from <limits>) for the mask.

   Better start on the other end.

5. I really wonder why you initialize longest_binary_gap to -1 and then use a conditional-operator to ensure you return at least 0. That's a lot of work for nothing,

6. You were exceedingly generous with long and descriptive names in your function, don't you think it's much more important for the function itself?

7. The function cannot throw by design, so make it noexcept.

8. There also doesn't seem to be a reason not to allow use in a ctce, so mark it constexpr.

Re-coded:

constexpr int biggest_binary_gap(unsigned n) noexcept {
    while (n && !(n & 1))
        n >>= 1;
    int r = 0;
    for (;;) {
        while (n & 1)
            n >>= 1;
        if (!n)
            return r;
        int m = 0;
        while (!(n & 1)) {
            ++m;
            n >>= 1;
        }
        if (r < m)
            r = m;
    }
}

Answer 2

I'm a bit late to the party, but I'll add my two cents nonetheless!

Your code is quite good, even if, as other reviewers pointed, you can still improve it marginally. But I also agree with other reviewers that you could have chosen a more modern, less C-like approach. I would defend one based on ranges, that needs a bit of scaffolding but could be used to solve many other binary-oriented code challenges.

If you don't know what ranges are, you could start here or google "Eric Niebler ranges". With ranges you can (among other things) combine views on a sequence of values; views modify the way you look at the sequence.

Making a number into a binary view of the said number is relatively straight-forward thanks to the view_facade class:

class binary_view
  : public ranges::view_facade<binary_view> // magic here ...
{
    friend ranges::range_access; // ... and here
    int value = 0;

    // how you read the current element of the view
    int read() const { return value & 1; } 

    // how you know you're at the end of the view
    bool equal(ranges::default_sentinel) const { return value == 0; } 

    // how you compare two positions in the view
    bool equal(const binary_view& that) const { return value == that.value; } 

    // how you get to the next position in the view
    void next() { value >>= 1; } 

public:
    binary_view() = default;
    explicit binary_view(int value) : value(value) {}
};

Once you have this view that allows you to look at a number as a sequence of zeros and ones, you can use the operator | to combine it with other views . For instance, we can view the sequence of zeros and ones as a sequence of sequences of consecutive zeros or consecutives ones:

auto zeros_and_ones       = binary_view(my_number);
auto split_zeros_and_ones = zeros_and_ones | group_by(std::equal_to<>());

We can then view those groups of consecutive ones or zeros as the number of zeros they contain:

auto numbers_of_zeros = split_zeros_and_ones | transform([](auto&& group) { 
    return count(group, 0); 
});

Then we can simply request the maximum value out of that view with max_element:

auto consecutive_zeros =
    binary_view(0b1001000) 
        | group_by(std::equal_to<>())
        | transform([](auto&& group) { return count(group, 0); });

auto largest_gap =  *max_element(consecutive_zeros);

Here's a link to the full code (with a slightly buffed-up binary_view allowing bidirectional traversal): https://wandbox.org/permlink/OVlg6aJP9DC1wkPR

If you're skeptical about the benefit you can get from all this (after all, my solution is quite complicated compared to the original code), I suggest you visit this page where you'll find all pre-defined views and think about all the problems you could solve with a combination of them!

Answer 3

Your question states that you want to solve this problem in C++/C++14. In your solution you are mainly using old C style code.

In order to make your code more readable / maintable / bug-free (you choose!), try to make use of STL as much as possible.

std::vector< bool >

Using std::vector<bool> as the binary representation we can make use of the algorithm library of STL.

STL iterators

When dealing with containers in STL, iterators are used to specify a range for a container. These begin and end iterators (specifying a range) are needed for the algorithms.

STL algorithm

The STL algorithm module has most of algorithms you need for manipulating containers. Try to use STL algorithms as much as possible whenever you need to operate on a range of elements.

Here is another approach using std::vector<bool>, iterators and algorithm from STL.

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

std::vector<bool> to_binary(int num)
{
  std::vector<bool> binary;
  while(num != 0)
  {
    binary.push_back(num % 2 != 0);
    num /= 2;
  }
  return binary;
}

int findlargestGap(int num)
{
  int largest_gap = 0;
  auto binary       = to_binary(num);
  auto       it     = binary.begin();
  const auto it_end = binary.end();
  while(it != it_end)
  {
    auto current_true = std::find(it, it_end, true);
    if(current_true == it_end)
      break;

    auto next_true = std::find(current_true+1, it_end, true);
    if(next_true == it_end)
      break;

    const auto d = std::distance(current_true, next_true) - 1;
    largest_gap = std::max(largest_gap, static_cast<int>(d));

    it++;
  }

  return largest_gap;
}

int main(int argc, char** argv)
{
  std::cout << "largest gap for 9: "   << findlargestGap(9) << '\n';
  std::cout << "largest gap for 529: " << findlargestGap(529) << '\n';
  std::cout << "largest gap for 20: "  << findlargestGap(20) << '\n';
  std::cout << "largest gap for 15: "  << findlargestGap(15) << '\n';
  std::cout << "largest gap for 32: "  << findlargestGap(32) << '\n';
}

EDIT

Change the last line in findLargestGap() from it++ to it = next_true to start the next iteration where the last one was found to save cycles in some cases.

LIVE DEMO

Answer 4

Your solution seems rather complicated. I suggest this: shift the argument right until it is zero, counting runs of zeros, noting the longest. I hope this is valid C++, I mostly write in C#.

int binary_gap ( unsigned n )
{
  int best_gap = 0;
  for ( int gap = 0; n != 0; n >>= 1 )
  {
    if ( ( n & 1 ) == 0 ) gap += 1;
    else 
    {
      if ( gap > best_gap ) best_gap = gap;
      gap = 0;
    }
  }
  return best_gap;
}

Answer 5

1. I would use unsigned int.
2. Gap count must be initialized to zero. What's the meaning of -1?

3. Why do you need a mask to move to the first 1? This looks cleaner:

   while( n && !( n & 1u ) )
     n >>= 1;
   

4. Testing for end is just testing for zero, again you do not need the mask:

   while ( n )
   { // ...
   

   or

   for ( ; n; n >>= 1 )
   { //...
   

5. The algorithm seems unnecessarily complicated.