negation using bitwise operators, C

Question

Suppose you have 2 numbers:

int x = 1;
int y = 2;

Without worrying about specific difference between them, i'd like to know whether x is larger then y using only bitwise operators.

I can check to see if number is positive or negative by using !(x >> 31), but before i get there, i need to implement negation using bitwise operators.

How can i check whether difference between 2 numbers is positive or negative?

Answer 1

You need to read about two's complement arithmetic. Addition, subtraction, negation, sign testing, and everything else are all done by the hardware using bitwise operations, so you can definitely do it in your C program. The wikipedia link above should teach you everything you need to know to solve your problem.

Answer 2

Your first step will be to implement addition using only bitwise operators. After that, everything should be easy. Start small- what do you have to do to implement 00 + 00, 01 + 01, etc? Go from there.

Answer 3

When comparing the bits of two numbers A and B there are three posibilities. The following assumes unsigned numbers.

1. A == B : All of the bits are the same
2. A > B: The most significant bit that differs between the two numbers is set in A and not in B
3. A < B: The most significant bit that differs between the two numbers is set in B and not in A

Code might look like the following

int getDifType(uint32_t A, uint32_t B)
{
  uint32_t bitMask = 0x8000000;
  // From MSB to LSB
  for (bitMask = 0x80000000; 0 != bitMask; bitMask >>= 1)
  {
    if (A & bitMask != B & bitMask)
      return (A & bitMask) - (B & bitMask);
  }
  // No difference found
  return 0;
}

Answer 4

You need to start checking from the most significant end to find if a number is greater or not. This logic will work only for non-negative integers.

int x,y;
//get x & y
unsigned int mask=1;           // make the mask 000..0001
mask=mask<<(8*sizeoF(int)-1);    // make the mask 1000..000

while(mask!=0)             
{
if(x & mask > y & mask)        
{printf("x greater");break;}
else if(y & mask > x & mask)
{printf("y greater");break;}
mask=mask>>1;                  // shift 1 in mask to the right
}

Answer 5

Compare the bits from left to right, looking for the leftmost bits that differ. Assuming a machine that is two's complement, the topmost bit determines the sign and will have a flipped comparison sense versus the other bits. This should work on any two's complement machine:

int compare(int x, int y) {
  unsigned int mask = ~0U - (~0U >> 1); // select left-most bit
  if (x & mask && ~y & mask)
    return -1; // x < 0 and y >= 0, therefore y > x
  else if (~x & mask && y & mask)
    return 1; // x >= 0 and y < 0, therefore x > y
  for (; mask; mask >>= 1) {
    if (x & mask && ~y & mask)
      return 1;
    else if (~x & mask && y & mask)
      return -1;
  }
  return 0;
}

[Note that this technically isn't portable. C makes no guarantees that signed arithmetic will be two's complement. But you'll be hard pressed to find a C implementation on a modern machine that behaves differently.]

To see why this works, consider first comparing two unsigned numbers, 13d = 1101b and 11d = 1011b. (I'm assuming a 4-bit wordsize for brevity.) The leftmost differing bit is the second from the left, which the former has set, while the other does not. The former number is therefore the larger. It should be fairly clear that this principle holds for all unsigned numbers.

Now, consider two's complement numbers. You negate a number by complementing the bits and adding one. Thus, -1d = 1111b, -2d = 1110b, -3d = 1101b, -4d = 1100b, etc. You can see that two negative numbers can be compared as though they were unsigned. Likewise, two non-negative numbers can also be compared as though unsigned. Only when the signs differ do we have to consider them -- but if they differ, the comparison is trivial!