## 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.

**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:

**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.