Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?

by 
int getMax(int a, int b) {
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

Let’s dissect this. This first line appears to be straightforward – it stores the difference of a and b. This value is negative if a < b and is nonnegative otherwise. But there’s actually a bug here – if the difference of the numbers a and b is so big that it can’t fit into an integer, this will lead to undefined behavior – oops! So let’s assume that doesn’t happen here.

In the next line, which is

int k = (c >> 31) & 0x1;

the idea is to check if the value of c is negative. In virtually all modern computers, numbers are stored in a format called two’s complement in which the highest bit of the number is 0 if the number is positive and 1 if the number is negative. Moreover, most ints are 32 bits. (c >> 31) shifts the number down 31 bits, leaving the highest bit of the number in the spot for the lowest bit. The next step of taking this number and ANDing it with 1 (whose binary representation is 0 everywhere except the last bit) erases all the higher bits and just gives you the lowest bit. Since the lowest bit of c >> 31 is the highest bit of c, this reads the highest bit of c as either 0 or 1. Since the highest bit is 1 iff c is 1, this is a way of checking whether c is negative (1) or positive (0). Combining this reasoning with the above, k is 1 if a < b and is 0 otherwise.

The final step is to do this:

int max = a - k * c;

If a < b, then k == 1 and k * c = c = a - b, and so

a - k * c = a - (a - b) = a - a + b = b

Which is the correct max, since a < b. Otherwise, if a >= b, then k == 0 and

a - k * c = a - 0 = a

Which is also the correct max.

More Related Contents:

  1. The most efficient way to implement an integer based power function pow(int, int)
  2. What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?
  3. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  4. Power by squaring for negative exponents
  5. How do you print the EXACT value of a floating point number?
  6. Compute fast log base 2 ceiling
  7. C – How to implement Set data structure?
  8. Gaussian elimination without result for acceleration
  9. signed and unsigned arithmetic implementation on x86
  10. What’s the quickest way to compute log2 of an integer in C#?
  11. Algorithm to generate bit mask
  12. How does this bitwise operation check for a power of 2?
  13. A possible algorithm for determining whether two strings are anagrams of one another? [closed]
  14. Algorithm to pick values from array that sum closest to a target value?
  15. Algorithm to find the smallest number in an array in C [closed]
  16. Finding target sum of two numbers in array
  17. How can I multiply and divide using only bit shifting and adding?
  18. hash function for string
  19. What is CHAR_BIT?
  20. What is the efficient way to count set bits at a position or lower?
  21. How to add two numbers without using ++ or + or another arithmetic operator
  22. Time complexity of a recursive algorithm
  23. warning: left shift count >= width of type
  24. Generating a uniform distribution of INTEGERS in C
  25. Finding out the duplicate element in an array
  26. How to replace bits in a bitfield without affecting other bits using C
  27. Intersection of two lines defined in (rho/theta ) parameterization
  28. Does C have any tools for doing string addition?
  29. C Programming – XOR Bitwise Operation
  30. Best algorithm for evaluating a mathematical expression?

Leave a Comment