What else can the less than operator mean in C?

Question

I am learning bit algorithm and saw the equation that finds the max of two values:

r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

The explanation says this equation will find the max without using comparison and "if x < y, then -(x < y) will be all ones". I cannot comprehend what the explanation means because I see a "less than" operator in the equation and if that is an less than operator, (x < y) should return only one bit of data. Therefore, for the explanation to make sense, the sign "<" cannot be the less than operator. I looked at the list of C operators and did not find other meanings for operator "<". Can someone tell me what does the operator "<" do in this equation? Thanks!

It *is* the “less than” operator. `x < y` is either 0 or 1. `-(x < y)` is either 0 or −1. — Ry-, Mar 16 '17 at 04:51
It doesn't find the max "without using comparison", it just uses a comparison in a less straightforward way... so the explanation is questionable. Without using a *conditional*, maybe... — Dmitri, Mar 16 '17 at 05:11

Antoine Trouve · Accepted Answer · 2017-03-17T03:25:23.390

2

This is a very tricky code. The truth is that C does not have any Boolean type: it uses integer instead: 0 for false and 1 for true.

Therefore -(x<y) means

0 if x≥y
-1 if x<y

It is then used as a bit mask.

Edit

As suggested by Jonathan Leffler in comments, C has now a _Bool. I made this small program to check what is it and how it is used:

#include <stdio.h>

int main() {  
  _Bool bFalse = 1>2;    
  printf("size of _Bool: %lu\nsize of comparison result: %lu\n", sizeof(bFalse), sizeof(1>2));
  return 0;
}

This outputs:

size of _Bool: 1
size of comparison result: 4

In other words _Bool is one byte (a char), but it is not used as a result of Boolean comparisons (my compiler generates 4 bytes, that is, an int)

Note: tested with Clang on an Intel processor.

Edit: fix the types as kindly suggested in comments (and after checking the clang IR)

edited Mar 17 '17 at 03:25

answered Mar 16 '17 at 04:51

Antoine Trouve

1,198
10
21

1

The truth is that C has had a Boolean type, `_Bool` (and `bool` if you include ``) since the 1999 standard. – Jonathan Leffler Mar 16 '17 at 04:54
`_Bool` is a native type, not an unsigned char or whatever. You could read the documentation for it instead of trying to guess its behaviour – M.M Mar 16 '17 at 05:22
The result of a comparison is of type `int`, not `unsigned int`. Please don't guess. – Keith Thompson Mar 16 '17 at 06:10

score 2 · Answer 2 · edited May 23 '17 at 12:09

2

"if x < y, then -(x < y) will be all ones"

This is because, if x is less than y, condition evaluates to true (equal to 1). Notice the negetive sign before comparison, it makes the "1" of comparison result as "-1". In binary world, -1 has an all 1 representation, see Two's_complement. Example: 1111 1111 = -1.

However, if x > y, you get a -0 which is again all zero in binary.

Here, '<' is only a "x is_less_than y" comparison check, a logical operator.

edited May 23 '17 at 12:09

Community

1
1

answered Mar 16 '17 at 04:58

vishwarajanand

1,021
13
23

1

C implementations do not all use 2's complement. So we could say that the OP code relies on being run on a 2's complement implementation. – M.M Mar 16 '17 at 05:24

What else can the less than operator mean in C?

2 Answers2