Search code examples
cbit-manipulation

Using only bit manipulations, return a mask that marks the position of the most significant 1 bit. If x == 0, return 0

As part of my coding class, an intro to C, I'm working on a coding project dealing with bit manipulation under restrictions. On this question in particular, I'm stuck because I don't know how to fix my error.

/* 
 * SigBitMask - return a mask that marks the position of the
 *           most significant 1 bit. If x == 0, return 0
 *   Example: SigBitMask(96) = 0x40
 *   Legal operations: ! ~ & ^ | + << >>
 *   Max operations: 16
 *   Rating: 4 
 */

Besides the legal operations listed, I can't use any statements such as do, if, while, or else. I'm not allowed cast to other data types either., this includes using unsigned. Also I can't use any constant bigger than 0xFF, which is super important for this problem since I'm not allowed to use 0x80000000. Also, assume we are using a 32 bit machine.

A big thing here is that I can't use operations like - or * which would make this a lot easier.

Here is my code so far:

int SigBitMask(int x) {
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  x = x ^ (x >> 1);
  return x & ~(x >> 1);
}

The error the checking software is giving me says:

    "ERROR: Test SigBitMask(-2147483648[0x80000000]) failed...
    ...Gives 0[0x0]. Should be -2147483648[0x80000000]

I'm not quiet sure how to go about fixing my problem. I'd prefer more than just the answer. Can someone actually explain the process too. The whole point of this project is to learn to code in C. Thanks :)

Edit: I know there is a similar problem on Stack Overflow already, but their restrictions were different than mine, plus I'm looking for help fixing my code, and understanding why.

Edit2: Clarified what max and legal ops meant

Solution

  • Get rid of your last line because it doesn't do anything. So your function becomes:

    int SigBitMask(int x) {
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  return x ^ (x >> 1);
}

    This works great for non-negative inputs, but for negative inputs, x will be -1 when the last line runs, so the last line will give a result of zero. But that's bad, because we want to return -2147483648 (i.e. 0x80000000) for all negative inputs.

    What if we could patch the return expression, by using | to combine it with another expression that is 0x80000000 when x is -1, and 0 when is x is non-negative? (We don't care about its values for other negative values of x.) Can you think of such an expression? I can think of one using only 3 operators, but it involves a little bit of undefined behavior.