C Newb Killer - Bitwise operators

[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.
Here is the homework.....

CODING RULES:
 
  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code 
  must conform to the following style:
 
  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;
 
      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }
 
  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>
 
  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.
 
  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
 
  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting an integer by more
     than the word size.
 
EXAMPLES OF ACCEPTABLE CODING STYLE:
  /*
   * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
   */
  int pow2plus1(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     return (1 << x) + 1;
  }
 
  /*
   * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
   */
  int pow2plus4(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     int result = (1 << x);
     result += 4;
     return result;
  }
 
#endif
 
/*
 * Modify the following functions according the coding rules.
 * 
 *   IMPORTANT. TO AVOID GRADING SURPRISES:
 *   1. Use the dlc compiler to check that your solutions conform
 *      to the coding rules.
 *   2. Use the btest test harness to check that your solutions produce 
 *      the correct answers. Watch out for corner cases around Tmin and Tmax.
 */
/* 
 * bitNor - ~(x|y) using only ~ and & 
 *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitNor(int x, int y) {
/* Complementing x and y(mirroring bits)
 * and then applying the and operator
 */
  return (~x & ~y );
}
 
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 2
 */
int bitXor(int x, int y) {
 
 
 
/* Using the slides on demorgans laws
 * I combined 2 equalies to recieve
 * this result
 * The complement of the complement
 * of the complement of x AND y 
 * and the complement x and the complement of
 * y
 */
 
  return ( ~ ( ~(~x&y) & ~ (x&~y)    ));
 
}
/* 
 * evenBits - return word with all even-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 2
 */
int evenBits(void) {
 
 
  return 2;
 
 
}
/* 
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int getByte(int x, int n) {
 
 
 return 2 ;
}
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  return 2;
}
/* 
 * bitMask - Generate a mask consisting of all 1's 
 *   lowbit and highbit
 *   Examples: bitMask(5,3) = 0x38
 *   Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
 *   If lowbit > highbit, then mask should be all 0's
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int bitMask(int highbit, int lowbit) {
  return 2;
}
/* 
 * TMax - return maximum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmax(void) {
 
  return ~(0x08<<28);
}
/* 
 * divpwr2 - Compute x/(2^n), for 0 <= n <= 30
 *  Round toward zero
 *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int divpwr2(int x, int n) {
    return 2;
}
/* 
 * isLess - if x < y  then return 1, else return 0 
 *   Example: isLess(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLess(int x, int y) {
       return 2;
}
/* 
 * isNonNegative - return 1 if x >= 0, return 0 otherwise 
 *   Example: isNonNegative(-1) = 0.  isNonNegative(0) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 3
 */
int isNonNegative(int x) {
 
  return 2;
}
/* 
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 1 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3 
 */
int logicalShift(int x, int n) {
  return 2;
}
/*
 * multFiveEights - multiplies by 5/8 rounding toward 0.
 *   Examples: multFiveEights(77) = 48
 *             multFiveEights(-22) = -13
 *   You can assume |x| < (1 << 29)
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 3
 */
int multFiveEights(int x) {
  return 2;
}
/* 
 * abs - absolute value of x (except returns TMin for TMin)
 *   Example: abs(-1) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int abs(int x) {
  return 2;
}
/* 
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int bang(int x) {
  return 2;
}
/* 
 * sm2tc - Convert from sign-magnitude to two's complement
 *   where the MSB is the sign bit
 *   Example: sm2tc(0x80000005) = -5.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 4
 */
int sm2tc(int x) {
  return 2;
}
 

[Banfa]

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.

[bjsmom]

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]

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