CODEWITHSUNDEEP
cbit-manipulationbitwise-operators
Benjamin Rodriguez
Benjamin Rodriguez

Reputation: 156

C function that uses bitwise operations to see if an int x fits in n bits

/* 
 * fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */

int fitsBits(int x, int n) {
  /* mask the sign bit against ~x and vice versa to get highest bit in x. Shift by n-1, and not. */
  int mask = x >> 31;

  return !(((~x & mask) + (x & ~mask)) >> (n + ~0));

}

I have this function and I don't understand why we are masking ~x with that mask. It is my understanding that x >> 31 will bring the last bit (sign bit) to the most right place. Why do we need the sign bit in that position. Why do we have to add the result of the second mask and why are we right shifting n - 1 spaces? I'm lost and I don't know where to start to understand this function. Please help me get started.

Upvotes: 1

Views: 2694

Answers (2)

nmd_07
nmd_07

Reputation: 706

UPDATE:

Left shift operation is the same for both arithmetic and logical shift operations because sign-ness of a value is not represented at the least significant bit but rather in the most significant bit. Where it gets complicated is bit shifting operation towards right.

One problem with this function is that it assumes right shift operation to be an arithmetic shift in which sign-ness of a value is protected. Arithmetic shift takes places by filling the slot of the most significant bit with a value that is the same as previous value that had been there. This means if you shift a binary number representing a negative value(negative signed int) to the right, by the rules of negative int representation, right shift operation will be mathematically consistent such that resulting value will be negative and be divided by two. There is also something called logical shift in which the most significant bit from where the previous value is shifted to right will always be zero which is the same as what happens in left-shift. In such case right shifting operation will not be consistent with integer representation.

Above function assumes shift operation will always be a type of arithmetic shift operation. However, if you check out the following source

Are the shift operators (<<, >>) arithmetic or logical in C?

it says right shift operation is implementation-defined meaning that there is no guarantee right shift operation will ever be a logical or arithmetic shift. It also states right shift is "most of the time" implemented as an arithmetic shift but does not have to be that way.

For example, Java has two left shift operators >>> and >>. The former enforces logical shift and the latter enforces arithmetic shift.

int mask = x >> 31;

Main idea behind shifting right by 31 is to be able to differentiate a negative and a positive integer. By sign extension rule, if a negative number is shifted to the right by any magnitude, value of the most significant bit is repeated throughout the right shift to maintain number's sign.

return !(((~x & mask) + (x & ~mask)) >> (n + ~0));

This is the place where it gets little bit complicated, let's divide it,

//Either x or y has to be zero since mask either will be all zeroes or ones
a = (~x & mask)
b = (x & ~mask) 

//When added together, since x or y will always be zero, number to be used is returned
//Hence addition is used to simulate logical OR operation.
c = (a OR b) >> (n - 1)

//Any remaining non-zero bit means N wasn't sufficient 
result = !c

As seen above entire return statement can be separated into logical steps shown above. Now let's evaluate what they may mean by rewriting the code in a straight-forward manner,

int fitsBits(int x, int n) {
   int res = -1;
   if(x >= 0){
       res = (x >> (n - 1));
   }
   else if (x < 0){
       res = (~x >> (n - 1));
   }
   return !res;
}

Shifting by n-1 is used for positive numbers. Since the most significant digit of a number is only used to detect a number's sign, it would give a false result to shift a positive number by n in a situation the most significant digit is not used. Basically we need a dummy bit to show whether a number is positive or negative, by shifting n -1, we are making sure we have enough place for that one bit. An example follows below 

4 is 00100. Can be represented using n=3 bits? Let's look at it.
Shift by 3, result is !00000 = 1, this true for unsigned int but not for signed int
Shift by 2, result is !00001 = 0, more correct representation.

HOW DOES IT WORK FOR NEGATIVE NUMBERS?

2's complement rule is used to represent both negative and positive integers using binary numbering system. It is a way of transforming numbering system from one the another. There is also another system called 1's complement where the difference between negativeness and positiveness is determined by inverting all the bits. But in such case there is a condition called negative zero and positive zero. To avoid such condition, 2's complement is being used where 1 is added after flipping all the bits.

In the case of fitsBits function it is simply enough to invert all the bits if a number is negative, that's because it will give the value -(x) - 1 where x is negative. Let's say if you have -3, ~ operation will give you -(-3) - 1 = 2.

By the rule of two's complement, -3 has to be 2 when inverted using the formula -(x) - 1. If ~ operation does not satisfy -(x) - 1 using the given number of bits, that means number of bit slots are not sufficient.

Upvotes: 3

rtpax
rtpax

Reputation: 1777

int fitsBits(int x, int n) {
  int mask = x >> 31;

  return !(((~x & mask) + (x & ~mask)) >> (n + ~0));

}

mask is the sign bit as you said.

if mask is 0x01
    (~x & mask) last bit of x, but flipped `0 <-> 1`
    (x & ~mask) everything except the last bit
if mask is 0x00
    (~x & mask) is always 0x00
    (x & ~mask) is always x

so we have

if positive (~x & mask) + (x & ~mask) evaluates to just x
if negative (~x & mask) + (x & ~mask) evaluates to x with the last (least) bit switched

(n + ~0) is equivalent to (n-1), at least for n >= 0

and of course the ! at the end makes a nonzero value 0 and a zero value become 1

The reason for switching the last bit for negative numbers is because in two's compliment of a negative number are allowed to be larger than those of a positive number

Upvotes: 0

Related Questions