Comparing Two Integers Without Any Comparison

Comparing two integers without any comparison

Subtract them and check the sign using nasty bit twiddling hacks

http://graphics.stanford.edu/~seander/bithacks.html

Don't do this in production code if the other programmers know where you live.

Comparing two integers without using any comparison (recursion, python)

Since your function needs to work only for positive integers, you can decrement both numbers at the same time and see which one of them reaches 0 first. Then you can easily decide:

def less_than(a, b):  # ONLY NEEDS TO WORK FOR POSITIVE INTEGERS
    if a == b:
        return False
    while a != 0 and b != 0:
        a -= 1
        b -= 1
    # we're out of the loop, one of the numbers should be 0
    if a == 0:
        return True
    return False

>>> less_than(4, 5)
True
>>> less_than(4, 4)
False
>>> less_than(4, 3)
False

How we must compare two integers?

The preferred way to write the non-branching code would be to use a local variable for the operands:

int icmp(const void *x, const void *y)
{
    int a = *(const int *)x;
    int b = *(const int *)y;
    return (a > b) - (a < b);
}

The expression is a common idiom in comparison functions, and if written using variables instead of in-place pointer dereferences it is rather readable too.

The code relies upon the fact that the result of a comparison using >, < or even == is of type int and either 1 or 0. This is required by the C standard - any compiler that generates values like 42 or -1 is by definition not a C compiler.

It is easy to see that max. one of a > b or a < b can be true at a given time, and the result is either 1 - 0, 0 - 1 or 0 - 0.

As to why branchless code - while compilers might generate the exact same code for both functions, they often do not. For example latest GCC and ICC both seem to generate a branch for the first function on x86-64, but branchless code with conditional execution for the latter. And to anyone who says that branches do not matter, then I refer you to the highest-voted QA ever on Stack Overflow.

Comparing two numbers without comparison operators in verilog

Remember that the leftmost bit of a negative number is aways 1. So you can use it to check the sign of the difference.

input[7:0] in1,in2;
output select;
wire [7:0] difference = in1-in2;
wire sign_of_difference = difference[7];
assign select = sign_of_difference? 0:1;

How to I use bitwise operators to compare two unsigned integers?

Let's us consider two integers 4 (0100) and 3 (0011). We need to generate the biggest-sub-bits-series which differentiate the two integers, for example above it is 0100 ( since the third bit is different ), then we can simply know which is bigger by making bit AND operation:

0100 & 0100 = 0100 > 0  
0011 & 0100 = 0

The code is as follows:

#include <stdio.h>
int main()
{
  int a, b;

  printf("Enter two numbers\n");
  scanf("%d%d", &a, &b);

  int diff = a ^ b;
  if (diff)  //true means both are not equal
  {
    diff = diff | (diff >> 1);
    diff |= diff >> 2;
    diff |= diff >> 4;
    diff |= diff >> 8;
    diff |= diff >> 16;
    diff ^= diff >> 1;

    int res = (a & diff) ? 1 : 0;

    if (res)
        printf("%d greater than %d", a, b);
    else
        printf("%d greater than %d", b, a);
   }

  else //both equal
  {
    printf("Both are equal\n");
    return 0;
  }

  return 0;
}

Compare two integers for equality in C++ with unknown int types

You can use std::common_type to remove the warning.

#include <type_traits>
template<typename A, typename B>
bool is_numbers_equal(A a, B b) {
    using C = typename std::common_type<A, B>::type;
    return (a > 0) == (b > 0) && static_cast<C>(a) == static_cast<C>(b);
    // or maybe `... && C(a) == C(b);`
}

Well, this looks fun to optimize it for the compiler for types that both are the "same":

#include <type_traits>

template<typename A, typename B>
typename std::enable_if<
    std::is_integral<A>::value &&
    std::is_integral<B>::value &&
    (std::is_signed<A>::value ^ std::is_signed<B>::value)
, bool>::type
is_numbers_equal(A a, B b) {
    using C = typename std::common_type<A, B>::type;
    return (a >= 0) == (b >= 0) && 
        static_cast<C>(a) == static_cast<C>(b);
}

template<typename A, typename B>
typename std::enable_if<
    ! (
        std::is_integral<A>::value &&
        std::is_integral<B>::value &&
        (std::is_signed<A>::value ^ std::is_signed<B>::value)
    )
, bool>::type
is_numbers_equal(A a, B b) {
    return a == b;
}

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

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.

---

Related Topics