Original method to iterate the bits within an integer

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