Maximum of three integers using bitwise operations?

Question

How would I return the maximum of three unsigned integers using only bit-wise operations, such as !,~,|,&,^,+,>>,<<. I don't know where to start. Any help would be appreciated.

edit:

I am only allowed to use the given legal ops, thats it.

/** maxOfThree - Returns the maximum of three integers.
* NOTE: x, y, z are all in the range [0, TMax].
* Examples: maxOfThree(1, 2, 3) = 3
* Legal Ops: ! ~ & ^ | + << >>
* Max Ops: 25
int maxOfThree(int x, int y, int z) {
}

As you have no code to show at all, here is some hint to get you started: Take 10 integers between 1 and 100. Sort them Write down their binary representation. Look at the binary digits. Maybe you get an idea. — Guntram Blohm, Feb 16 '14 at 21:07

Marco A. · Accepted Answer · 2014-02-16T23:26:12.383

Take a look at the "bit-twiddling hacks" page and study how maximum/minimum are implemented.

If you can figure out how the maximum for two numbers works, then you can generalize the case for three numbers.

Let me explain to you the two-numbers case for getting the maximum value:

-(a<b) can either return -1 or 0, then you can have either 11111111 11111111 11111111 11111111 (-1 in two's complement for an int) or 00000000 00000000 00000000 00000000 (-0 == 0 for an int).

Remembering that a^b^b = a and that a^b^a = b (doesn't matter what the order is, this is the xor operation), you have that in the first case:

If a < b you need to return b as result, so

a ^ ((a ^ b) & -(a < b)) must be equal to a ^ a ^ b.. and in fact it is since -(a<b) returns 11111111 11111111 11111111 11111111, and an and-bitwise & operated on 11111111 11111111 11111111 11111111 for an unsigned integer leaves the number unchanged... thus a ^ a ^ b = b. This is the maximum.

If a > b then a < b is false, thus (anything & 00000000 00000000 00000000 00000000) is 0. And thus you have a ^ 0, which is, a. The maximum.

And finally we have the solution generalized for three numbers:

#include <stdio.h>

int getMax(unsigned int a, unsigned int b, unsigned int c) {
    int temp = a ^ ((a ^ b) & -(a < b)) ;
    int r = c ^ ((c ^ temp) & -(c < temp));
    return r;
}

int main(void) {
    unsigned int a = 3, b = 1, c = 9;

    printf("%d", getMax(a,b,c));
    return 0;
}

Edit: if you're not allowed to use "<" then use the second version

x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));

and keep in mind the following excerpt

Note that the 1989 ANSI C specification doesn't specify the result of signed right-shift, so these aren't portable. If exceptions are thrown on overflows, then the values of x and y should be unsigned or cast to unsigned for the subtractions to avoid unnecessarily throwing an exception, however the right-shift needs a signed operand to produce all one bits when negative, so cast to signed there

Edit II: this should work with the specification you posted:

#include <stdio.h>

int getMax(int x, int y, int z) {
    int r  =  (x + ~((x+~y+1) & ((x+~y+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31
    int r2 =  (z + ~((z+~r+1) & ((z+~r+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31
    return  r2;
}

int main(void) {
    unsigned int a = 5, b = 7, c = 1;

    printf("%d", getMax(a,b,c));
    return 0;
}

Notice that it would be better if you could use sizeof() instead of just assuming that an int is 4 bytes (it isn't true on all platforms).

Fortunately you *are* allowed to use `{`. How silly can those school assignments get? — Jongware, Feb 16 '14 at 21:31
Much as I like the bit twiddling hacks page, the above answer doesn't quite work, because if `aa)*(b-a)`, which is rather simpler than the above. I don't think `a — abligh, Feb 16 '14 at 21:32
I agree, if '<' isn't allowed then the solution with the CHAR_BIT should be used instead — Marco A., Feb 16 '14 at 21:33
@DavidKernin Your edited solution relies on a specific behaviour of signed right shift, which is implementation defined. You should probably add that as a caveat. — Juri Robl, Feb 16 '14 at 21:37
Im only allowed to use the given ops nothing else, not CHAR_bit, <, >, or even *. — user3316874, Feb 16 '14 at 21:47
@user3316874 I posted another solution which might be helpful — Marco A., Feb 16 '14 at 23:26

score 0 · Answer 2 · answered Feb 16 '14 at 21:42

If you are allowed to use - (you suggest +), I suggest the following (untested) which is I think more efficient than the bit twiddling page, particularly if the first max is as a macro, and we know we are dealing with signed ints.

#define MAX2(a,b) (a-((a-b) >> (sizeof(int) * CHAR_BIT - 1))*(b-a))
int
max3 (int x, int y, int z)
{
    return MAX2(MAX2(x, y), z);
}

CHAR_BIT should be #define'd to 8 on most platforms.

This also relies on the undefined behaviour of right shifts of negative numbers.

If you are not allowed to use -, use ~ and addition of 1.

David Kernin's answer is more general though.

Maximum of three integers using bitwise operations?

2 Answers2

Linked