C# - What's the fastest way to convert a number to the smallest BitArray-CodePudding

I would like to convert a number to a BitArray, with the resulting BitArray only being as big as it needs to be.

For instance:

BitArray tooBig = new BitArray(new int[] { 9 });

results in a BitArray with a length of 32 bit, however for the value 9 only 4 bits are required. How can I create BitArrays which are only as long as they need to be? So in this example, 4 bits. Or for the number 260 I expected the BitArray to be 9 bits long

CodePudding user response：

You can figure out all the bits first and then create the array by checking if the least significant bit is 1 or 0 and then right shifting until the number is 0. Note this will not work for negative numbers where the 32nd bit would be 1 to indicate the sign.

public BitArray ToShortestBitArray(int x)
{
    var bits = new List<bool>();
    while(x > 0)
    {
        bits.Add((x & 1) == 1);
        x >>= 1;
    }
    
    return new BitArray(bits.ToArray());
}

CodePudding user response：

Assuming you are working with exclusively unsigned integers, the number of bits you need is equal to the base 2 logarithm of the (number 1), rounded up.

CodePudding user response：

Counting the bits is probably the easiest solution.

In JavaScript for example...

// count bits needed to store a positive number
const bits = (x, b = 0) => x > 0 ? bits(x >> 1, b   1) : b;