The fn odd_ones(x: u32) -> bool
function should return true
when x
contains a odd number of 1s.
Assumption:
x
is 32 bit unsigned.
Restriction:
- The code should contain a total of at most 12 arithmetic, bitwise and logical operations.
Forbidden:
- Conditionals, loops, function calls and macros.
- Division, modulus and multiplication.
- Relative comparison operators (
<
,>
,<=
and>=
).
Allowed operations:
- All bit level and logic operations.
- Left and right shifts, but only with shift amounts between 0 and w - 1
- Addition and subtraction.
- Equality (
==
) and inequality (!=
) tests. - Casting between
u32
andi32
.
My code: (Rust playground)
fn odd_ones(x: u32) -> bool {
let mid = (x >> 16) ^ x;
let mid2 = (mid >> 8) ^ mid;
let mid3 = (mid2 >> 4) ^ mid2;
let mid4 = (mid3 >> 2) ^ mid3;
(((mid4 >> 1) ^ mid4) & 1) == 1
}
fn odd_ones_test(x: u32) -> bool {
let sum = (0..32).map(|y| x >> y )
.fold(0, |sum ,y| sum + (y & 1));
sum % 2 != 0
}
fn test (from: u32, to: u32) -> bool {
(from..to).all(|x| odd_ones_test(x) == odd_ones(x))
}
fn main() {
println!("{}", test(!0 - 45345, !0));
}
Any better way of doing this?
gcc
you would use__builtin_parity
. Isn't something similar in Rust? \$\endgroup\$count_ones
uses LLVM intrinsics, which seems likely to call the x86_64popcnt
instruction when available. Remember that Rust is meant to be used on multiple processor architectures, andpopcnt
is SSE 4.2, so it's comparatively new. Of course, both C and Rust allow raw assembly, so you can always access it. \$\endgroup\$