leetcode/lcci/16.07.Maximum

comments	difficulty	edit_url
true	Easy	https://github.com/doocs/leetcode/edit/main/lcci/16.07.Maximum/README_EN.md

16.07. Maximum

中文文档

Description

Write a method that finds the maximum of two numbers. You should not use if-else or any other comparison operator.

Example:

Input:  a = 1, b = 2
Output:  2

Solutions

Solution 1: Bitwise Operation

We can extract the sign bit k of a-b. If the sign bit is 1, it means a \lt b; if the sign bit is 0, it means a \ge b.

Then the final result is a \times (k \oplus 1) + b \times k.

The time complexity is O(1), and the space complexity is O(1).

Python3

class Solution:
    def maximum(self, a: int, b: int) -> int:
        k = (int(((a - b) & 0xFFFFFFFFFFFFFFFF) >> 63)) & 1
        return a * (k ^ 1) + b * k

Java

class Solution {
    public int maximum(int a, int b) {
        int k = (int) (((long) a - (long) b) >> 63) & 1;
        return a * (k ^ 1) + b * k;
    }
}

C++

class Solution {
public:
    int maximum(int a, int b) {
        int k = ((static_cast<long long>(a) - static_cast<long long>(b)) >> 63) & 1;
        return a * (k ^ 1) + b * k;
    }
};

Go

func maximum(a int, b int) int {
	k := (a - b) >> 63 & 1
	return a*(k^1) + b*k
}

TypeScript

function maximum(a: number, b: number): number {
    const k: number = Number(((BigInt(a) - BigInt(b)) >> BigInt(63)) & BigInt(1));
    return a * (k ^ 1) + b * k;
}

Swift

class Solution {
    func maximum(_ a: Int, _ b: Int) -> Int {
        let diff = Int64(a) - Int64(b)
        let k = Int((diff >> 63) & 1)
        return a * (k ^ 1) + b * k
    }
}