# Integer comparisons via bit operations

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.

`(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

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

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.

(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

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.

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