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.