tags:

views:

131

answers:

2

Hello!

I have a byte array, as follows:

byte[] array = new byte[] { 0xAB, 0x7B, 0xF0, 0xEA, 0x04, 0x2E, 0xF3, 0xA9};

The task is to find the quantity of occurrences '0xA' in it. Could you advise what to do? The answer is 6.

A: 

If you treat the entire array as a single bit-string:

0xAB,    0x7B,    0xF0,    0xEA,    0x04,    0x2E,    0xF3,    0xA9 is then:
10101011 01111011 11110000 11101010 00000100 00101110 11110011 10101001
====                         ====                              ====
  ====                         ====                              ====

This has 1010 occurring 6 times.

If you don't try to match across byte boundaries, you could try something like the following (tested in Perl and translated by hand):

int counter = 0;
for (int i = 0; i < array.length; ++i)
{
    for (int bits = 0xA0, mask = 0xF0; bits >= 0x0A; bits >>= 1, mask >>= 1)
    {
        if ((array[i] & mask) == bits)
            ++counter;
    }
}

To match across byte boundaries, you have to shift the bits in from the next byte. Try something like this (tested in Perl and translated by hand):

int counter = 0;
byte tester = array[0];

for (int i = 1; i < array.length + 1; ++i)
{
    byte nextByte = i < array.length ? array[i] : 0;

    for (int bit = 0; bit < 8; ++bit)
    {
        if ((tester & 0xF0) == 0xA0)
            ++counter;

        tester <<= 1;
        if ((nextByte & 0x80) != 0)
            tester |= 1;

        nextByte <<= 1;
    }
}

Both programs count 6 as there are no 1010 sequences across byte-boundaries in this example.

Adrian Pronk
No, they have. The point is:first element in array is 10101011. It means that it has at least 21010 (8-4 bits) and 1010 (6-2 bits).I should check for each occurrence. The problem is that I cannot go outside byte boundaries.
Spaniard
I should find 1010 (this is 0xA).
Spaniard
So I should check first 4 bits (8-5) then I should shift (?) right and compare another 4 bits. And I should do it up to end of the array.I tried to work with BitArray: BitArray arr = new BitArray(array);But couldn't comnpare.
Spaniard
Thank you very much, but this example doesn't work.It found 17 occurrences instead of 6.
Spaniard
Spaniard
Now - 25 occurrences
Spaniard
Adrian Pronk
Spaniard
Thank you! It works =))))))
Spaniard
By the way, could you explain what is happening there?
Spaniard
You're looking for 1010 bit patterns so you AND with the mask 1111 so that all other bits are set to zero, then you see if what remains is 1010
Adrian Pronk
Thanks! Does it go outside the boundaries?
Spaniard
By the way, how it will work without mask?
Spaniard
yes, it doesn't cross the boundaries
Spaniard
Sorry, it works =)
Spaniard
A: 

So from your comment, you want the total count of appearances of the bit pattern 1010 in the bytes in your array.

For a given byte b, the count is the sum of

(b & 0x0A) == 0x0A ? 1 : 0
(b & 0x14) == 0x14 ? 1 : 0
(b & 0x28) == 0x28 ? 1 : 0
(b & 0x50) == 0x50 ? 1 : 0
(b & 0xA0) == 0xA0 ? 1 : 0

(left as an exercise: what is this doing?)

Put this in a function, call it for each byte in the array, sum the results.

AakashM
Thank you! I'll try
Spaniard