C Programming
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed Forums > Programming Languages > C Programming
Reload this Page

manipulating data at the bitwise level in C


Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
« Previous Thread | Next Thread »  
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old November 3rd, 2003, 02:30 PM
gtpc gtpc is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
  
Join Date: Oct 2003
Location: Canada
Posts: 228 gtpc User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 10
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 a, short b, short c)
{
   int i;
   short m=0;
   for (i = 1; i <= 16; ++i) {  /* to proc one bit at a time */
      if (((a&i) == 1 && (b&i) == 1) || ((a&i) == 1 && (c&i) == 1))   /* checking for majority */
         m <<= 1;
      else
         m <<= 0;
      }
   return m;    /* return a short with all majorities */
} 
Reply With Quote
  #2  
Old November 3rd, 2003, 04:02 PM
dwise1_aol's Avatar
dwise1_aol dwise1_aol is offline
Contributing User
Dev Shed God 2nd Plane (6000 - 6499 posts)
  
Join Date: Jan 2003
Location: USA
Posts: 6,252 dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level) 
Time spent in forums: 2 Months 2 Weeks 5 Days 19 h 13 m 3 sec
Reputation Power: 1985
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 04:05 PM.
Reply With Quote
  #3  
Old November 3rd, 2003, 04:11 PM
gtpc gtpc is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
  
Join Date: Oct 2003
Location: Canada
Posts: 228 gtpc User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 10
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.
Reply With Quote
  #4  
Old November 3rd, 2003, 05:57 PM
clifford's Avatar
clifford clifford is offline
Contributing User
Dev Shed Demi-God (4500 - 4999 posts)
  
Join Date: Aug 2003
Location: UK
Posts: 4,824 clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level) 
Time spent in forums: 1 Month 2 Days 21 h 1 m
Reputation Power: 1800
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 07:27 PM.
Reply With Quote
  #5  
Old November 3rd, 2003, 07:04 PM
dwise1_aol's Avatar
dwise1_aol dwise1_aol is offline
Contributing User
Dev Shed God 2nd Plane (6000 - 6499 posts)
  
Join Date: Jan 2003
Location: USA
Posts: 6,252 dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level)dwise1_aol User rank is General 15th Grade (Above 100000 Reputation Level) 
Time spent in forums: 2 Months 2 Weeks 5 Days 19 h 13 m 3 sec
Reputation Power: 1985
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.
Reply With Quote
  #6  
Old November 3rd, 2003, 07:22 PM
clifford's Avatar
clifford clifford is offline
Contributing User
Dev Shed Demi-God (4500 - 4999 posts)
  
Join Date: Aug 2003
Location: UK
Posts: 4,824 clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level)clifford User rank is General 12nd Grade (Above 100000 Reputation Level) 
Time spent in forums: 1 Month 2 Days 21 h 1 m
Reputation Power: 1800
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 a, short b, short c)
{
   return( (b & c) | (a & c) | (a & 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 07:27 PM.
Reply With Quote
  #7  
Old November 4th, 2003, 03:40 PM
gtpc gtpc is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
  
Join Date: Oct 2003
Location: Canada
Posts: 228 gtpc User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: < 1 sec
Reputation Power: 10
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.
Reply With Quote
Reply

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

« Previous Thread | Next Thread »

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Linear Mode Linear Mode
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

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


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap