Strange is_even(x)

I was stuck on this too but I found a zero allocation way:

async fn is_even(input: i32) -> bool {
 use is_odd::IsOdd;
 let exponent_mask = 0x7F800000;
 let significand_mask = 0x007FFFFF;
 let remainder = exponent_mask - input.is_odd() as i128;
 let callback = { <i128>::div_euclid };
 ::is_odd::IsOdd::is_odd(&(callback(remainder, 1) as u8));
 let exponent_bias = 0x7F_i128;
 let helper = remainder + exponent_bias & significand_mask;
 return helper.count_ones().is_odd() ||
     helper.overflowing_mul(exponent_mask).1;
}

– dtolnay

Programmers sometimes attempt humor. A good example is is-even: a library which determines the evenness of a number. This bit of satire comes up every now-and-then in talks of frivolous software dependencies. Anyhow, with all the hype Rust has got recently, it’s understandable how such an important library would be ported over—this time as is-odd.

Now, simply knowing the oddness of a number is not enough to know evenness¹, and naturally an issue was filed for this discrepancy in which the above solution was posted.

How it works

Clearly this example is designed to be obtuse; I’ll try to simplify.

There are a bunch of slight issues (useless async and return), but the largest is all the indirection. Most obviously, the 6th and 7th lines don’t do anything. Additionally, there are a few non-helpful magic number variables. We simplify all that:

fn is_even(input: i32) -> bool {
    let remainder = 0x7F800000 - input.is_odd() as i128;
    let helper = remainder + 0x7F & 0x007FFFFF;
    helper.count_ones().is_odd()
        || helper.overflowing_mul(0x7F800000).1
}

That’s a lot nicer. The helper variable determines the final output so let’s trace its possible values. Because helper only depends on the oddness of input, it can only have two values. Let’s write them explicitly.

fn is_even(input: i32) -> bool {
    let helper: i128 = if input.is_odd() {
        (0x7F800000 - 1) + 0x7F & 0x007FFFFF
    } else {
        0x7F800000 + 0x7F & 0x007FFFFF
    };
    helper.count_ones().is_odd()
        || helper.overflowing_mul(0x7F800000).1
}

Throwing the constants in SpeedCrunch says that if input.is_odd(), helper is 126, else 127. Substituting back in:

fn is_even(input: i32) -> bool {
    if input.is_odd() {
        126i128.count_ones().is_odd() 
            || 126i128.overflowing_mul(0x7F800000).1
    } else {
        127i128.count_ones().is_odd()
            || 127i128.overflowing_mul(0x7F800000).1
    }
}

Looking at the count_ones part, 126 has six ones (even) in binary and 127 has seven (odd). Simplify:

fn is_even(input: i32) -> bool {
    if input.is_odd() {
        // because 126 has an even count of ones in binary
        false
            || 126i128.overflowing_mul(0x7F800000).1
    } else {
        // because 127 has an odd count of ones in binary
        true
    }
}

So the final unknown is the value of 126i128.overflowing_mul(0x7F800000).1. This expression multiplies 126 × 0x7F800000, and returns a boolean saying if it overflowed. Does this overflow? We’re working with 128-bit signed integers, so the maximum is 2^127-1 or 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF. The result of the multiplication is 0x3EC1000000. By the amount of F’s given, we can be sure there was no overflow. All that we’re left with is:

fn is_even(input: i32) -> bool {
    !input.is_odd()
}

Beautiful.