Connecting Tech Pros Worldwide Forums | Help | Site Map
bytes > topic > c > answers

C Newb Killer - Bitwise operators

Newbie
  
Join Date: Feb 2006
Posts: 1
#1: Feb 21 '06
I am native to various languages but bitwise operators just kill me. I see how much I take object oriented languages for granted. I like all the other c derivitives but ANSI C is making me loose my hair....especially ANSI C's bitwise operators.....
For reference i come from the (Java/C#/C++) realm and was never forced to use these.

Many people dont understand these....I tried to make sense....I know the truth tables...and I can do simple operation....can anyone provide a couple answers and possibly give me some explainations on how to attack these...any special tricks on attacking these....I am familiar with these operators but these are tricky and none of my friends got these....I am the most advanced since I at least got 3 correctly..........
:confused: :( :mad: :eek:
Any help is much appreciated.
Here is the homework.....

Expand|Select|Wrap|Line Numbers
  1. CODING RULES:
  2.  
  3.   Replace the "return" statement in each function with one
  4.   or more lines of C code that implements the function. Your code 
  5.   must conform to the following style:
  6.  
  7.   int Funct(arg1, arg2, ...) {
  8.       /* brief description of how your implementation works */
  9.       int var1 = Expr1;
  10.       ...
  11.       int varM = ExprM;
  12.  
  13.       varJ = ExprJ;
  14.       ...
  15.       varN = ExprN;
  16.       return ExprR;
  17.   }
  18.  
  19.   Each "Expr" is an expression using ONLY the following:
  20.   1. Integer constants 0 through 255 (0xFF), inclusive. You are
  21.       not allowed to use big constants such as 0xffffffff.
  22.   2. Function arguments and local variables (no global variables).
  23.   3. Unary integer operations ! ~
  24.   4. Binary integer operations & ^ | + << >>
  25.  
  26.   Some of the problems restrict the set of allowed operators even further.
  27.   Each "Expr" may consist of multiple operators. You are not restricted to
  28.   one operator per line.
  29.  
  30.   You are expressly forbidden to:
  31.   1. Use any control constructs such as if, do, while, for, switch, etc.
  32.   2. Define or use any macros.
  33.   3. Define any additional functions in this file.
  34.   4. Call any functions.
  35.   5. Use any other operations, such as &&, ||, -, or ?:
  36.   6. Use any form of casting.
  37.  
  38.   You may assume that your machine:
  39.   1. Uses 2s complement, 32-bit representations of integers.
  40.   2. Performs right shifts arithmetically.
  41.   3. Has unpredictable behavior when shifting an integer by more
  42.      than the word size.
  43.  
  44. EXAMPLES OF ACCEPTABLE CODING STYLE:
  45.   /*
  46.    * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
  47.    */
  48.   int pow2plus1(int x) {
  49.      /* exploit ability of shifts to compute powers of 2 */
  50.      return (1 << x) + 1;
  51.   }
  52.  
  53.   /*
  54.    * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
  55.    */
  56.   int pow2plus4(int x) {
  57.      /* exploit ability of shifts to compute powers of 2 */
  58.      int result = (1 << x);
  59.      result += 4;
  60.      return result;
  61.   }
  62.  
  63. #endif
  64.  
  65. /*
  66.  * Modify the following functions according the coding rules.
  67.  * 
  68.  *   IMPORTANT. TO AVOID GRADING SURPRISES:
  69.  *   1. Use the dlc compiler to check that your solutions conform
  70.  *      to the coding rules.
  71.  *   2. Use the btest test harness to check that your solutions produce 
  72.  *      the correct answers. Watch out for corner cases around Tmin and Tmax.
  73.  */
  74. /* 
  75.  * bitNor - ~(x|y) using only ~ and & 
  76.  *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
  77.  *   Legal ops: ~ &
  78.  *   Max ops: 8
  79.  *   Rating: 1
  80.  */
  81. int bitNor(int x, int y) {
  82. /* Complementing x and y(mirroring bits)
  83.  * and then applying the and operator
  84.  */
  85.   return (~x & ~y );
  86. }
  87.  
  88. /* 
  89.  * bitXor - x^y using only ~ and & 
  90.  *   Example: bitXor(4, 5) = 1
  91.  *   Legal ops: ~ &
  92.  *   Max ops: 14
  93.  *   Rating: 2
  94.  */
  95. int bitXor(int x, int y) {
  96.  
  97.  
  98.  
  99. /* Using the slides on demorgans laws
  100.  * I combined 2 equalies to recieve
  101.  * this result
  102.  * The complement of the complement
  103.  * of the complement of x AND y 
  104.  * and the complement x and the complement of
  105.  * y
  106.  */
  107.  
  108.   return ( ~ ( ~(~x&y) & ~ (x&~y)    ));
  109.  
  110. }
  111. /* 
  112.  * evenBits - return word with all even-numbered bits set to 1
  113.  *   Legal ops: ! ~ & ^ | + << >>
  114.  *   Max ops: 8
  115.  *   Rating: 2
  116.  */
  117. int evenBits(void) {
  118.  
  119.  
  120.   return 2;
  121.  
  122.  
  123. }
  124. /* 
  125.  * getByte - Extract byte n from word x
  126.  *   Bytes numbered from 0 (LSB) to 3 (MSB)
  127.  *   Examples: getByte(0x12345678,1) = 0x56
  128.  *   Legal ops: ! ~ & ^ | + << >>
  129.  *   Max ops: 6
  130.  *   Rating: 2
  131.  */
  132. int getByte(int x, int n) {
  133.  
  134.  
  135.  return 2 ;
  136. }
  137. /* 
  138.  * conditional - same as x ? y : z 
  139.  *   Example: conditional(2,4,5) = 4
  140.  *   Legal ops: ! ~ & ^ | + << >>
  141.  *   Max ops: 16
  142.  *   Rating: 3
  143.  */
  144. int conditional(int x, int y, int z) {
  145.   return 2;
  146. }
  147. /* 
  148.  * bitMask - Generate a mask consisting of all 1's 
  149.  *   lowbit and highbit
  150.  *   Examples: bitMask(5,3) = 0x38
  151.  *   Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
  152.  *   If lowbit > highbit, then mask should be all 0's
  153.  *   Legal ops: ! ~ & ^ | + << >>
  154.  *   Max ops: 16
  155.  *   Rating: 3
  156.  */
  157. int bitMask(int highbit, int lowbit) {
  158.   return 2;
  159. }
  160. /* 
  161.  * TMax - return maximum two's complement integer 
  162.  *   Legal ops: ! ~ & ^ | + << >>
  163.  *   Max ops: 4
  164.  *   Rating: 1
  165.  */
  166. int tmax(void) {
  167.  
  168.   return ~(0x08<<28);
  169. }
  170. /* 
  171.  * divpwr2 - Compute x/(2^n), for 0 <= n <= 30
  172.  *  Round toward zero
  173.  *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
  174.  *   Legal ops: ! ~ & ^ | + << >>
  175.  *   Max ops: 15
  176.  *   Rating: 2
  177.  */
  178. int divpwr2(int x, int n) {
  179.     return 2;
  180. }
  181. /* 
  182.  * isLess - if x < y  then return 1, else return 0 
  183.  *   Example: isLess(4,5) = 1.
  184.  *   Legal ops: ! ~ & ^ | + << >>
  185.  *   Max ops: 24
  186.  *   Rating: 3
  187.  */
  188. int isLess(int x, int y) {
  189.        return 2;
  190. }
  191. /* 
  192.  * isNonNegative - return 1 if x >= 0, return 0 otherwise 
  193.  *   Example: isNonNegative(-1) = 0.  isNonNegative(0) = 1.
  194.  *   Legal ops: ! ~ & ^ | + << >>
  195.  *   Max ops: 6
  196.  *   Rating: 3
  197.  */
  198. int isNonNegative(int x) {
  199.  
  200.   return 2;
  201. }
  202. /* 
  203.  * logicalShift - shift x to the right by n, using a logical shift
  204.  *   Can assume that 1 <= n <= 31
  205.  *   Examples: logicalShift(0x87654321,4) = 0x08765432
  206.  *   Legal ops: ~ & ^ | + << >>
  207.  *   Max ops: 16
  208.  *   Rating: 3 
  209.  */
  210. int logicalShift(int x, int n) {
  211.   return 2;
  212. }
  213. /*
  214.  * multFiveEights - multiplies by 5/8 rounding toward 0.
  215.  *   Examples: multFiveEights(77) = 48
  216.  *             multFiveEights(-22) = -13
  217.  *   You can assume |x| < (1 << 29)
  218.  *   Legal ops: ! ~ & ^ | + << >>
  219.  *   Max ops: 12
  220.  *   Rating: 3
  221.  */
  222. int multFiveEights(int x) {
  223.   return 2;
  224. }
  225. /* 
  226.  * abs - absolute value of x (except returns TMin for TMin)
  227.  *   Example: abs(-1) = 1.
  228.  *   Legal ops: ! ~ & ^ | + << >>
  229.  *   Max ops: 10
  230.  *   Rating: 4
  231.  */
  232. int abs(int x) {
  233.   return 2;
  234. }
  235. /* 
  236.  * bang - Compute !x without using !
  237.  *   Examples: bang(3) = 0, bang(0) = 1
  238.  *   Legal ops: ~ & ^ | + << >>
  239.  *   Max ops: 12
  240.  *   Rating: 4 
  241.  */
  242. int bang(int x) {
  243.   return 2;
  244. }
  245. /* 
  246.  * sm2tc - Convert from sign-magnitude to two's complement
  247.  *   where the MSB is the sign bit
  248.  *   Example: sm2tc(0x80000005) = -5.
  249.  *   Legal ops: ! ~ & ^ | + << >>
  250.  *   Max ops: 15
  251.  *   Rating: 4
  252.  */
  253. int sm2tc(int x) {
  254.   return 2;
  255. }
  256.  

Banfa's Avatar
AdministratorVoR
  
Join Date: Feb 2006
Location: South West UK
Posts: 6,177
#2: Feb 23 '06

re: C Newb Killer - Bitwise operators

I am unwilling to do your homework for you, partly because if I do it you wont learn but mainly because I did more than enough when I was at school and don't feel the need to do any more.

However I am happy to try and help you understand the bitwise operators better but you haven't really said what it is about them that you don't understand.

The bitwise operators operate directly on the bits of an integer rather than considering the value of the whole thing, that is if a bitwise operator considers the value of each individual bit of the integer without reference to the other bits in the integer, so when looking at the value of bit 4, for instance, bits 0 - 3 and 5 - 31 are ignored and play no part in the operation.

You say you understand the logic tables, then you are virtually there as far as understanding the bitwise operators, consider this code statement

int r, a, b;

... /* code seting value of a and b */

r = a | b;

For this statement the computer with combine bit 0 and a and bit 0 of b using the OR truth table and put the result in bit 0 of r. It will then repeat this for the other 31 bits (1 - 31). In reality of course most CPU cores have an instruction that does this simulateously for all bits.

Get back with some specific questions.


P.S. You homework states that + is a bitwise operator, strictly speaking I would say that this is not true, + does not act on the bits of an integer independently.
Newbie
  
Join Date: Apr 2007
Posts: 1
#3: Apr 24 '07

re: C Newb Killer - Bitwise operators

Hello,
Were you able to get help on this? I have the same homework assignment and I'm having difficulty completing this, can you help?
AdrianH's Avatar
Expert
  
Join Date: Feb 2007
Location: Halifax
Posts: 1,099
#4: Apr 24 '07

re: C Newb Killer - Bitwise operators

Quote:

Originally Posted by shdwsclan

I am native to various languages but bitwise operators just kill me. I see how much I take object oriented languages for granted. I like all the other c derivitives but ANSI C is making me loose my hair....especially ANSI C's bitwise operators.....
For reference i come from the (Java/C#/C++) realm and was never forced to use these.

Many people dont understand these....I tried to make sense....I know the truth tables...and I can do simple operation....can anyone provide a couple answers and possibly give me some explainations on how to attack these...any special tricks on attacking these....I am familiar with these operators but these are tricky and none of my friends got these....I am the most advanced since I at least got 3 correctly..........
:confused: :( :mad: :eek:
Any help is much appreciated.

Just to let you know, these bitwise operators are available in all the languages you described. Perhaps you should reorient your thinking. Think about the integer number as the object and the operators as functions that you invoke on the object.

You really don’t explain what it is that you are having trouble on. Banfa’s explanation is fairly clear. But in case you are still having difficulty with it, most of the bitwise operators operate as if you have a series of Booleans and you are using the same Boolean (a.k.a. logical) operator on all of them in parallel.

So the bitwise or is equivalent to a logical or, the bitwise and is equivalent to the logical and, the bitwise not is equivalent to the logical not when relating the bits in the same place of each number to the other. There is no logical equivalent to the bitwise xor, you would have to do something like this: (a != 0)^(b != 0) which may be slightly more efficient than (a && !b)||(!a && b) in certain circumstances and less so in others due to the short-circuiting nature of the logical and and or operators.

The left shift and right shift operators shift the bits as you would read them as binary. The number 1 shifted left one would give you 2 as the binary of 1 is 00000001 and the binary of 2 is 00000010. As you will notice, the least significant bit is filled in with a zero (0).

Shifting right is a little trickier as it does something different if you are shifting a signed or unsigned value. If the number you are shifting is signed, then sign extension takes place, so it is filled in with whatever was there to start with. This means that if the most significant bit is 1 then that 1 stays 1 after the shift, if it is 0 then it stays 0. So a signed byte of 10000000 shift right would be 11000000. An unsigned value however would fill the most significant bit with 0 no matter what it was to start with. So an unsigned byte of 10000000 shifted right 1 would result in 01000000. Any bits that fall off the end will be lost forever. There is no access to the overflow like there is in assembly.

In Java, to reduce problems, they added a >>> operator which means that it is to treat the number being shifted always as an unsigned number, and I think if you were to use the >> it would treat the number being shifted always as a signed number.

As for + being a bitwise operator, well, that is somewhat on the fence. Like the right shift operator, it has some dependencies related to the state of the operands, though it is slightly more complicated and relates to all but the least significant bit. I can see both sides of the issue, so I have no real qualms about it being considered a bitwise operator.

If you are still having trouble, feel free to post back any additional specific questions that you may have.


Adrian
Reply

« previous question | next question »

Similar C / C++ bytes

/bytes/development

/bytes/it

Forums
Visit our community forums for general discussions and latest on Bytes

Our staff and community areas have moved to bytes.com/forums/

/bytes/about

We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights. Get the best answers to your questions from over 226,449 network members.

dev questions:
algorithms | asp | asp.net | c/c++ | coldfusion | c# | flash | html/css | java | javascript |
mobile dev | .net | perl | php | python | ruby | software dev | vb.net | visual basic | xml
it questions:
access | apache | careers | db2 | iis | macosx | mysql | networking | oracle | postgresql | sql server | unix | windows

About Bytes | Copyright 1995-2009 BYTES. All rights Reserved