Reading bits from byte (in a file)

[Oyvind Eriksen]

Hello.
I need to read bits from bytes in a file.
I have code that works but it's very slow.
Can anybody help me?
The code I have is:

private bool GetBit(byte b, int pos)
{
return ((b & (byte)(1 << pos)) != 0);
}
private int GetBits(byte b, int offset, int count)
{
int number = 0;
for (int i = 1; i <= count; i++)
{
if (GetBit(b, offset + i - 1))
{
switch (i)
{
case 1:
number += 1;
break;
case 2:
number += 2;
break;
case 3:
number += 4;
break;
case 4:
number += 8;
break;
case 5:
number += 16;
break;
case 6:
number += 32;
break;
case 7:
number += 64;
break;
case 8:
number += 128;
break;
}
}
}
return number;
}

Thank you in advance!
Oyvind Eriksen

[Tim Van Wassenhove]

On 2006-06-25, Oyvind Eriksen <oyvind> wrote:

private bool GetBit(byte b, int pos)
{
return ((b & (byte)(1 << pos)) != 0);
}
private int GetBits(byte b, int offset, int count)
{
int number = 0;
for (int i = 1; i <= count; i++)
{
if (GetBit(b, offset + i - 1))
{
switch (i)
{
case 1:
number += 1;
break;
case 2:
number += 2;
break;
case 3:
number += 4;
break;
case 4:
number += 8;
break;
case 5:
number += 16;
break;
case 6:
number += 32;
break;
case 7:
number += 64;
break;
case 8:
number += 128;
break;
}
}
}
return number;
}

How about:

private static int GetBits2(byte b, int offset, int count)
{
int result = 0;
int pow = 1;

b >>= offset;
for (int i = 0; i < count; ++i)
{
if (((byte)1 & b) == 1)
{
result += pow;
}

b >>= 1;
pow *= 2;
}

return result;
}
--
Met vriendelijke groeten,
Tim Van Wassenhove <http://timvw.madoka.be >

[Barry Kelly]

"Oyvind Eriksen" <oyvind -(at)- eriksen.cn> wrote:

I need to read bits from bytes in a file.
I have code that works but it's very slow.
Can anybody help me?

You appear to be trying to get the value of a bitfield in a byte. Try
this code:

---8<---
static int GetBits3(byte b, int offset, int count)
{
return (b >> offset) & ((1 << count) - 1);
}
--->8---

My tests show it's about 8 times faster.

-- Barry

--
http://barrkel.blogspot.com/

[Oyvind Eriksen]

Thank you so much!
Can you explain how that code works? Or send me to a website that explains
that?
I'm somewhat new to C# and haven't figured out the consept you used and I'm
eager to learn.

Again, thank you!
Oyvind Eriksen

"Barry Kelly" <ba***********@ gmail.com> wrote in message
news:f5******** *************** *********@4ax.c om...

"Oyvind Eriksen" <oyvind -(at)- eriksen.cn> wrote:

I need to read bits from bytes in a file.
I have code that works but it's very slow.
Can anybody help me?

You appear to be trying to get the value of a bitfield in a byte. Try
this code:

---8<---
static int GetBits3(byte b, int offset, int count)
{
return (b >> offset) & ((1 << count) - 1);
}
--->8---

My tests show it's about 8 times faster.

-- Barry

--
http://barrkel.blogspot.com/

[Barry Kelly]

"Oyvind Eriksen" <oyvind -(at)- eriksen.cn> wrote:

Thank you so much!
Can you explain how that code works? Or send me to a website that explains
that?
I'm somewhat new to C# and haven't figured out the consept you used and I'm
eager to learn.

---8<---
static int GetBits3(byte b, int offset, int count)
{
return (b >> offset) & ((1 << count) - 1);
}
--->8---

You've got a set of bits in memory that look like this:

00000000

The offset is zero-based, and starts counting from the right.
The count is the number of bits to get. For a (offset, count) of (2,4),
you'd be trying to get these bits:

GGxxxxGG

(I'm using 'xxxx' to represent the bits you're trying to get at, and G
to indicate Garbage that we don't want in the result.)

The three operations used in the code above are >> (shift right), <<
(shift left) and & ("AND" or "mask").

The first step is to move the interesting bits to the right until they
start at offset zero. So, we shift the bits to the right with shift
right (>>) offset times:

GGxxxxGG >> offset => 00GGxxxx

So now we have all our interesting bits positioned from 0..count-1
(counting bits from the right-most place). (0 got shifted in from the
left, because byte is an unsigned number.)

The next thing to do is to remove any uninteresting bits that extend to
the left of our bitfield. For example, the original byte might look like
this:

01001011

after shifting by 2, it would look like:

00010010
____^^^^___ interesting bits

You can see here that any bits left over, to the left of our interesting
bits, would corrupt our result. So, we need to mask them out with the &
operator (the "and" operator).

The value we'd like to use to mask these bits out is "count '1's". For a
count of 4, we need 1111; for a count of 6, we'd need 111111. So, for
our count of 4, we'd like to perform this mask operation:

00GGxxxx
00001111 &
--------
0000xxxx

This removes the garbage because any number and'd with '0' produces 0.

So, the only question is how to turn 'count' into our mask. The way this
is done is simple: every power of two is one more than the sum of the
previous positive powers of two.

For example consider 8, which is 2^3:

2^0 + 2^1 + 2^2 + 1
= 1 + 2 + 4 + 1 = 8

Look at it another way, in binary. Every power of 2 in binary consists
of exactly one digit:

2^0 = 1 = 1
2^1 = 2 = 10
2^2 = 4 = 100
2^3 = 8 = 1000
2^4 = 16 = 10000

What happens when you subtract 1 from these powers of two? You end up
with all the 0's to the right of the 1 becoming 1:

2^0 - 1 = 0 = 0
2^1 - 1 = 1 = 1
2^2 - 1 = 3 = 11
2^3 - 1 = 7 = 111
2^4 - 1 = 15 = 1111

So, here's where the << operator comes in. Shift 1 left by count times,
and you get 2^count. For example, 2^3 = 1 << 3:

1 << 3 = 1000 = 8

So, hopefully you can see where it all comes together. 1 << count is
2^count, and when you subtract 1, that makes all the lesser bits 1 -
which is exactly what we want out of the mask. Getting back to our byte:

00GGxxxx

Our count is 4, so we take 1 << 4:

00010000

And we subtract one:

00001111

This is the mask that's used with earlier, shifted number:

00GGxxxx
00001111 &
--------
xxxx

This mask works because any digit AND'd with 1 remains unchanged.

OK. No more homework for me unless I go back to college :)

-- Barry

--
http://barrkel.blogspot.com/

[Oyvind Eriksen]

Hello again.
I never got around to thank you for taking time to explain to me.
If you're not already a teacher, you should be.. :-)
I've never found an easy explaination like you wrote.
Now my program is up an running, at least the "alpha" version.

Again thank you!
I hope I can return the favor some day.

Regards,
Oyvind Eriksen
"Barry Kelly" <ba***********@ gmail.com> wrote in message
news:38******** *************** *********@4ax.c om...

"Oyvind Eriksen" <oyvind -(at)- eriksen.cn> wrote:

Thank you so much!
Can you explain how that code works? Or send me to a website that
explains
that?
I'm somewhat new to C# and haven't figured out the consept you used and
I'm
eager to learn.

> ---8<---
> static int GetBits3(byte b, int offset, int count)
> {
> return (b >> offset) & ((1 << count) - 1);
> }
> --->8---

You've got a set of bits in memory that look like this:

00000000

The offset is zero-based, and starts counting from the right.
The count is the number of bits to get. For a (offset, count) of (2,4),
you'd be trying to get these bits:

GGxxxxGG

(I'm using 'xxxx' to represent the bits you're trying to get at, and G
to indicate Garbage that we don't want in the result.)

The three operations used in the code above are >> (shift right), <<
(shift left) and & ("AND" or "mask").

The first step is to move the interesting bits to the right until they
start at offset zero. So, we shift the bits to the right with shift
right (>>) offset times:

GGxxxxGG >> offset => 00GGxxxx

So now we have all our interesting bits positioned from 0..count-1
(counting bits from the right-most place). (0 got shifted in from the
left, because byte is an unsigned number.)

The next thing to do is to remove any uninteresting bits that extend to
the left of our bitfield. For example, the original byte might look like
this:

01001011

after shifting by 2, it would look like:

00010010
____^^^^___ interesting bits

You can see here that any bits left over, to the left of our interesting
bits, would corrupt our result. So, we need to mask them out with the &
operator (the "and" operator).

The value we'd like to use to mask these bits out is "count '1's". For a
count of 4, we need 1111; for a count of 6, we'd need 111111. So, for
our count of 4, we'd like to perform this mask operation:

00GGxxxx
00001111 &
--------
0000xxxx

This removes the garbage because any number and'd with '0' produces 0.

So, the only question is how to turn 'count' into our mask. The way this
is done is simple: every power of two is one more than the sum of the
previous positive powers of two.

For example consider 8, which is 2^3:

2^0 + 2^1 + 2^2 + 1
= 1 + 2 + 4 + 1 = 8

Look at it another way, in binary. Every power of 2 in binary consists
of exactly one digit:

2^0 = 1 = 1
2^1 = 2 = 10
2^2 = 4 = 100
2^3 = 8 = 1000
2^4 = 16 = 10000

What happens when you subtract 1 from these powers of two? You end up
with all the 0's to the right of the 1 becoming 1:

2^0 - 1 = 0 = 0
2^1 - 1 = 1 = 1
2^2 - 1 = 3 = 11
2^3 - 1 = 7 = 111
2^4 - 1 = 15 = 1111

So, here's where the << operator comes in. Shift 1 left by count times,
and you get 2^count. For example, 2^3 = 1 << 3:

1 << 3 = 1000 = 8

So, hopefully you can see where it all comes together. 1 << count is
2^count, and when you subtract 1, that makes all the lesser bits 1 -
which is exactly what we want out of the mask. Getting back to our byte:

00GGxxxx

Our count is 4, so we take 1 << 4:

00010000

And we subtract one:

00001111

This is the mask that's used with earlier, shifted number:

00GGxxxx
00001111 &
--------
xxxx

This mask works because any digit AND'd with 1 remains unchanged.

OK. No more homework for me unless I go back to college :)

-- Barry

--
http://barrkel.blogspot.com/