Finding the Binary Gap for a Number in .NET

Binary Gap

A binary gap is any sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of the number. For example, the number 25 has binary representation 11001 and contains a binary gap of 2. The number 723 has binary representation 1011010011 and contains three binary gaps: two of length 1 and one of length 2. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 30 has binary representation 11110 and has no binary gaps. The number 7 has binary representation 111 and has no binary gaps.

There are a few ways to work out the binary gap for a number. Let’s do a small program to demonstrate this.

Create a new Visual Basic.NET or C# Windows Forms application.

Design the form as shown in Figure 1.

Design
Figure 1: Design

Add the following Namespaces.

C#

using System;
using System.Collections;
using System.Data;
using System.Linq;
using System.Text.RegularExpressions;
using System.Windows.Forms;

VB.NET

Imports System.Text.RegularExpressions

Add the intResult variable to hold the value of the gaps as worked out in functions that we will add a bit later.

C#

   int IntResult = 0;

VB.NET

   Private IntResult As Integer = 0

By looking at the design, you may have realised that there are three different ways I will demonstrate. There may be more, but I am showing you three. Add the first function.

C#

   public static int BinaryGap1(int val)
   {

      var rxGap = new Regex("(?<=1)(0+)(?=1)");
      var strGap = Convert.ToString(val, 2);

      return
         rxGap.Matches(strGap)
            .Cast<Match>()
            .Select(m => m.Length)
            .DefaultIfEmpty(0)
            .Max();

   }

VB.NET

   Public Shared Function BinaryGap1(ByVal val As Integer) _
         As Integer

      Dim rxGap = New Regex("(?<=1)(0+)(?=1)")
      Dim strGap = Convert.ToString(val, 2)

      Return rxGap.Matches(strGap).Cast(Of Match)().[Select] _
         (Function(m) m.Length).DefaultIfEmpty(0).Max()

   End Function

The preceding function makes use of Regular Expressions to test for the binary digits of the input number. These digits are only 1s and 0s. It then checks to see how many 0s are present between 1s; this creates the binary gap.

Add the next function.

C#

   private static int BinaryGap2(int val)
   {

      BitArray baGap = new BitArray(new[] { val });

      int intCount = 0;
      int intIndex = -1;

      for (int i = 0; i < baGap.Length; i++)
      {

         if (!baGap[i])

            continue;

         if (intIndex != -1)
         {

            int intTemp = i - intIndex - 1;

            if (intTemp > intCount)
            {

               intCount = intTemp;

            }

         }

         intIndex = i;

      }

      return intCount;

   }

VB.NET

   Private Shared Function BinaryGap2(ByVal val As Integer) _
         As Integer

      Dim baGap As BitArray = New BitArray({val})
      Dim intCount As Integer = 0
      Dim intIndex As Integer = -1

      For i As Integer = 0 To baGap.Length - 1

         If Not baGap(i) Then Continue For

         If intIndex <> -1 Then

            Dim intTemp As Integer = i - intIndex - 1

            If intTemp > intCount Then

               intCount = intTemp

            End If

         End If

         intIndex = i

      Next

      Return intCount

   End Function

The previous function converts the input number to a BitArray. It then loops between the values to find the binary gap if one exists.

The following C# function makes use of Bitshifting to determine the binary gap.

C#

   public static int BinaryGap3(int val)
   {

      int intMax = 0;
      int intCount = 0;

      val |= val - 1;

      while (val != val >> 1)
      {

         val >>= 1;

         if ((val & 1) == 1)
         {

            if (intCount > intMax)

               intMax = intCount;

               intCount = 0;

         }

         else

            intCount++;

      }

      return intMax;

   }

Add the code to call all the functions.

C#

      private void Button1_Click(object sender, EventArgs e)
      {

         IntResult = BinaryGap1(200890);
         MessageBox.Show(IntResult.ToString());

      }

      private void Button2_Click(object sender, EventArgs e)
      {

         IntResult = BinaryGap2(200890);
         MessageBox.Show(IntResult.ToString());

      }

      private void Button3_Click(object sender, EventArgs e)
      {

         IntResult = BinaryGap3(200890);
         MessageBox.Show(IntResult.ToString());

      }
   }

VB.NET

   Private Sub button1_Click(sender As Object, e As EventArgs) _
         Handles button1.Click

      IntResult = BinaryGap1(200890)
      MessageBox.Show(IntResult.ToString())

   End Sub

   Private Sub button2_Click(sender As Object, e As EventArgs) _
         Handles button2.Click

      IntResult = BinaryGap2(200890)
      MessageBox.Show(IntResult.ToString())

   End Sub

When run, the output will be shown inside a MessageBox, as you can see in Figure 2:

Running
Figure 2: Running

Conclusion

This was a nice little exercise. Something different. I hope I have managed to show you how easy it is to manipulate binary values.

Hannes DuPreez
Hannes DuPreez
Ockert J. du Preez is a passionate coder and always willing to learn. He has written hundreds of developer articles over the years detailing his programming quests and adventures. He has written the following books: Visual Studio 2019 In-Depth (BpB Publications) JavaScript for Gurus (BpB Publications) He was the Technical Editor for Professional C++, 5th Edition (Wiley) He was a Microsoft Most Valuable Professional for .NET (2008–2017).

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read