Bit twiddling

[grid]

Hi,
I have written a couple of programs which just prints the bits in
both directions.Would appreciate any help to refine them a bit.

1.
#include<stdio.h>
#include<limits.h>
void printbits_reverse(unsigned char a){
int i;
for(i=0 ; i < CHAR_BIT ; i++)
((0x1<<i) & a) ? printf("1") : printf("0"); }
int main()
{
unsigned char a = 0x96;
printbits_reverse(a);
return 0;
}

Now here the loop dosent look the best of code.How can I refine it to
better and generic code ?

2.
#include<stdio.h>
struct twid{
unsigned :24; /* skip bits 31 -> 8 for big-endian machines */
unsigned bit1:1;
unsigned bit2:1;
unsigned bit3:1;
unsigned bit4:1;
unsigned bit5:1;
unsigned bit6:1;
unsigned bit7:1;
unsigned bit8:1;
};

void print(struct twid *tw)
{
tw->bit1?printf("1")rintf("0");
tw->bit2?printf("1")rintf("0");
tw->bit3?printf("1")rintf("0");
tw->bit4?printf("1")rintf("0");
tw->bit5?printf("1")rintf("0");
tw->bit6?printf("1")rintf("0");
tw->bit7?printf("1")rintf("0");
tw->bit8?printf("1")rintf("0");
printf("\n");
}

int main()
{
unsigned val = 0x96;
struct twid *tw = (struct twid *) &val ;
print(tw);
return 0;
}

This is not a generic code ( a bit platform specific), but that long
list of printf's in the print function isnt again a very decent way.Can
I use a loop or any construct to print the values ?

TIA,

 

[pete]

Hi,
I have written a couple of programs which just prints the bits in
both directions.Would appreciate any help to refine them a bit.

1.
#include<stdio.h>
#include<limits.h>
void printbits_reverse(unsigned char a){
int i;
for(i=0 ; i < CHAR_BIT ; i++)
((0x1<<i) & a) ? printf("1") : printf("0"); }
int main()
{
unsigned char a = 0x96;
printbits_reverse(a);
return 0;
}

Now here the loop dosent look the best of code.How can I refine it to
better and generic code ?

#include<stdio.h>
#include<limits.h>

void printbits_reverse(unsigned char a);
void bit_str(char *s1, const void *s2, size_t n);
unsigned char bit_rev(unsigned char byte);

int main(void)
{
unsigned char a = 0x96;

printbits_reverse(a);
return 0;
}

void printbits_reverse(unsigned char a)
{
char string[CHAR_BIT + 1];

a = bit_rev(a);
bit_str(string, &a, 1);
puts(string);
}

void bit_str(char *s1, const void *s2, size_t n)
{
unsigned mask;
const unsigned char *const byte = s2;

while (n-- != 0) {
mask = ((unsigned char)-1 >> 1) + 1;
do {
*s1++ = (char)(mask & byte[n] ? '1' : '0');
mask >>= 1;
} while (mask != 0);
}
*s1 = '\0';
}

unsigned char bit_rev(unsigned char byte)
{
unsigned hi_mask, lo_mask;

hi_mask = ((unsigned char)-1 >> 1) + 1;
lo_mask = 1;
do {
if (!(byte & hi_mask) != !(byte & lo_mask)) {
byte ^= hi_mask | lo_mask;
}
hi_mask >>= 1;
lo_mask <<= 1;
} while (hi_mask > lo_mask);
return byte;
}

 

[Paul Mesken]

Hi,
I have written a couple of programs which just prints the bits in
both directions.Would appreciate any help to refine them a bit.

1.
#include<stdio.h>
#include<limits.h>
void printbits_reverse(unsigned char a){
int i;
for(i=0 ; i < CHAR_BIT ; i++)
((0x1<<i) & a) ? printf("1") : printf("0"); }

Oh, I don't think it's too bad but an obvious optimization would be to
make a string (instead of printing each digit individually) and then
print that string.

void printbits_reverse(unsigned char a)
{
int i;
char MyBitstring[CHAR_BIT + 1];

for (i = 0; i < CHAR_BIT; ++ i)
{
if (a & 1)
MyBitstring = '1';
else
MyBitstring = '0';
a >>= 1;
}
MyBitstring[CHAR_BIT] = '\0';
printf("%s", MyBitstring);
return;
}

2.
#include<stdio.h>
struct twid{
unsigned :24; /* skip bits 31 -> 8 for big-endian machines */
unsigned bit1:1;
unsigned bit2:1;
unsigned bit3:1;
unsigned bit4:1;
unsigned bit5:1;
unsigned bit6:1;
unsigned bit7:1;
unsigned bit8:1;
};

void print(struct twid *tw)
{
tw->bit1?printf("1")rintf("0");
tw->bit2?printf("1")rintf("0");
tw->bit3?printf("1")rintf("0");
tw->bit4?printf("1")rintf("0");
tw->bit5?printf("1")rintf("0");
tw->bit6?printf("1")rintf("0");
tw->bit7?printf("1")rintf("0");
tw->bit8?printf("1")rintf("0");
printf("\n");
}

int main()
{
unsigned val = 0x96;
struct twid *tw = (struct twid *) &val ;
print(tw);
return 0;
}

This is not a generic code ( a bit platform specific), but that long
list of printf's in the print function isnt again a very decent way.Can
I use a loop or any construct to print the values ?

It's ugly, unportable and relies on unspecified behaviour (you cannot
know whether bitfields are laid out from left to right or vice versa).

 

[Paul Mesken]

void printbits_reverse(unsigned char a)
{
int i;
char MyBitstring[CHAR_BIT + 1];

for (i = 0; i < CHAR_BIT; ++ i)
{
if (a & 1)
MyBitstring = '1';
else
MyBitstring = '0';
a >>= 1;
}
MyBitstring[CHAR_BIT] = '\0';
printf("%s", MyBitstring);
return;
}

By the way, just for fun :

for (i = 0; i < CHAR_BIT; ++ i)
{
MyBitstring = '0' + (a & 1);
a >>= 1;
}

But I don't know whether '1' is 1 greater than '0' in every character
set that C supports (but it's okay for both EBCDIC and ASCII).

 

[Walter Roberson]

But I don't know whether '1' is 1 greater than '0' in every character
set that C supports (but it's okay for both EBCDIC and ASCII).

Yes, that is a requirement in the standard. Sequentially increasing
digits is the -only- ordering requirements that the C89 standard
imposes on the character set.

 

[Paul Mesken]

Yes, that is a requirement in the standard. Sequentially increasing
digits is the -only- ordering requirements that the C89 standard
imposes on the character set.

Yes, you're right :

5.2.1 Character Sets

..... In both the source and execution basic character sets, the value
of each character after '0' in the above list of decimal digits shall
be one greater than the value of the previous....

Well, in that case : go for the second solution, Grid

 

[CBFalconer]

.... snip ...

Oh, I don't think it's too bad but an obvious optimization would be
to make a string (instead of printing each digit individually) and
then print that string.

It's just printing a number in base 2. In the last day or two I
posted a routine to output numbers to streams in various bases.
Search for unum2txt.

 

[Old Wolf]

Oh, I don't think it's too bad but an obvious optimization would be to
make a string (instead of printing each digit individually) and then
print that string.

Is that really an optimisation? It uses more memory, and stdout
is probably buffered anyway.

This solution 'optimises' by using putchar instead of printf (surely
that must be at least as fast), and is still as concise as the
original:

for (i = 0; i < CHAR_BIT; i++)
putchar( ((1 << i) & a) ? '1' : '0' );
putchar('\n');

 

[Paul Mesken]

Is that really an optimisation? It uses more memory, and stdout
is probably buffered anyway.

Reducing the amount of calls (especially to big ones, like printf) is,
typically, an optimization (reducing the overhead that may accompany
the calls). Although this might not hold for functions that are very
small and are inlined by the compiler but I don't believe printf is
inlined. I wouldn't worry too much about the extra memory used by an
array of CHAR_BIT + 1 chars

This solution 'optimises' by using putchar instead of printf (surely
that must be at least as fast), and is still as concise as the
original:

for (i = 0; i < CHAR_BIT; i++)
putchar( ((1 << i) & a) ? '1' : '0' );
putchar('\n');

This is better than the OPs printf function, but IMHO not better than
my second version (adding "a & 1" to '0') which eliminates the
implicit "if-else" of the "?:" operator and only one call to printf.

 

[grid]

void print(struct twid *tw)

{
tw->bit1?printf("1")rintf("0");
tw->bit2?printf("1")rintf("0");
tw->bit3?printf("1")rintf("0");
tw->bit4?printf("1")rintf("0");
tw->bit5?printf("1")rintf("0");
tw->bit6?printf("1")rintf("0");
tw->bit7?printf("1")rintf("0");
tw->bit8?printf("1")rintf("0");
printf("\n");

Is there any way to traverse through the member bitfields with a loop or
is there a consise way to write the above stuff.

TIA

 

[Paul Mesken]

Is there any way to traverse through the member bitfields with a loop or
is there a consise way to write the above stuff.

No, because you cannot have an array of bitfields (something like
"signed int Bit[8]:1;").

Just *don't* use bitfields in this case. You cannot know in which
order they are represented (left to right or right to left).

For example :

union
{
int MyInteger;
struct
{
unsigned int Bit1:1;
unsigned int Bit2:1;
....
unsigned int Bit8:1;
} Bits;
}MyUnion;

Let's say that the compiler stores your bitfields in an integer the
same size as MyInteger (but, in reality, you don't know this).

Still, you cannot be sure whether Bit1 is bit 0 of that integer or bit
31 (if int is 32 bits).

By the way : the least significant bit of some value is, typically,
not called "bit 1" but "bit 0".

The whole use of bitfields, in your case, is highly unportable. It
just might happen to work okay for your compiler (sheer luck) but on
another it might not work as you expected.

It's also not faster at all (if you thought it was). Behind the
scenes, the compiler is, typically, doing all kinds of masking,
shifting, etc. in order to use, store or read the bitfield.

Don't use bitfields just because they are part of C. There are better
ways (both portability- and performance-wise) to achieve what you want
to achieve and they have been posted.

Remember what K&R2 says about bitfields :

"Almost everything about fields is implementation-dependent.".

What you try to do depends on the implementation. That's a _bad_
programming habit that should be avoided.

 

[Paul Mesken]

No, because you cannot have an array of bitfields (something like
"signed int Bit[8]:1;").

"usigned" might be a better choice, given the size of the field ;-)

 

[Keith Thompson]

No, because you cannot have an array of bitfields (something like
"signed int Bit[8]:1;").

Just *don't* use bitfields in this case. You cannot know in which
order they are represented (left to right or right to left).
Right.

[...]

Still, you cannot be sure whether Bit1 is bit 0 of that integer or bit
31 (if int is 32 bits).

By the way : the least significant bit of some value is, typically,
not called "bit 1" but "bit 0".

Whether bit 0 is the least or most significant bit is probably
system-specific; the bits in a 32-bit word might be numbered 0..31 or
31..0. Which way they're numbered is probably more a matter of
terminology than actual semantics, unless the CPU provides
instructions that take bit numbers as arguments.

Since C doesn't define any kind of numering for bits, the question
isn't relevant for portable code.

When you declare a bit field, you're asking the compiler to allocate a
bit in a structure. You're not telling it which one.

 

[Dik T. Winter]

> Whether bit 0 is the least or most significant bit is probably
> system-specific; the bits in a 32-bit word might be numbered 0..31 or
> 31..0. Which way they're numbered is probably more a matter of
> terminology than actual semantics, unless the CPU provides
> instructions that take bit numbers as arguments.

And if the instructions are consistent. That is not the case with all
processors...

 

[glen herrmannsfeldt]

And if the instructions are consistent. That is not the case with all
processors...

IBM machines derived from S/360 consistently number them with the
MSB as zero. The terminology gets a little confusing now that the
architecture has been extended to 64 bits. The old instructions now
operate on bits 32-63 of the general registers.

-- glen

 

[Dik T. Winter]

>
> IBM machines derived from S/360 consistently number them with the
> MSB as zero. The terminology gets a little confusing now that the
> architecture has been extended to 64 bits. The old instructions now
> operate on bits 32-63 of the general registers.

From memory, the 68k processors had different terminology for the bit
field and single bit instructions.

 

[Chris Croughton]

IBM machines derived from S/360 consistently number them with the
MSB as zero. The terminology gets a little confusing now that the
architecture has been extended to 64 bits. The old instructions now
operate on bits 32-63 of the general registers.

That's a good reason for numbering with 0 as LSB! European comms
specifications had the 'standard' of numbering 0 as MSB, I believe that
it got into some early RFCs as well (I've certainly seen it in some
non-European spec.s). Most confusing, especially when dealing with
multiple specifications in the same project (the lower layers have bit 0
as most significant, whereas the higher layers have bit 0 as LSB -- or
is it the other way round? Madness!)

Chris C

 

[Paul Mesken]

That's a good reason for numbering with 0 as LSB! European comms
specifications had the 'standard' of numbering 0 as MSB, I believe that
it got into some early RFCs as well (I've certainly seen it in some
non-European spec.s). Most confusing, especially when dealing with
multiple specifications in the same project (the lower layers have bit 0
as most significant, whereas the higher layers have bit 0 as LSB -- or
is it the other way round? Madness!)

I didn't even know that the MSB is called "bit 0" in some
specifications. It makes perfect sense to me that the LSB is called
"bit 0" since the value (for integer values) it represents is
(bitvalue * 2) ^ 0 (and for bit 1 : (bitvalue * 2) ^ 1, for bit 2 :
(bitvalue * 2) ^ 2, etc.).

 

[Joe Wright]

Dik T. Winter wrote:




That's a good reason for numbering with 0 as LSB! European comms
specifications had the 'standard' of numbering 0 as MSB, I believe that
it got into some early RFCs as well (I've certainly seen it in some
non-European spec.s). Most confusing, especially when dealing with
multiple specifications in the same project (the lower layers have bit 0
as most significant, whereas the higher layers have bit 0 as LSB -- or
is it the other way round? Madness!)

Chris C

In the end, happily, it doesn't matter. It's just a matter of notation.
It doesn't change the way the machine works, only how it's described in
the docs.

More interesting is a bit's value in time. Think of async serial bytes:
start bit, 8 data bits and stop bit. It is of crucial importance that we
know whether the bit after the start bit is the lsb or the msb of the
byte. I used to know. Really.

 

[Chris Croughton]

I didn't even know that the MSB is called "bit 0" in some
specifications.

Most of the CCITT ones, as I recall, and some of the OSI protocol specs
had it as well (they may have changed later).

It makes perfect sense to me that the LSB is called
"bit 0" since the value (for integer values) it represents is
(bitvalue * 2) ^ 0 (and for bit 1 : (bitvalue * 2) ^ 1, for bit 2 :
(bitvalue * 2) ^ 2, etc.).

It certainly does, but early specs tended to look at it from a graphical
point of view:

+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+

and it probably seemed more logical to number left to right.

An alternative explanation is that they were French <g>...

(Naughty Chris! Mustn't mock the French, they voted the right way on
the EU constitution. Perhaps one day they'll even forgive us for
Agincourt...)

I have a vague memory that early ICL mainframes were numbered MSB first
as well, but I could be wrong...

Just checked -- the RFC STD for IP has the MSB labelled as 0, see
http://www.faqs.org/rfcs/std/std5.html!

Chris C