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;
 }
}

• Dmitry Zinkevich: Thank you very much for such a detailed explanation!

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!

• Mike: A very nice approach indeed. Thanks for providing a solution using ranges. I have a minor note though: the problem defines a "gap" as a contiguous block of zeros surrounded by ones on both ends. Therefore, the answer for 0b1001000 should be 2 (not 3). Of course, the solution can be easily extended by adding std::views::drop(1) after group_by, so that the last block of zeros (if any) is always discarded...

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

• serkan.tuerker: @MartinR Edited my answer to include some reasoning to my solution.
• Martin R: Note that your approach repeatedly finds the same gaps. For the number 529 it finds a gap of length 3, and then the same gap (of length 4) four times. Yes, I know about "premature optimization," but it should be possible to start the search for next gap where the last gap ended (so that the bits are only traversed once, as in the original code).
• serkan.tuerker: @MartinR Thanks, I edited my solution to include the fix.

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;
}

• Uga Buga: I believe this solution will give an answer of 5 for 0b100000 which does not comply with the definition for binary gap. The group of zeroes does not have ones on both sides.

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.

• Toby Speight: Not only is testing the MSB cleaner, it also eliminates that assumption that unsigned int has 32 or more bits (and works when the input is larger than that).
• The Failure by Design: @TobySpeight Correct.