CODEWITHSUNDEEP
c#
hmdb
hmdb

Reputation: 323

Fastest way to increment a BitArray (binary number) by one?

The following "Increment" method is working perfectly. But I wanted to know is there any faster way to do this in less steps.

    public BitArray Increment(BitArray bArray)
    {
        carry = true;

        for (i = 0; i < 32; i++)
        {
            if (carry)
            {
                if (bArray[i] == false)
                {
                    bArray[i] = true;
                    carry = false;
                }
                else
                {
                    bArray[i] = false;
                    carry = true;
                }
            }
        }
        return bArray;
    }

Thanks....

Upvotes: 3

Views: 3354

Answers (3)

HABO
HABO

Reputation: 15816

Without overflow handling:

for (int i = 0; i < 32 && !(bitArray[i] = !bitArray[i++]););

C-derived for loops always cry out for obscurity.

Upvotes: 1

Greg Hewgill
Greg Hewgill

Reputation: 992787

You can certainly write this in fewer steps and no branching:

bool newbit = bArray[i] ^ carry;
carry = bArray[i] & carry;
bArray[i] = newbit;

This bit of code can be generalised to a full adder, not just an incrementer.

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1499860

There's one very obvious improvement you can make: stop when you're done!

public void Increment(BitArray bArray)
{
    for (int i = 0; i < 32; i++)
    {
        bool previous = bArray[i];
        bArray[i] = !previous;
        if (!previous)
        {
            // Found a clear bit - now that we've set it, we're done
            return;
        }
    }
}

Alternatively, if you're really only got 32 bits (and will only ever have 32 bits), why not just use an int instead? Incrementing that is really easy! You could always wrap it in your own custom struct if you want.

Upvotes: 5

Related Questions