Testing if the binary representation of an integer has an odd number of ones

Question

The fn odd_ones(x: u32) -> bool function should return true when x contains a odd number of 1s.

Assumption:

1. x is 32 bit unsigned.

Restriction:

1. The code should contain a total of at most 12 arithmetic, bitwise and logical operations.

Forbidden:

1. Conditionals, loops, function calls and macros.
2. Division, modulus and multiplication.
3. Relative comparison operators (<, >, <= and >=).

Allowed operations:

1. All bit level and logic operations.
2. Left and right shifts, but only with shift amounts between 0 and w - 1
3. Addition and subtraction.
4. Equality (==) and inequality (!=) tests.
5. Casting between u32 and i32.

---

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?

• anon: For the record, I believe this is called the binary parity of a number.
• Karoly Horvath: Weird world. Though both C and Rust claim they are system-programming languages, neither of them directly support common bit operations (that are on modern processors natively supported) like popcount or parity... In C's case there are compiler extensions, in gcc you would use __builtin_parity. Isn't something similar in Rust?
• glampert: Several other possible solutions here: graphics.stanford.edu/~seander/bithacks.html#ParityNaive
• Shepmaster: Why exactly do you have all of these restrictions? It sounds like this is homework problem or a job interview question.
• Shepmaster: @KarolyHorvath depends what you mean by "directly support". The Rust implementation of count_ones uses LLVM intrinsics, which seems likely to call the x86_64 popcnt instruction when available. Remember that Rust is meant to be used on multiple processor architectures, and popcnt is SSE 4.2, so it's comparatively new. Of course, both C and Rust allow raw assembly, so you can always access it.

Answer 1

Leveraging code that other people wrote is always a great idea. In this case, there is count_ones:

fn odd_ones(x: u32) -> bool { 
 x.count_ones() % 2 == 1
}

This method is a shim for the LLVM intrinsic @llvm.ctpop.i32, which seems likely to become the very optimized SSE4.2 popcnt instruction when available.

Beyond that, you have some poor indentation habits. Rust uses 4-space indents, not the 3 (?!?) spaces you have in your odd_ones function.

There should not be a space between a function name and the arguments, whether in the function definition or the function call. Your test method should be fixed.

Be consistent with your spacing on commas. No space before, one space after. |sum ,y| is just wrong.

You should give names to magic constants. A rogue 32 laying around doesn't mean anything. Give it a name like BITS_IN_U32. There's an unstable constant that you might be able to use someday.

When mapping and folding over an iterator, you might as well put all the mapping into the map call. There's no reason to do the bitwise-and in the fold.

I have no idea what !0 - 45345 is supposed to mean or why those particular values are useful. That's bad news when you try to understand this code in the future.

const BITS_IN_U32: usize = 32;
fn odd_ones(x: u32) -> bool { 
 x.count_ones() % 2 == 1
}
fn odd_ones_test(x: u32) -> bool { 
 let sum = 
 (0..BITS_IN_U32)
 .map(|y| (x >> y) & 1)
 .fold(0, |sum, y| sum + y);
 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)); 
}

• MAG: 1. Calling modulus operation or functions is forbidden. 2. !0 is to represent u32 max value and I wasn't sure what constant rust uses for that, but it was a random choice anyway. 2. "Face palm" cant believe I didn't saw I could pass it everything to the map function :/, good catch . 3. I know it is usually good practice to named constants at the top but in this particular case I don't see it that beneficial . If I change the constant I would have to change the data type as well (That is just my opinion though).

Answer 2

Once I had to count the bits that were set in an array of one million integers. After several naive(very slow) starts I came across some bit twiddling hacks that sped things up dramatically. This is a C# function that contains two methods.

private bool isOddOnes(UInt32 numToCheck)
{
 //first method
 //Dim bitsSetCt As UInt32 = 0
 //numToCheck = numToCheck - ((numToCheck >> 1) And &H55555555UI)
 //numToCheck = (numToCheck And &H33333333UI) + ((numToCheck >> 2) And &H33333333UI)
 //bitsSetCt = ((numToCheck + (numToCheck >> 4) And &HF0F0F0FUI) * &H1010101UI) >> 24
 //second method
 UInt32 bitsSetCt = default(UInt32);
 bitsSetCt = numToCheck - ((numToCheck >> 1) & 0x55555555u);
 bitsSetCt = ((bitsSetCt >> 2) & 0x33333333u) + (bitsSetCt & 0x33333333u);
 bitsSetCt = ((bitsSetCt >> 4) + bitsSetCt) & 0xf0f0f0fu;
 bitsSetCt = ((bitsSetCt >> 8) + bitsSetCt) & 0xff00ffu;
 bitsSetCt = ((bitsSetCt >> 16) + bitsSetCt) & 0xffffu;
 return (bitsSetCt & 1u) == 1u;
}

Answer 3

Since I already know a better way of doing this thanks to this link given by @glampert in the comments and none of the answers so far followed the rules, I will answer my own question to wrap things up:

fn odd_ones(x: u32) -> bool {
 let mut m = x ^ (x >> 16);
 m ^= m >> 8;
 m ^= m >> 4;
 m &= 0xf;
 ((0x6996 >> m) & 1) == 1
}

Using 0x6996 bit pattern saves up 2 operations. Also, the use of ^= makes the code more compact.