Some bit manipulation

[Henry Samuelson]

I am looking for some bit wizardy for the following:

We have two 32-bit integers A and B. I need to come up with an operation
O that takes A and B as arguments, spitting out a single integer R such
that if the bit in position b in A is set, then the bit in position b in R
is cleared; otherwise, the value of the bit in position b in B is copied to R.
This is to be done for all the 32 bits in the arguments.

 

[Eric Sosman]

I am looking for some bit wizardy for the following:

We have two 32-bit integers A and B. I need to come up with an operation
O that takes A and B as arguments, spitting out a single integer R such
that if the bit in position b in A is set, then the bit in position b in R
is cleared; otherwise, the value of the bit in position b in B is copied to R.
This is to be done for all the 32 bits in the arguments.

R = B & ~A;

As a rule, you should be using some flavor of `unsigned'
integers for bit-fiddling, because it avoids potentially
unpleasant surprises when sign bits participate.

 

[Fao, Sean]

I am looking for some bit wizardy for the following:

We have two 32-bit integers A and B. I need to come up with an operation
O that takes A and B as arguments, spitting out a single integer R such
that if the bit in position b in A is set, then the bit in position b in R
is cleared; otherwise, the value of the bit in position b in B is copied to R.
This is to be done for all the 32 bits in the arguments.

Question for you...Where does b (position) come from?

 

[Derrick Coetzee]

We have two 32-bit integers A and B. I need to come up with an operation
O that takes A and B as arguments, spitting out a single integer R such
that if the bit in position b in A is set, then the bit in position b in R
is cleared; otherwise, the value of the bit in position b in B is copied to R.

I'm going to assume in good faith this isn't a homework problem. To pull
off any particular logical function, it helps to look at the truth table:
B A=0 A=1
0 0 0
1 1 0

As you can see, the bit in R is set only if A's bit is clear AND B's bit
is set. In other words, if ~A's bit is set and B's bit is set, or:

R = ~A & B;

 

[Dan Pop]

I am looking for some bit wizardy for the following:

There is precious little wizardry involved in the solution.

We have two 32-bit integers A and B. I need to come up with an operation
O that takes A and B as arguments, spitting out a single integer R such
that if the bit in position b in A is set, then the bit in position b in R
is cleared; otherwise, the value of the bit in position b in B is copied to R.
This is to be done for all the 32 bits in the arguments.

Assuming A, B and R are unsigned integers:

R = 0xFFFFFFFF;
R ^= A; /* clear all bits that are set in A */
R &= B; /* copy the bits from B in the other bits of R */

If you still don't understand how it works, execute it with paper
and pencil for a single bit, giving A and B different values.

Dan

 

[Fao, Sean]

I'm going to assume in good faith this isn't a homework problem. To pull
off any particular logical function, it helps to look at the truth table:
B A=0 A=1
0 0 0
1 1 0

As you can see, the bit in R is set only if A's bit is clear AND B's bit
is set. In other words, if ~A's bit is set and B's bit is set, or:

R = ~A & B;

Unless I misunderstood the original logic, this doesn't work.

Suppose you supply the integers 5 and 2. Here is the result (working
with 4 bits to save space):

0101 - 5
1010 - ~5
0010 - ~5 & 2

Suppose I was interested in whether or not the bit in position 3 was set
in A. In my example, bit 3 was indeed set for parameter A. However,
the answer I have come up with clearly does not leave bit 3 turned on.

 

[Derrick Coetzee]

Suppose I was interested in whether or not the bit in position 3 was set
in A. In my example, bit 3 was indeed set for parameter A. However,
the answer I have come up with clearly does not leave bit 3 turned on.

I'm not sure how you interpreted the original poster, but they said:

"[ . . . ] if the bit in position b in A is set, then the bit in
position b in R is cleared [ . . . ]"

If bit 3 was set for A, it *must be* clear in R. Thus your answer is
correct. This does imply you can't retrieve the value of any bit of A
from the value of R, except for bits where B is 1 (in which case it is
the negation of R's bit).

 

[dbtid]

I am looking for some bit wizardy for the following:

We have two 32-bit integers A and B. I need to come up with an operation
O that takes A and B as arguments, spitting out a single integer R such
that if the bit in position b in A is set, then the bit in position b in R
is cleared; otherwise, the value of the bit in position b in B is copied to R.
This is to be done for all the 32 bits in the arguments.

Odd that no one came up with the standard "do your own damn homework!"
response...

 

[Derrick Coetzee]

Odd that no one came up with the standard "do your own damn homework!"
response...

I prefer to make them feel guilty by saying I trust them not to do that.
Unless I can find sure evidence on the web...

 

[Mabden]

Odd that no one came up with the standard "do your own damn homework!"
response...

There's a word, that I can't remember, that means or rather describes a word
or phrase, that by saying it, you do it. So when a judge says, "I sentence
you..." the speaking of that phrase causes it to happen. For instance, when
you are getting married and say, "I do." you are enacting or doing that
thing.

I forget what the word is, but your comment in your post did that!

 

[William L. Bahn]

In <[email protected]> Henry Samuelson

There is precious little wizardry involved in the solution.


Assuming A, B and R are unsigned integers:

R = 0xFFFFFFFF;
R ^= A; /* clear all bits that are set in A */
R &= B; /* copy the bits from B in the other bits of R */

If you still don't understand how it works, execute it with paper
and pencil for a single bit, giving A and B different values.

While this works, I would claim that your documentation is
misleading. Saying that you are clearing all bits that are set in
A implies that you are performing an opertion only on the bits
that are set and leaving the rest unchanged. Of course, a little
bit of pondering would result in the realization that this would
be another way of saying to set the value to zero and then one
would have to wonder you someone would use to such steps to
accomplish something like that. But then again, they might wonder
why the two steps that are used above are used instead of just
using the bitwise inversion operator:

R = ~A;
R &= B;

or simply

R = (~A) & B;

 

[William L. Bahn]

Unless I misunderstood the original logic, this doesn't work.

Suppose you supply the integers 5 and 2. Here is the result (working
with 4 bits to save space):

0101 - 5
1010 - ~5
0010 - ~5 & 2

Suppose I was interested in whether or not the bit in position 3 was set
in A. In my example, bit 3 was indeed set for parameter A. However,
the answer I have come up with clearly does not leave bit 3 turned on.

And why should it? That's not what was asked for.

By inverting 5, you are saying that A=5 and B=2. Look at the
result. For every bit that was set in A, isn't the corresponding
bit in the result cleared? For every bit that was not set in A,
isn't the bit in the result equal to the corresponding bit in B?

Also, I think the normal convention is to count bits starting
with bit zero so that the bit number matches the power to which
the bit is raised in a pure binary representation.

 

[William L. Bahn]

I am looking for some bit wizardy for the following:

We have two 32-bit integers A and B. I need to come up with an operation
O that takes A and B as arguments, spitting out a single integer R such
that if the bit in position b in A is set, then the bit in position b in R
is cleared; otherwise, the value of the bit in position b in B is copied to R.
This is to be done for all the 32 bits in the arguments.

This definitely smacks of a homework problem, but what the hell.

Stated another way, given a bit mask A and a bit pattern B, clear
all of the bits in B whose corresponding bits are set in A.

What logic function do you know that has the effect given two
logical values A and B that it will produce a False result based
solely on what is in A regardless of what is in B? The AND
function:

A B R
0 0 0
0 1 0
1 0 0
1 1 1

Notice that if A is zero, the Y is zero. If A is one, then Y is
whatever B is. Does that sound like what you are looking for?
It's pretty close, isn't it. The only difference is that you want
the behavior for the opposite values of A from what's given
above. Fine - use the opposite values - and you have an operator
to give you the opposite values. So:

R = (NOT(A)) AND (B)

I'll leave it up to you to cast this into a bitwise C expression.

 

[Dan Pop]

While this works, I would claim that your documentation is
misleading. Saying that you are clearing all bits that are set in
A implies that you are performing an opertion only on the bits
that are set and leaving the rest unchanged.

And isn't this exactly what I was doing?

Of course, a little
bit of pondering would result in the realization that this would
be another way of saying to set the value to zero and then one
would have to wonder you someone would use to such steps to
accomplish something like that. But then again, they might wonder
why the two steps that are used above are used instead of just
using the bitwise inversion operator:

R = ~A;
R &= B;

or simply

R = (~A) & B;

I was trying to be as explicit as possible (the OP was obviously a newbie
in the field) rather than as terse as possible. So, I've chosen a way
that implemented the OP's specifications in the very order they were
formulated and in a manner that was the easiest (IMHO) to follow.
Otherwise, I would have simply written:

R = ~A & B;

and let the OP not much more enlightened than he was before posting.

Dan

 

[Michael Wojcik]

There's a word, that I can't remember, that means or rather describes a word
or phrase, that by saying it, you do it.

It sounds to me like you're thinking of some term from speech act
theory, possibly "performative". See J. L. Austin, _How to Do Things
With Words_.

Several people have already posted solutions, of course, with various
explanations. Some, such as Dan, tried to provide solutions which
followed Henry's requirements in order, which I imagine was probably
quite useful. I'd like to suggest another way of explaining the "not-A
and B" version, though:

Note that if you read the requirements in the other order, the result
is the same as B, except that some of the bits are reset according to
what's in A. So the first step is easy: copy B into R:

R = B;

Now, you want to reset some of the bits in R, based on A. AND is the
usual operator to clear some bits and leave others unchanged. In
this case, though, you don't want to AND with A, because AND clears
the bits that are 0 in the second operand (or in the first one, but
we're treating the first as "source" and the second as "mask", for
the sake of clarity). You want the opposite - clear bits where A is
1.

So, what you want is an AND that clears where the mask is 1, or you
want a mask that has 1 where A is 0 and vice versa. The latter is
easier - it's just NOT A. So step 2 is to AND R with NOT A:

R = R & ~A;

And, of course, the two steps can be combined into one:

R = B & ~A;

There are lots of ways to arrive at Boolean functions: breaking down
the requirements into steps, writing out the truth table and figuring
out what operators it corresponds to, analysis methods like Karnaugh
maps, and so forth. Sometimes trying a couple of different approaches
will clarify the problem for you.

 

[Henry Samuelson]

I am looking for some bit wizardy for the following:

We have two 32-bit integers A and B. I need to come up with an operation
O that takes A and B as arguments, spitting out a single integer R such
that if the bit in position b in A is set, then the bit in position b in R
is cleared; otherwise, the value of the bit in position b in B is copied to R.
This is to be done for all the 32 bits in the arguments.

Thanks to everybody who replied, even those who couldn't resist dropping
comments about homework. I had come up with R = A & B ^ B, but I guess
that R = ~A & B is more economical.