Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
November 3rd, 2003, 03:30 PM
 gtpc
Contributing User

Join Date: Oct 2003
Posts: 228
Time spent in forums: < 1 sec
Reputation Power: 11
manipulating data at the bitwise level in C

HELP! I am writing a function that is supposed
to take 3 short ints filled at the bit level with 16
yes/no answers, theoretically from 3 different
people. Then finding the majority (best 2 of 3) for
each bit compared. This is new territory for me
so I am feeling a little lost...
Here is where I am so far...

PHP Code:
short majority(short ashort bshort c)
{

int i;

short m=0;
for (
1<= 16; ++i) {  /* to proc one bit at a time */

if (((a&i) == && (b&i) == 1) || ((a&i) == && (c&i) == 1))   /* checking for majority */

<<= 1;
else

<<= 0;
}
return
m;    /* return a short with all majorities */

#2
November 3rd, 2003, 05:02 PM
 dwise1_aol
Contributing User

Join Date: Jan 2003
Location: USA
Posts: 6,855
Time spent in forums: 3 Months 1 Day 4 h 11 m 54 sec
Reputation Power: 2199
OK, first, are you familiar with binary numbers and with the bitwise logical operations (AND, OR, NOT) and with the shift operator?

As it is currently written, as your for-loop iterates through, these will be the values of i in binary (preceded by the decimal equivalent and followed by what I think you want):
1 -- 0000 0000 0000 0001 -- 0000 0000 0000 0001
2 -- 0000 0000 0000 0010 -- 0000 0000 0000 0010
3 -- 0000 0000 0000 0011 -- 0000 0000 0000 0100
4 -- 0000 0000 0000 0100 -- 0000 0000 0000 1000
5 -- 0000 0000 0000 0101 -- 0000 0000 0001 0000
6 -- 0000 0000 0000 0110 -- 0000 0000 0010 0000
7 -- 0000 0000 0000 0111 -- 0000 0000 0100 0000
8 -- 0000 0000 0000 1001 -- 0000 0000 1000 0000
9 -- 0000 0000 0000 1001 -- 0000 0001 0000 0000
10 -- 0000 0000 0000 1010 -- 0000 0010 0000 0000
11 -- 0000 0000 0000 1011 -- 0000 0100 0000 0000
12 -- 0000 0000 0000 1100 -- 0000 1000 0000 0000
13 -- 0000 0000 0000 1101 -- 0001 0000 0000 0000
14 -- 0000 0000 0000 1110 -- 0010 0000 0000 0000
15 -- 0000 0000 0000 1111 -- 0100 0000 0000 0000
16 -- 0000 0000 0001 0000 -- 1000 0000 0000 0000

What you want is on the far right (though by your problem definition you might be required to go from left to right; I don't know that). What you are trying to use is in the middle. So use i only as a counter and not as an operand in the bitwise AND.

Instead, use a mask. Declare a short int and initialize it to one (see the far right value for i == 1). Then at the end of every iteration of the loop, shift it to the left by one (mask << 1).

Next, what is the result of an AND? You are assuming that it is 1; that is not true. Bitwise ANDing means that you take each bit of the two operands and AND the corresponding bits together. That means that you AND bit0 of both shorts together and the result goes into bit0 of the resultant short, and then bit1, and bit2, etc.
If we AND 1010 with 1000, then we get 1000, which is 8, not 1.

The way to test whether a particular bit in a short is set is to AND it with a mask short that has that bit and only that bit set. If that bit was set, then the result is non-zero and it is also the value of the mask short. If that bit was not set, then the result is zero. So it would be valid to simply test the AND for being either zero or non-zero.

For GPs, lets see how the test for bit5 (the sixth bit) would go. With your code as it currently is:
0000 0000 0010 0000 AND 0000 0000 0000 0110 = 0
Your current code would AND it with a 6, which is 0110 and whose bit5 is not set. Therefore, you would not detect the bit you want to test for because you aren't even testing that bit.

Using a mask short that you've shifted five times (this being the sixth test):
0000 0000 0010 0000 AND 0000 0000 0010 0000 = 0000 0000 0010 0000, which is non-zero
In this case, we are testing that bit, and so we do detect it.

Hope that helps.

Last edited by dwise1_aol : November 3rd, 2003 at 05:05 PM.

#3
November 3rd, 2003, 05:11 PM
 gtpc
Contributing User

Join Date: Oct 2003
Posts: 228
Time spent in forums: < 1 sec
Reputation Power: 11
WOW! This is lots to digest. Thanks for your reply. I am going to print it out and read it over a few times. I have studied the and/or/not operators, and using 'mask'. I will work with this a little and see what I come up with.

#4
November 3rd, 2003, 06:57 PM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,965
Time spent in forums: 1 Month 4 Days 3 h 25 m 52 sec
Reputation Power: 1801
What follows is a generally applicable method for solving such problems:

Consider the truth table for a single bit in each of a, b, and c, the corresponding bit in m is 1 is more than one of A B or C are 1.

Code:
A B C   M
0 0 0   0
0 0 1   0
0 1 0   0
0 1 1   1
1 0 0   0
1 0 1   1
1 1 0   1
1 1 1   1

Now for each of M=1, write the boolean expression that of the input bits to get the result 1:

Code:
A B C   M
0 0 0   0
0 0 1   0
0 1 0   0
0 1 1   1    B & C & ~A
1 0 0   0
1 0 1   1    A & C & ~B
1 1 0   1    A & B & ~C
1 1 1   1    A & B & C

If any one of these expressions is true, M is true, so they can be combined by OR:

Code:
(B & C & ~A) | (A & C & ~B) | ( A & B & ~C) | (A & B & C)

This can be simplified:

Code:
(B & C) | (A & C) | ( A & B)

There are mathematical methods of simplifying such expressions - DeMorgan's theorem, Karnaugh maps etc., but this simple case can be reasoned intuitively. Do a web search if you are interested (try "boolean algebra" ).

Now to translate that to C code, we can perform this operation on all bits simultaneously as follows:
Code:
m = (b & c) | (a & c) | (a & b) ;

i.e. One line of code!

QED

Clifford.

Last edited by clifford : November 3rd, 2003 at 08:27 PM.

#5
November 3rd, 2003, 08:04 PM
 dwise1_aol
Contributing User

Join Date: Jan 2003
Location: USA
Posts: 6,855
Time spent in forums: 3 Months 1 Day 4 h 11 m 54 sec
Reputation Power: 2199
One caveat that gtpc should note is that the bit-wise binary operators are different from the relational operators.

What I gave him applies to the testing of the bit flag with the short int.

What Clifford gave him would be very applicable to the relational operations to which the results of the bit-wise testing would be input.

BTW, long ago in a telecommunications class we were given a programming assignment to generate and use a Huffman encoding tree. I was having trouble with some very gnarly compound conditionals to figure out, so I listed them all, plugged them into a Karnaugh map, and simplified them down to a (relatively) concise if statement that worked first time. Hurrah!

But I never got a chance to show it off, because the instructor decided that part of the program was too difficult to code and rescinded it; seems I was the only one who had even tried to do it.

#6
November 3rd, 2003, 08:22 PM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,965
Time spent in forums: 1 Month 4 Days 3 h 25 m 52 sec
Reputation Power: 1801
Quote:
 Originally posted by dwise1_aol What I gave him applies to the testing of the bit flag with the short int. What Clifford gave him would be very applicable to the relational operations to which the results of the bit-wise testing would be input.

I am not sure what you mean. What I wrote implements exactly the function that the OP gave in the question, a, b, and c containing appropriate data are a pre-requisite. The result is a bit set in m where the majority of corresponding bits were set in a, b, and c.

To be explicit (at the risk of doing someones homework!):
PHP Code:
short majority(short ashort bshort c)
{
return( (
c) | (c) | (b)  ) ;    /* return a short with all majorities */

However, my method (and the final answer) were incorrect. I have since edited it to correct it.

Clifford

Last edited by clifford : November 3rd, 2003 at 08:27 PM.

#7
November 4th, 2003, 04:40 PM
 gtpc
Contributing User

Join Date: Oct 2003
Posts: 228
Time spent in forums: < 1 sec
Reputation Power: 11
You guys are truly sage! Thanks a load. I added the simple code, and with my main() and another small file I wrote called bit_print_short.c, whose function bitprint() is to print a short int in bit-form, it worked the first time!!! THANKS.

 Viewing: Dev Shed Forums > Programming Languages > C Programming > manipulating data at the bitwise level in C