bitwise operators(info)

[Ceriousmall]

Can anyone here point me towards any documentation that explains
bitwise operations in C in a simple manner. After K&R Chap 2.9
introduction to the bitwise operator I'm still in the dark. Basically
I take out my paper take two integers convert them into their binary
form and compare them using the rules of the bitwise operartors to
yield a result then convert that value back to decimal.......

 

[John Gordon]

Can anyone here point me towards any documentation that explains
bitwise operations in C in a simple manner. After K&R Chap 2.9

http://www.cprogramming.com/tutorial/bitwise_operators.html

 

[Morris Keesan]

Can anyone here point me towards any documentation that explains
bitwise operations in C in a simple manner. After K&R Chap 2.9
introduction to the bitwise operator I'm still in the dark. Basically
I take out my paper take two integers convert them into their binary
form and compare them using the rules of the bitwise operartors to
yield a result then convert that value back to decimal.......

The main place where you're going wrong here is in converting the value
back to decimal. I've found that in general, if I'm using bitwise
operations, I'm probably just interested in the individual bits of a
value, not in the numerical value of the entire number. E.g. various
Unix system calls deal with int values which are collections of flag
bits, so if you wanted to query the value of a flag you would use the
'&' operator, e.g.
if (my_flags & SOME_FLAG_BIT) { /* do something */ }
If you wanted to turn on that flag, it would be
my_flags |= SOME_FLAG_BIT
and to turn it off would be
my_flags &= ~SOME_FLAG_BIT

where SOME_FLAG_BIT is probably #defined as a power of two, typically
using an octal or hexadecimal constant, e.g.

#define FLAG_A 001
#define FLAG_B 002
#define FLAG_C 004
#define FLAG_D 010
etc.

 

[Ceriousmall]

Thanks for all the feed-back and the tutorial has been very
enlightening. Ive been at this all day from binary to hex to octal but
I'm beginning to get a grasp of it now.

 

[Keith Thompson]

If your number is an int, it is already in binary on any machine you're likely
to be using. You can use sscanf and sprintf to convert a decimal integer string
to/from a binary int.

In fact an int is represented in binary on any conforming
implementation; see C99 6.2.6.2.

 

[Harald van Dijk]

In fact an int is represented in binary on any conforming
implementation; see C99 6.2.6.2.

Only in the abstract machine. An integer may for example, in a
concrete translation of a program, very well be represented as a
string/float if the implementation determines that the value will not
be used for anything else than a conversion to a string/float. Or a
compiler may load an integer in a floating point register, because a
floating point register happens to be available and all integer
registers are already in use. Or, although I doubt it would be a good
idea, a conforming implementation of C could be created for a ternary
machine, converting behind the scenes between binary and ternary as
required.

 

[Eric Sosman]

In fact an int is represented in binary on any conforming
implementation; see C99 6.2.6.2.

I've invented a four-state device that is 7% faster, 18% less
power-hungry, and 31% cheaper to manufacture than a pair of two-
state devices. I'm building a revolutionary new computer based on
these devices, storing values as 0,1,2,3 "quits" instead of as pairs
of 0,1 "bits." Is my C implementation doomed to be non-conforming?

 

[Keith Thompson]

I've invented a four-state device that is 7% faster, 18% less
power-hungry, and 31% cheaper to manufacture than a pair of two-
state devices. I'm building a revolutionary new computer based on
these devices, storing values as 0,1,2,3 "quits" instead of as pairs
of 0,1 "bits." Is my C implementation doomed to be non-conforming?

Not if you manage to make it *look* like everything is made of bits.

 

[Joe Pfeiffer]

Can anyone here point me towards any documentation that explains
bitwise operations in C in a simple manner. After K&R Chap 2.9
introduction to the bitwise operator I'm still in the dark. Basically
I take out my paper take two integers convert them into their binary
form and compare them using the rules of the bitwise operartors to
yield a result then convert that value back to decimal.......

You're not going to like this, but: that section strikes me as crystal
clear -- you just need to think in binary. The bitwise operators are
about, well, bits. Translating back and forth to decimal adds a bunch
of complexity, and makes things much harder to understand.

Translating back and forth to octal or hex is pretty much automatic once
you're really thinking in binary.

 

[Kaz Kylheku]

I've invented a four-state device that is 7% faster, 18% less
power-hungry, and 31% cheaper to manufacture than a pair of two-
state devices. I'm building a revolutionary new computer based on
these devices, storing values as 0,1,2,3 "quits" instead of as pairs
of 0,1 "bits." Is my C implementation doomed to be non-conforming?

I always suspected you'd be calling it quits.

 

[Ben Bacarisse]

Only in the abstract machine.

Surely that's a misuse of "only"? Something that is "only" true in C's
abstract machine, it true as far as any conforming C program in
concerned.

An integer may for example, in a
concrete translation of a program, very well be represented as a
string/float if the implementation determines that the value will not
be used for anything else than a conversion to a string/float. Or a
compiler may load an integer in a floating point register, because a
floating point register happens to be available and all integer
registers are already in use. Or, although I doubt it would be a good
idea, a conforming implementation of C could be created for a ternary
machine, converting behind the scenes between binary and ternary as
required.

That's all true, but I'd still say that the numbers are represented in
binary because that whole idea is an abstract one. Look deep enough
into any implementation and the binary data vanishes eventually. It's
the abstractions that matter to programmers.

 

[James Kuyper]

Surely that's a misuse of "only"? Something that is "only" true in C's
abstract machine, it true as far as any conforming C program in
concerned.

No, things that are true in the abstract machine may be false in the
real machine. All that's actually required is that the C implementation
produce the same results as it would if they were true. That's the whole
point of the concept of the abstract machine.

 

[Kaz Kylheku]

No, things that are true in the abstract machine may be false in the
real machine.

Perhaps:

Things that are true OF the abstract machine may be false OF the real
machine.

Things that are true IN the abstract machine are true IN the real one.

All that's actually required is that the C implementation
produce the same results as it would if they were true. That's the whole
point of the concept of the abstract machine.

Determining what the output should be is an overwhelmingly large
and broadly encompassing point.

 

[Harald van Dijk]

Surely that's a misuse of "only"?  Something that is "only" true in C's
abstract machine, it true as far as any conforming C program in
concerned.

Pretty much, yes. I didn't read Devil with the China Blue Dress's
message as applying to the abstract machine, so I objected to a
correction that did. I fully agree with you that an otherwise strictly
conforming program must not be able to tell the difference, so from
the point of view of anyone writing C code, it doesn't matter.

 

[Ben Bacarisse]

No, things that are true in the abstract machine may be false in the
real machine.

True (except for the peculiar choice of the first word).

All that's actually required is that the C implementation
produce the same results as it would if they were true.
Yup.

That's the whole
point of the concept of the abstract machine.

Indeed. Where is it that you are disagreeing with me, or did you mean
to start "Yes, things that are true..."?

 

[Ceriousmall]

(K&R Exercise 2-6)
Write a function setbits(x,p,n,y) that returns x with the n bits that
begin
at position p set to the rightmost n bits of y, leaving the other bits
unchanged.

** p set to the rightmost n bits of y ** This has me at a loss as to
he role
of P. P is passed to the function as one value then reset to the n
most of y

my code thus far......
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
unsigned mask = ~(~0 << n);

***************************************
* /* p = y & mask; */ *
* /* return x & (mask << (p+1-n)) */ *
* first attempt *
***************************************
return x & (mask << ((((p & 0) | mask) & y)+1-n));
} second attempt and still trying

Im not looking for the answer as I'd really like to work this out for
myself but rather some pointers on where I'm going wrong here or where
my interpretation has gone wrong.

 

[Keith Thompson]

return x & (mask << ((((p & 0) | mask) & y)+1-n));

[...]

p & 0 is always 0.

 

[Shao Miller]

Not if you manage to make it *look* like everything is made of bits.

Yeah. A difference that makes no difference is no difference.

The context is "bitwise operators," which work with bits. Since
inspecting the object representation must be possible, any difference
between abstract machine and physical representation seems out-of-scope.

 

[Ben Bacarisse]

I've fixed up line breaks. There's something odd about the look of your
posts.

(K&R Exercise 2-6)
Write a function setbits(x,p,n,y) that returns x with the n bits that
begin at position p set to the rightmost n bits of y, leaving the
other bits unchanged.

** p set to the rightmost n bits of y ** This has me at a loss as to
[t]he role of P. P is passed to the function as one value then reset
to the n most of y

No, p is not set at all. Your quote "p set to the rightmost bits..." is
out of context. Its is "the n bits that begin at position p" that get
set.

my code thus far......
unsigned setbits(unsigned x, int p, int n, unsigned y)

Good. Always do bit operations on unsigned quantities if you can.
Personally, I'd also make n and p unsigned since it makes no sense to
call setbits with either n or p < 0.

{
unsigned mask = ~(~0 << n);

***************************************
* /* p = y & mask; */ *
* /* return x & (mask << (p+1-n)) */ *
* first attempt *
***************************************
return x & (mask << ((((p & 0) | mask) & y)+1-n));
} second attempt and still trying

Im not looking for the answer as I'd really like to work this out for
myself but rather some pointers on where I'm going wrong here or where
my interpretation has gone wrong.

Try something simpler. Soon the exercise will itself look simple.
First, write a function clearbits(x, p, n) that returns x with the n
bits starting at position n cleared (zeroed). If that's too tricky,
image what you'd write if p was always zero. How would that code have
to change when p > 0?

Next write rightmost(y, n) that returns the right-most n bits of y. How
can you use rightmost and clearbits to write setbits?

 

[ImpalerCore]

(K&R Exercise 2-6)
Write a function setbits(x,p,n,y) that returns x with the n bits that
begin
at position p set to the rightmost n bits of y, leaving the other bits
unchanged.

** p set to the rightmost n bits of y ** This has me at a loss as to
he role
of P. P is passed to the function as one value then reset to the n
most of y

When faced with difficulty, it often helps to start with a concrete
example.

Let me rename the variables a little bit. Having this many single
letter variables is awful for the next person who needs to read it.

setbits( word, index, width, field )

Consider an unsigned 32-bit integer 'word' with the value 0x76543210.
It's binary representation is

0111 0110 0101 0100 0011 0010 0001 0000

Within the 'word', there is a 'field' of 'width' 8 that you want to
set, let's say 0xA1. It's binary representation is

0000 0000 0000 0000 0000 0000 1010 0001
\ /
width=8

For a given 'index' (12) in 'word', set the corresponding bits in
'word' so that the final result is '0x765 A1 210' or

msb lsb
0111 0110 0101 1010 0001 0010 0001 0000
\
index

Think of this as a two part problem. The first problem is to clear
out the bits in 'word' where the 'field' will be inserted. The second
problem is to insert the 'field' into 'word' at the right index.

Hint: For the problem above, try to setup the following.

0111 0110 0101 0000 0000 0010 0001 0000

and

0000 0000 0000 1010 0001 0000 0000 0000

Once you get one concrete example working, test it on other examples
to see if you need to make adjustments to your algorithm.

my code thus far......
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
        unsigned mask = ~(~0 << n);

        ***************************************
        *  /* p = y & mask; */                *
        *  /* return x & (mask << (p+1-n)) */ *
        *       first attempt                 *
        ***************************************
return x & (mask << ((((p & 0) | mask) & y)+1-n));

}  second attempt and still trying

Im not looking for the answer as I'd really like to work this out for
myself but rather some pointers on where I'm going wrong here or where
my interpretation has gone wrong.

One issue with using '~0' is that the type is restricted to 'int'. If
'int' is 16 bits, and you want to set a field in a 32-bit long, it's
not going to come out right. What I do is define a constant that
defines the mask so that it's easy to change if I need to support bit
operations on larger integer types.

\code snippet
/*!
* \brief Define the integer type used to create a bitmask of all
* ones.
*
* One of the basic constructs used in the \c bits macro library is
* to create a mask that is all ones of a given width starting from
* the least significant bit. This is implemented using the
* expression <tt>~((~0) << width)</tt>. This is used to isolate a
* region of bits to be set or cleared within an integer. This
* concept is needed to implement the set of \c BIT_FIELD macros.
*
* The \c C_BITS_ALL_ONES define can be \c ~0U for \c int sized
* masks, <tt>~UINT32_C(0)</tt> to enable 32-bit support on 16-bit
* integer platforms, or <tt>~UINT64_C(0)</tt> to enable 64-bit
* support. This could be configured using a Makefile or config.h,
* but for now its definition is here.
*
* See \ref C_BITS_ONE for more information.
*/
#define C_BITS_ALL_ONES ( ~UINT32_C(0) )
\endcode

The motivation for 'setbits' is to be able to pack information at the
bit level from several different pieces of data. For example, in
avionics data, the ARINC 429 data standard packs 5 bits of information
into a single 32-bit word.

\comment snippet
/*
* The ARINC 429 standard is a point to point protocol consisting
* of a twisted pair that transmits 32-bit messages from avionics
* devices on an aircraft. The data bus consists of one source with
* many potential receivers. The following is a description of the
* meaning of the message fields.
*
* <ul>
* <li> \c label - This identifies the data type and the
* parameters associated with it for representing
* avionics data. A single avionics device may
* have up to 256 different messages.
* <li> \c sdi - This field is used for multiple receivers to
* identify which receiver is the recipient of
* the avionics data.
* <li> \c data - The avionics data, represented in a number of
* different formats. The common ones are binary
* coded decimal, 2's complement binary, and bit
* fields.
* <li> \c ssm - This field contains hardware equipment
* conditions, operational mode, or validity of
* data content.
* <li> \c parity - The most significant bit is the parity bit,
* typically used to ensure the ARINC 429 message
* has odd parity. Whether this bit is used
* depends on the avionic system design.
* </ul>
*
* Let's look at a real ARINC 429 standard message from an Air Data
* Computer (ADC). The labels are represented in octal form.
*
* Total Air Temperature
* <ul>
* <li> Bit: 1 - 8 Name: Label (211)
* <li> Bit: 9 - 10 Name: SDI
* <li> Bit: 11 - 17 Name: Spare
* <li> Bit: 18 - 29 Name: Total Air Temperature Value \n
* <ul>
* <li> Element Size: 12
* <li> Type: 2's Complement
* <li> Units: Degrees C
* <li> Scale: .25
* <li> State: [-60, 100]
* </ul>
* <li> Bit: 30 - 31 Name: SSM
* <li> Bit: 32 Name: Parity
* </ul>
*/
\endcomment

So, if you wanted to simulate an ARINC 429 data stream, you could take
an array of floating point temperatures in celsius, factor out the
scale factor to convert it to a 2's complement integer representation,
and use 'setbits' to place the 'Total Air Temperature' value's bits at
the right location in the ARINC 429 data word. You can use 'setbits'
to fill in the rest of the fields (Label, SSM, SDI) as needed.

Best regards,
John D.