Behind the connection

Today, I would like to present you an original way of iterating thru all the bits in an integer. The usual way of iterating the bits is to build a moving bit mask in a loop and selecting each bit in turn with that mask. This works perfectly and it is fast.

But today, I want to show you a better looking way of doing the same iteration. The final code is like this:

var
OneBit : Boolean;
begin
for OneBit in TBitIterator.Create(1234) do
    Write(Ord(OneBit));
end;

This code snippet will display “01001011001000000000000000000000” on screen. This is actually the binary representation of the 32 bit integer 1234, the least significant bit on the left.

This code is interesting not because it is very efficient (It isn’t in fact) but because it will show you can write an enumerator for almost anything which is a collection. Usually the developer thinks the collection has to be a kind of array or list, but this is not true. The collection can be anything provided something is repeated. Here we have one of the simplest collections: the bits used by the CPU to represent an integer value.

The code is more interesting than it looks at first glance. The constructor of TBitIterator actually takes 3 parameters: the integer which holds the bits to iterate, the width of the number and a direction flag.

Here are 3 examples:

TBitIterator.Create(1234);
TBitIterator.Create(1234, 16);
TBitIterator.Create(1234, 48, TRUE);

The first produce the output shown above. By default, with only one argument, there are 32 bits in the enumeration and they are enumerated bit 0 first. By specifying an optional width, you can select the number of bits. So the second line displays “0100101100100000”.

The third optional argument adds the direction of the enumeration. By default, it is FALSE which makes the enumeration starting from the least significant bit. If you use TRUE as in the third example, the enumeration starts by the most significant bit which is handy for example when you have to display the bits because usually binary values have the most significant bit on the left of the number.

Writing the enumerator

I wrote another blog article (http://francois-piette.blogspot.com/2012/12/writing-iterator-for-container.html) explaining how to write an enumerator. It was applied to a dynamic list. We will apply the exact same mechanism to the bits of an integer.

To write an enumerator, we need a record, a class or an interface. In this example, we will use a record:

TBitEnumerator = class;
TIntType = Int64; // Will define the maximum width

TBitIterator = record
public
Value : TIntType;
Width : Byte;
Reverse : Boolean;
function GetEnumerator: TBitEnumerator;
constructor Create(AValue : TIntType;
                     AWidth   : Byte = 32;
                     AReverse : Boolean = FALSE);
end;

Actually, there are 3 types involved: A class TBitEnumerator which will implement the enumeration processing, the record TBitIterator which is the container holding data and an integer type TIntType which is used to have only one place for the underlying integer type holding the data.

TBitIterator is holding the data. To implement the interesting features to select the width (number of bits) and direction of enumerator, I added two more fields. The constructor will ne trivial: just copy the arguments to the member variables.

Of course, to be enumerable, our record needs a function named GetEnumerator and returning a class which has the code for the actual enumeration.

The complete implementation is short:

constructor TBitIterator.Create(
AValue : TIntType;
AWidth : Byte;
AReverse : Boolean);
begin
Value := AValue;
Reverse := AReverse;
if Width > (8 * SizeOf(TIntType)) then
    raise ERangeError.Create('Maximum width exceeded');
Width := AWidth;
end;

function TBitIterator.GetEnumerator: TBitEnumerator;
begin
Result := TBitEnumerator.Create(Self);
end;

The enumerator class is also very simple. Here is his declaration:

TBitEnumerator = class
Container : TBitIterator;
Index : Integer;
public
constructor Create(AContainer : TBitIterator);
function GetCurrent: Boolean;
function MoveNext: Boolean;
property Current: Boolean read GetCurrent;
end;

The code is really simple. It looks mostly like in the previous article (http://francois-piette.blogspot.com/2012/12/writing-iterator-for-container.html) except for the GetCurrent function.

constructor TBitEnumerator.Create(AContainer : TBitIterator);
begin
inherited Create;
Container := AContainer;
Index := - 1;
end;

function TBitEnumerator.MoveNext: Boolean;
begin
Result := Index < (Container.Width - 1);
if Result then
Inc(Index);
end;

function TBitEnumerator.GetCurrent: Boolean;
begin
if Container.Reverse then
    Result := (Container.Value and (TIntType(1) shl (Container.Width - Index - 1))) <> 0
else
    Result := (Container.Value and (TIntType(1) shl Index)) <> 0;
end;

This code doesn’t require much explanation, except GetCurrent which deserve a few words for those not accustomed to bit handling. Basically to get the value of a bit inside an integer, we must build a mask, use the bitwise operator “and” and check against zero.

A bit mask is a number which has only one bit set to the value 1. All other bits are set to zero. To create an integer with the Nth bit set to 1, we can start from the value 1 and shift it N positions to the left. Delphi has the “shl” operator to do exactly that.

You see that the value 1 is cast to TIntType. This is because by default if you write 1 alone, his data type depends on the context. Here we want to force the data type to be the size we need, hence the explicit cast.

Link: http://francois-piette.blogspot.com/2013/01/original-method-to-iterate-bits-within.html
Follow me on Twitter

Every now and then, people keep asking me why I use Delphi to develop my software.

Here are a few reasons:

1. Speed. Delphi is not only a language, but also an integrated development environment (IDE). Both parts are blazing fast at their respective tasks.

Language: Being a native language compiler, the generated code, Intel machine code, is really fast at doing his job.

IDE: I can do everything within the IDE, from editing, to debugging. I have tools to quickly build applications. There is a two way form designer and object inspector. As soon as you change a property value in the object inspector or move/add something visually on a form, your code reflects it immediately. Developer productivity is excellent.

2. Universality: Delphi can do almost everything. There is no need to use anything external. Your program is standalone and do not depends on anything. If you need it, it is easy to call external software or be called by external software. Delphi supports almost everything, from low level API to high level database. You can write business application as well as process control, communication or multimedia applications. You can build full blown GUI application 2D or 3D, or build web applications using soap, rest and more.

3. Modern language: although originally based on Pascal, the Delphi language is now a full blown object oriented language supporting everything from simple object polymorphism and inheritance to generic code and run time type information.

4. Rich library: Delphi includes two broad component frameworks: VCL and FireMonkey. VCL is Windows only while FireMonkey is cross-platform.

5. Familiar: C/C++/Java/C# and Delphi are quite similar. They all have the same kind of syntax. Of course some details vary, but all in all they support the same construct. Among all, I find I’m the most productive with Delphi.

6. Cross-platform: You can build applications for Windows, MAC OSx, iOS, 32 and 64 bits. And soon Androïd and Linux.

7. Active community: Delphi developer forms a very active community. There is a lot of website devoted to Delphi. All social networks have each several communities (LinkedIn, Google+, Facebook, Tweeter to point a few) where ideas and code are exchanged.

January 5, 2013

Original method to iterate the bits within an integer

January 2, 2013

Why I am using Delphi for all my development

January 1, 2013

What programming languages have you used this year?