CODEWITHSUNDEEP
c#arraysbit-manipulation
Dave Henry
Dave Henry

Reputation: 31

Removing leading 0s in a byte array

I have a byte array as follows - 

byte[] arrByt = new byte[] { 0xF, 0xF, 0x11, 0x4 };

so in binary arrByt = 00001111 00001111 00010001 000000100

Now I want to create a new byte array by removing leading 0s for each byte from arrByt

arrNewByt = 11111111 10001100 = { 0xFF, 0x8C };

I know that this can be done by converting the byte values into binary string values, removing the leading 0s, appending the values and converting back to byte values into the new array. However this is a slow process for a large array.

Is there a faster way to achieve this (like logical operations, bit operations, or other efficient ways)?

Thanks.

Upvotes: 3

Views: 869

Answers (3)

Torben Schramme
Torben Schramme

Reputation: 2140

This should do the job quite fast. At least only standard loops and operators. Give it a try, will also work for longer source arrays.

// source array of bytes
var arrByt = new byte[] {0xF, 0xF, 0x11, 0x4 };

// target array - first with the size of the source array
var targetArray = new byte[arrByt.Length];

// bit index in target array
// from left = byte 0, bit 7 = index 31; to the right = byte 4, bit 0 = index 0
var targetIdx = targetArray.Length * 8 - 1;

// go through all bytes of the source array from left to right
for (var i = 0; i < arrByt.Length; i++)
{
    var startFound = false;

    // go through all bits of the current byte from the highest to the lowest
    for (var x = 7; x >= 0; x--)
    {
        // copy the bit if it is 1 or if there was already a 1 before in this byte
        if (startFound || ((arrByt[i] >> x) & 1) == 1)
        {
            startFound = true;

            // copy the bit from its position in the source array to its new position in the target array
            targetArray[targetArray.Length - ((targetIdx / 8) + 1)] |= (byte) (((arrByt[i] >> x) & 1) << (targetIdx % 8));

            // advance the bit + byte position in the target array one to the right
            targetIdx--;
        }
    }
}

// resize the target array to only the bytes that were used above
Array.Resize(ref targetArray, (int)Math.Ceiling((targetArray.Length * 8 - (targetIdx + 1)) / 8d));

// write target array content to console
for (var i = 0; i < targetArray.Length; i++)
{
    Console.Write($"{targetArray[i]:X} ");
}

// OUTPUT: FF 8C

Upvotes: 1

neelesh bodgal
neelesh bodgal

Reputation: 662

Please check this code snippet. This might help you.

        byte[] arrByt = new byte[] { 0xF, 0xF, 0x11, 0x4 };
        byte[] result = new byte[arrByt.Length / 2];

        var en = arrByt.GetEnumerator();

        int count = 0;
        byte result1 = 0;
        int index = 0;
        while (en.MoveNext())
        {
            count++;
            byte item = (byte)en.Current;

            if (count == 1)
            {
                while (item < 128)
                {
                    item = (byte)(item << 1);
                }
                result1 ^= item;
            }

            if (count == 2)
            {
                count = 0;
                result1 ^= item;

                result[index] = result1;
                index++;
                result1 = 0;
            }
        }

        foreach (var s in result)
        {
            Console.WriteLine(s.ToString("X"));
        }

Upvotes: 0

mdiehl13
mdiehl13

Reputation: 492

If you are trying to find the location of the most-significant bit, you can do a log2() of the byte (and if you don't have log2, you can use log(x)/log(2) which is the same as log2(x))

For instance, the number 7, 6, 5, and 4 all have a '1' in the 3rd bit position (0111, 0110, 0101, 0100). The log2() of them are all between 2 and 2.8. Same thing happens for anything in the 4th bit, it will be a number between 3 and 3.9. So you can find out the Most Significant Bit by adding 1 to the log2() of the number (round down).

floor(log2(00001111)) + 1 == floor(3.9) + 1 == 3 + 1 == 4

You know how many bits are in a byte, so you can easily know the number of bits to shift left:

int numToShift = 8 - floor(log2(bytearray[0])) + 1;
shiftedValue = bytearray[0] << numToShift;

From there, it's just a matter of keeping track of how many outstanding bits (not pushed into a bytearray yet) you have, and then pushing some/all of them on.

The above code would only work for the first byte array. If you put this in a loop, the numToShift would maybe need to keep track of the latest empty slot to shift things into (you might have to shift right to fit in current byte array, and then use the leftovers to put into the start of the next byte array). So instead of doing "8 -" in the above code, you would maybe put the starting location. For instance, if only 3 bits were left to fill in the current byte array, you would do:

int numToShift = 3 - floor(log2(bytearray[0])) + 1;

So that number should be a variable:

int numToShift = bitsAvailableInCurrentByte - floor(log2(bytearray[0])) + 1;

Upvotes: 0

Related Questions