Integer comparisons via bit operations

Using Swift
1

I am looking for a way to express the following:

func compare(x: UInt64, y: UInt64) -> UInt64 {
	x < y ? 1 : 0
}

without using comparisons but only using:

  1. arithmetic &+, &-
  2. bit operations: &, |, ^, ~, >>, <<
  3. casts between Int64 and UInt64
  4. literals like 1, etc.

I remember I did it way in the past, so it must be possible, but can't quite remember what did I do.

2

(x < y ? 1 : 0) is precisely the borrow-out from x - y, or bit 64 if you view them as arbitrarily zero-extended bignums. There's a bunch of ways to get at that bit, but probably the easiest to understand is to just split each of x and y into high and low halves, subtract low halves, shift the borrow down, subtract high halves with the borrow, and shift the borrow down to get 1 or 0 out.

2 Likes
3

May I ask why you want to do this?

I would expect the optimizer to turn “x < y ? 1 : 0” into, well, whatever instructions are optimal.

2 Likes
4

This is more complicated than I thought.

Found this elsewhere:

func compare1(x: UInt64, y: UInt64) -> UInt64 {
    let r = x &- y
    return ((y & r) | ((y | r) & ~x)) >> 63
}

// reference implementation:
func compare2(x: UInt64, y: UInt64) -> UInt64 {
    x < y ? 1 : 0
}

Seems to be working good.

5

(1) If you’re hoping to get constant-time code, know that this is more likely to result in constant-time code, but it is not guaranteed to result in constant-time code, because LLVM can and will optimize bitwise operations to conditions. (Note that the code you get from an optimized x < y ? 1 : 0 will almost certainly be constant-time on any modern CPU, post-optimization.)

(2) x < y when y - x < 0, which is

UInt64(y.subtractingReportingOverflow(x).overflow)

Which is kind of what Steve said, and kind of breaking your rules, but is still probably the second clearest thing (the clearest being x < y ? 1 : 0)

EDIT: I take it back, because we don’t have an integer-from-Bool initializer, because ?: is fine.

1 Like
6

No, that's not about performance.

I found a bug in my "standard library free" implementation of "func <" used in a side project. The code in question looks like:

    static func < (a: XUInt64, b: XUInt64) -> XBool {
        let c = a - b
        if case .i = c.tuple.elements.7.bits.elements.7 {
            return .true
        }
        return .false
    }

As written it doesn't handle overflows correctly, and the listed "allowed" primitive operations is about all I have available at my disposal.

OTOH, I could just use a loop and scan through the bit string from the most significant to the least significant bits and find the first difference. Will give that a try as well.

7

I have sometimes found it convienient to write this extension for Numeric:

extension Numeric {
    init(_ predicate: Bool) {
        self = if predicate { 1 } else { 0 }
    }
}

It'd be nice if it were in the standard library like it is in Rust. It's not problematic like it is in C, because you have to call the initializer explicitly.

1 Like